À faire en classe
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
1.
Solution.
On travaille modulo \(5\text{.}\) On a
\begin{align*}
0^5 \amp\equiv 0 \mod 5\\
1^5 \amp\equiv 1 \mod 5\\
2^5 = 32 \amp\equiv 2 \mod 5\\
3^5 = 243 \amp\equiv 3\mod 5\\
4^5 = 1024 \amp\equiv 4 \mod 5\text{.}
\end{align*}
Ainsi, dans tous les cas, on a \(n^5 \equiv n \mod 5\text{,}\) ou encore \(n^5-n\equiv 0 \mod 5\text{,}\) c’est-à-dire que \(5\) divise \(n^5-n\text{.}\)
2.
Montrer que, si \(n\in \N\) est tel que \(n\geq 3\text{,}\) alors \(n^2-1\) est un nombre composé (c’est-à-dire, n’est pas un nombre premier).
Solution.
On travaille modulo \(n-1\text{.}\) On a alors \(n \equiv 1 \mod (n-1)\text{,}\) et donc
\begin{align*}
n^2 \amp \equiv 1 \mod (n-1)\\
n^2 -1 \amp \equiv 0 \mod (n-1)
\end{align*}
c’est-à-dire que \((n-1)\mid (n^2-1)\text{.}\) Puisque \(n\geq 3\text{,}\) on a que \(1 \lt n-1 \lt n^2-1 \text{.}\) Ainsi, \(n^2-1\) n’est pas un nombre premier.
3.
Déterminer quels sont les entiers \(n\in \N\) qui respectent l’inégalité \(2n+3\leq 2^n\text{.}\) Démontrer votre réponse à l’aide d’une preuve par récurrence.
Solution.
On peut vérifier que \(2n+3 \gt 2^n\) pour \(n\in\{0,1,2,3\}\text{.}\) On veut montrer que \(2n+3\leq 2^n\) pour \(n\geq 4\text{.}\)
Étape de base: En \(n=4\text{,}\) on a \(2(4)+3 = 11 \leq 2^4 = 16\text{.}\) Ainsi, la proposition est vraie pour \(n=4\)
Étape d’induction: On suppose que \(2k+3 \leq 2^k\) pour un certain entier \(k \geq 4\) (H.I.). On a alors
\begin{align*}
2(k+1)+3 \amp =(2k+3) +2 \\
\amp \leq (2^k) +2 \amp\amp \text{ Par H.I.} \\
\amp \leq 2^k +2^k \amp\amp \text{ Car } k\geq 4 \\
\amp \leq 2\cdot 2^k \amp\amp \text{ Mise en évidence} \\
\amp \leq 2^{k+1} \amp\amp \text{ Propriétés des exposants} \text{.}
\end{align*}
Ainsi, la proposition est vraie pour \(n=k+1\text{.}\)
On a montré que la proposition est vraie pour \(n=4\text{,}\) et que si elle est vraie pour \(n=k\text{,}\) alors est est aussi vraie pour \(n=k+1\text{.}\) Ainsi, par le principe de récurrence, la proposition est vraie pour tout entier \(n\geq 4\text{.}\)
4.
Soit \(x,\ y \in \R\) et \(n,\ r\in \N\) tels que \(0\leq r\leq n\text{,}\) alors le coefficient devant le terme \(x^{n-r} y^{r}\) de l’expression \((x+y)^n\) est donné par \(\Binomial{n}{n-r}\text{.}\)
Solution.
procède par récurrence sur \(n\) .
Étape de base: On montre que la proposition est vraie pour \(n=0\text{.}\) Dans ce cas, on a nécessairement \(r=0\text{,}\) et \((x+y)^0=1=1x^0y^0\text{,}\) et on a bien que le coefficient devant \(x^{n-r}y^{r}=x^0y^0\) est \(1=\Binomial{n}{n-r}=\Binomial{0}{0}=1\text{.}\)
Étape d’induction: On suppose que la proposition est vraie pour \(n=k\text{,}\) c’est-à-dire que
\begin{equation*}
(x+y)^{k}=\Binomial{k}{k}x^ky^0+\Binomial{k}{k-1}x^{k-1}ky^1+\cdots +\Binomial{k}{k-(k-1)}x^{1}y^{k-1}+\Binomial{k}{k-k}x^0y^k
\end{equation*}
Ainsi, on a
\begin{align*}
(x+y)^{k+1}\amp = (x+y)^k(x+y)^1 \amp\amp\\
\amp = \left(\Binomial{k}{k}x^ky^0+\Binomial{k}{k-1}x^{k-1}y^1+\cdots +\Binomial{k}{k-(k-1)}x^{1}y^{k-1}+\Binomial{k}{k-k}x^0y^k\right) (x+y)^1 \amp\amp \text{Par H.I.}\\
\amp = \Binomial{k}{k}x^{k+1}y^0+\Binomial{k}{k-1}x^{k}y^1+\cdots +\Binomial{k}{k-(k-1)}x^{2}y^{k-1}+\Binomial{k}{k-k}x^1y^k \amp\amp \text{(en multipliant la somme par }x\text{)}\\
\amp + \Binomial{k}{k}x^ky^1+\Binomial{k}{k-1}x^{k-1}y^2+\cdots +\Binomial{k}{k-(k-1)}x^{1}y^{k}+\Binomial{k}{k-k}x^0y^k (x+y)^1 \amp\amp \text{(en multipliant la somme par }y\text{)}\\
\amp = \Binomial{k}{k}x^{k+1}y^0 + \left(\Binomial{k}{k-1} +\Binomial{k}{k} \right)x^{k}y^1+\cdots +\left(\Binomial{k}{k- k}+\Binomial{k}{k-(k-1)}\right)x^{1}y^{k-1}+\Binomial{k}{k-k}x^0y^k \amp\amp \text{En regroupant les termes}\\
\amp = \Binomial{k+1}{k+1}x^{k+1}y^0 + \left(\Binomial{k+1}{k}\right)x^{k}y^1+\cdots +\left(\Binomial{k+1}{1}\right)x^{1}y^{k-1}+\Binomial{k+1}{0}x^0y^k \amp\amp \text{Par }\knowl{./knowl/xref/prop-formulePascal.html}{\text{4.2.17}}.
\end{align*}
Ainsi, la proposition est vraie pour \(n=k+1\text{.}\)
On a montré que la proposition est vraie pour \(n=0\text{,}\) et que si elle est vraie pour \(n=k\text{,}\) alors elle est vraie pour \(n=k+1\text{.}\) Ainsi, la proposition est vraie pour tout \(n\in \N\text{.}\)
5.
Montrer qu’il existe une infinité de nombres premiers.
6.
Montrer que, pour \(n\in \N^\ast\text{,}\) la somme des \(n\) premiers cubes est
\begin{equation*}
\frac{n^2(n+1)^2}{4}\text{.}
\end{equation*}
Ainsi, on veut montrer que
\begin{equation*}
1^3+2^3+\cdots + n^3 =\frac{n^2(n+1)^2}{4}
\end{equation*}
Solution.
Étape de base: On vérifie que la proposition est vraie pour \(n=1\text{.}\) En effet, on a \(1=1^3=\frac{1^2(1+1)^2}{4}=\frac{4}{4}=1\text{.}\)
Étape d’induction: On suppose que \(1^3+2^3+\cdots + k^3 =\frac{k^2(k+1)^2}{4}\) pour \(k\geq 1\) (H.I.).
Ici, il sera plus facile de travailler en posant \(j=k+1\text{,}\) et donc \(k=j-1\text{.}\) Avec ce changement de variables, on a
\begin{align*}
1^3+2^3+\cdots + k^3 + (k+1)^3 \amp = 1^3+2^3+\cdots + (j-1)^3 + j^3 \amp\amp \text{Par le changement de variables} \\
\amp = \frac{(j-1)^2j^2}{4} + j^3 \amp\amp \text{Par H.I.} \\
\amp = \frac{(j-1)^2j^2 +4j^3}{4} \amp\amp \text{Par manipulation algébrique} \\
\amp = \frac{((j-1)^2 +4j)j^2}{4}\amp\amp \text{Par manipulation algébrique} \\
\amp = \frac{(j^2-2j+1 +4j)j^2}{4}\amp\amp \text{Par manipulation algébrique} \\
\amp = \frac{(j^2+2j+1)j^2}{4}\amp\amp \text{Par manipulation algébrique} \\
\amp = \frac{(j+1)^2j^2}{4}\amp\amp \text{Par manipulation algébrique} \text{.}
\end{align*}
Ainsi, la proposition est vraie pour \(n=k+1\text{.}\)
On a montré que la proposition est vraie pour \(n=1\text{,}\) et que si elle est vraie pour \(n=k\text{,}\) alors elle est vraie pour \(n=k+1\text{.}\) Ainsi, la proposition est vraie pour tout \(n\in \N^\ast\text{.}\)
7.
Soit \(n\in \N\text{,}\) montrer que si \(3\) divise \(n^3\text{,}\) alors \(3\) divise \(n\text{.}\)
Solution.
On peut simplement remarquer que
\begin{gather*}
0^3 = 0 \equiv 0 \mod 3\\
1^3 = 1 \equiv 1 \mod 3\\
2^3 = 8 \equiv 2 \mod 3\text{.}
\end{gather*}
Ainsi, on a que le seul moment où \(n^3\equiv 0 \mod 3\) est lorsque \(n \equiv 0 \mod 3\text{.}\) On peut conclure que si \(3\mid n^3\text{,}\) alors \(3\mid n\text{.}\)
8.
Montrer que \(\sqrt[3]{3}\) est un irrationnel.
Solution.
On procède à l’aide d’une preuve par contradiction. On suppose que \(\sqrt[3]{3}\in \Q\text{.}\) On peut alors écrire \(\sqrt[3]{3}=\frac{p}{q}\text{,}\) avec \(p, q\in \N\) et \(q\neq 0\text{.}\) On peut également supposer que la fraction est réduite au maximum, c’est-à-dire que \(\pgcd(p,q)=1\)
On a alors
\begin{align*}
3=\left(\sqrt[3]{3}\right)^3 \amp \frac{p^3}{q^3}\\
3 q^3 \amp= p^3\text{.}
\end{align*}
Ainsi, on a que \(3\) divise \(p^3\text{.}\) Par l’exercice 5.4.7, on a que \(3\) divise \(p\text{.}\) On peut alors écrire \(p=3k\text{,}\) pour \(k\in \Z\text{.}\) En remplaçant \(p\) dans l’expression précédente, on obtient
\begin{align*}
3 q^3 \amp= (3k)^3\\
\amp = 3^3k^3\\
q^3 \amp = 3^2k^3\text{.}
\end{align*}
Ainsi, on a que \(3\mid q^3\text{,}\) et par le même argument, on a que \(3\mid q\text{.}\) On a donc que \(3\leq \pgcd(p,q)= 1\text{,}\) ce qui est une contradiction. On peut alors conclure que \(\sqrt[3]{3}\in \Q^c\text{.}\)
9.
Soit \(p\) un nombre premier. Montrer que \(a^2\equiv b^2 \mod p\) si et seulement si \(a\equiv b \mod p\) ou \(a\equiv -b \mod p\text{.}\)
Solution.
Si \(a \equiv \pm b \mod p\text{,}\) on a clairement que
\begin{align*}
a^2 \amp \equiv (\pm b)^2 \mod p\\
\amp \equiv b^2 \mod p
\end{align*}
De l’autre côté, si \(a^2\equiv b^2 \mod p\text{,}\) on a
\begin{align*}
0 \amp \equiv a^2-b^2 \mod p \\
\amp \equiv (a-b)(a+b) \mod p \text{.}
\end{align*}
Si \(a-b \not\equiv 0 \mod p \text{,}\) alors \(a-b\) possède un inverse modulo \(p\text{.}\) Notons \(x\) cet inverse. On a alors
\begin{align*}
0 \amp \equiv (a-b)(a+b) \mod p \\
x\cdot 0 = 0 \amp \equiv x(a-b)(a+b) \mod p \\
0 \amp \equiv (1)(a+b) \mod p \\
0 \amp \equiv (a+b) \mod p \text{.}
\end{align*}
10.
Montrer que
\begin{equation*}
\Binomial{n}{n} + \Binomial{n}{n-1} +\Binomial{n}{n-2} + \cdots + \Binomial{n}{2} + \Binomial{n}{1} + \Binomial{n}{0} = 2^n,
\end{equation*}
ou encore (avec la sommation)
\begin{equation*}
\sum_{k=0}^n \Binomial{n}{n-k}=2^n.
\end{equation*}
Indice.
On peut utiliser plusieurs méthodes pour cette preuve. La première solution, qui ressemble plus aux méthodes utilisées dans ce chapitre, se fera à l’aide du binôme de Newton. La deuxième méthode utilise un argument combinatoire à l’aide du nombre de sous-ensembles.
Solution 1.
On remarque que \(2^n=(1+1)^n\text{.}\) En posant \(x=y=1\text{,}\) la formule du binôme de Newton nous donne
\begin{align*}
2^n = (1+1)^n \amp=(x+y)^n \amp\amp \text{en posant } x=y=1\\
\amp=\Binomial{n}{n}x^n + \Binomial{n}{n-1}x^{n-1}y^1 + \Binomial{n}{n-2}x^{n-2}y^2 + \cdots + \Binomial{n}{2}x^{2}y^{n-2} + \Binomial{n}{1}x^1y^{n-1} +\Binomial{n}{0}y^n \amp\amp \text{par } \knowl{./knowl/xref/prop-binomNewton.html}{\text{4.2.18}} \\
\amp=\Binomial{n}{n} + \Binomial{n}{n-1} +\Binomial{n}{n-2} + \cdots + \Binomial{n}{2} + \Binomial{n}{1} + \Binomial{n}{0} \amp\amp \text{en remplaçant } x, y \text{ par } 1.
\end{align*}
Ici, il est possible d’utiliser la notation sigma. On obtient alors
\begin{align*}
2^n = (1+1)^n \amp=(x+y)^n \amp\amp \text{en posant } x=y=1\\
\amp=\sum_{r=0}^{n} \Binomial{n}{n-r}x^{n-r}y^{r} \amp\amp \text{par } \knowl{./knowl/xref/prop-binomNewton.html}{\text{4.2.18}} \\
\amp=\sum_{r=0}^{n} \Binomial{n}{n-r} \amp\amp \text{en remplaçant } x, y \text{ par } 1.
\end{align*}
Solution 2.
On pose \(Q\) comme étant le nombre de sous-ensembles d’un ensemble \(A\) de cardinalité \(n\text{.}\) D’un côté, on a que \(Q=2^n\text{,}\) par 4.1.9. D’un autre côté, on peut utiliser le principe de la somme pour compter cette quantité. En effet, on rappel que le nombre de sous-ensembles de l’ensemble \(A\) de taille \(r\) est donné par \(\Binomial{n}{r}\text{.}\) Lorsqu’on veut choisir un sous-ensemble quelconque de \(A\text{,}\) celui-ci peut être de cardinalité \(n\text{,}\) ou bien de cardinalité \(n-1\text{,}\) ou bien de cardinalité \(n-2\text{,}\) \(dots\text{,}\) ou bien de cardinalité \(1\) ou bien de cardinalité \(0\text{.}\) Ainsi, par le principe de la somme:
\begin{equation*}
Q=\Binomial{n}{n-1}+\Binomial{n}{n-2}+\Binomial{n}{n-3} \cdots +\Binomial{n}{2}+\Binomial{n}{1}+\Binomial{n}{0}.
\end{equation*}
Par ce qui précède, on a \(2^n=Q=\Binomial{n}{n-1}+\Binomial{n}{n-2}+\Binomial{n}{n-3} \cdots +\Binomial{n}{2}+\Binomial{n}{1}+\Binomial{n}{0}\text{.}\)
11.
Soit \(n\in \N\) tel que \(n\geq 4\text{.}\) En utilisant une preuve par récurrence, montrer que \(n^2-7n+12 \geq 0\text{.}\)Solution.
Étape d’induction: Supposons que \(k^2-7k+12\geq0\text{.}\) On a alors
\begin{align*}
(k+1)^2-7(k+1)+12 \amp= k^2-7k+12 + (2k+1-7) \\
\amp \geq 0 + (2k+1-7) \amp\amp \text{ Par H.I.} \\
\amp \geq (9-7) \amp\amp \text{ Car } k\geq 4 \\
\amp \geq 0 \text{.}
\end{align*}
12.
\(P(k):\) Pour tout \(m,n \in N\text{,}\) si \(k\mid (mn)\text{,}\) alors \(k\mid m\) ou \(k\mid n\text{.}\)
On considère \(p\in \N\) tel que \(p\gt 1\text{.}\) Montrer que si la proposition \(P(p)\) est vraie, alors \(p\) est un nombre premier.
Solution.
Par contradiction, supposons que \(p\) n’est pas un nombre premier tel que \(P(p)\) est vrai. Puisque \(p\) n’est pas premier, on peut écrire \(p=m\cdot n\) pour \(n, m\in \N\) et \(1\lt n,m \lt p\text{.}\) En particulier, \(p\mid p=(m\cdot n)\text{,}\) mais ne divise ni \(m\text{,}\) ni \(n\text{.}\) La proposition \(P(p)\) est donc fausse, ce qui est en contradiction avec notre hypothèse.
13.
Soit \(n\in \N\text{,}\) \(n\geq 2\text{.}\) Montrer par récurrence que si \(p\) est un nombre premier et si \(p\mid (a_1a_2\cdots a_n)\text{,}\) alors il existe un \(i\text{,}\) \(1\leq i\leq n\) tel que \(p\mid a_i\text{.}\)
Solution.
Étape de base: On veut montrer que la proposition est vraie pour \(n=2\text{.}\) Or, pour \(n=2\text{,}\) celle-ci est vraie par 5.1.4.10.
Étape d’induction: On suppose que la proposition est vraie pour \(n=k\text{.}\) Supposons que \(p\mid (a_1a_2\cdots a_ka_{k+1}) \text{.}\) Par 5.1.4.10, on a que \(p\mid (a_1a_2\cdots a_k)\) ou bien \(p\mid a_{k+1}\text{.}\) Si \(p\mid a_{k+1}\text{,}\) on a terminé. Si \(p\mid (a_1a_2\cdots a_k)\text{,}\) par notre hypothèse d’induction, on a que \(p\mid a_i\) pour \(1\leq i \leq k \text{.}\) Ainsi, la proposition est vraie pour \(n=k+1\text{.}\)
On a montré que la proposition est vraie pour \(n=2\text{,}\) et que si elle est vraie pour \(n=k\text{,}\) alors elle est vraie pour \(n=k+1\text{.}\) Ainsi, la proposition est vraie pour tous les entiers \(n \geq 2\text{.}\)
14.
Montrer que si \(n\in \N^\ast\) est tel que la somme de ses diviseurs \(n+1\text{,}\) alors \(n\) est un nombre premier.
Solution.
Par contradiction, supposons que la somme des diviseurs de \(n\) est \(n+1\text{,}\) mais que \(n\) n’est pas un nombre premier. Si \(n\) n’est pas un nombre premier, alors \(n\) possède au moins trois facteurs différents, soit \(1\text{,}\) \(n\) et \(m\in \N^\ast \) tel que \(1\lt m \lt n\text{.}\) La somme des facteurs est donc au moins de \(n+1+m \gt n+1\text{,}\) ce qui est en contradiction avec notre hypothèse. Ainsi, on doit avoir que \(n\) est un nombre premier.
Remarque 5.4.1.
Lorsqu’on montre qu’une proposition \(p\rightarrow q\) est vraie par contradiction, cela revient souvent à faire une preuve indirecte. En effet, on a montré que si \(\neg q\) est vraie, alors \(\neg p\) est vraie.
15.
On place les entiers \(1\) à \(10\) autour d’un cercle, dans n’importe quel ordre. Montrer qu’il existe trois entiers dans des emplacements consécutifs autour du cercle dont la somme est plus grande ou égale à \(17\text{.}\)
Solution.
Supposons que les entiers sont dans l’ordre \(a_1, a_2,\dots , a_{10}\text{.}\) On veut regrouper toutes les sommes de trois voisins consécutifs. Notons donc \(A_1=a_{10}+a_{1}+a_2\text{,}\) \(A_{10}=a_9+a_{10}+a_1\text{,}\) et \(A_{i}=a_{i-1}+a_i+a_{i+1}\) pour \(2\leq i \leq 9\text{.}\)
On a alors que la moyenne des \(A_i\) est \(\frac{3(1+2+\cdots +10)}{10}=16,5\text{.}\) Par l’exercice 5.1.4.9, on a qu’au moins un des \(A_i\geq 16,5\text{.}\) Puisque \(A_i\) est un entier, on a bien que \(A_i\geq 17\text{.}\)
16.
On considère la proposition \(P: \) Pour tout entier positif \(n\text{,}\) si \(x\) et \(y\) sont des entiers positifs, et si \(\max(x,y)=n\text{,}\) alors \(x=y=n\text{.}\)
On rappelle aussi que
\begin{equation*}
max(x,y) = \begin{cases} x \amp \text{si }x\geq y\\y \amp \text{si } x\lt y\end{cases}\text{.}
\end{equation*}
Clairement, la proposition est fausse. Trouver l’erreur dans la démarche ci-dessous.
Étape de base: Pour \(n=1\text{,}\) si \(\max(x,y)=1\text{,}\) alors \(1\leq x\leq\max(x,y)=1\text{,}\) d’où \(1=x\text{.}\) De même, \(1\leq y\leq\max(x,y)=1\text{,}\) d’où \(1=y\)
Étape d’induction: Soit \(k\) un entier positif. On suppose que si \(x_1\) et \(y_1\) sont des entiers positifs, alors \(\max(x_1,y_1)=k\) implique que \(x_1=y_1=k\text{.}\)
On veut montrer que si \(x_2\) et \(y_2\) sont des entiers positifs tels que \(\max(x_2,y_2)=k+1\text{,}\) alors \(x_2=y_2=k+1\text{.}\)
Si \(\max(x_2,y_2)=k+1\text{,}\) alors \(\max(x_2-1,y_2-1)=k\text{.}\) Par hypothèse d’induction, on a que \(x_2-1=y_2-1=k\text{,}\) donc \(x_2=y_2=k+1\text{.}\)
Par le principe de récurrence, la proposition est vraie.
17.
On considère les chaînes binaires de longueur \(n\text{.}\) On note \(A\) l’ensemble des chaînes binaire de longueur \(n\) qui possèdent un nombre pair de \(0\text{.}\) Similairement, on note \(B\) l’ensemble des chaînes binaire de longueur \(n\) qui possèdent un nombre impair de \(0\text{.}\) Par exemple, si \(n=3\text{,}\) alors \(A=\{111,100,010,001\}\) et \(B=\{000,110,101,011\}\text{.}\) Montrer que \(|A|=|B|\text{.}\)
Solution.
Pour montrer que \(|A|=|B|\text{,}\) on peut montrer qu’il existe une fonction \(f:A\to B\) telle que \(f\) est bijective. Si \(x\in A\) on pose \(f(x)\) la chaîne binaire obtenue en changeant le dernier caractère de la chaîne ( un \(1\) devient un \(0\text{,}\) et un \(0\) devient un \(1\)). Ainsi, si \(x\) possède un nombre pair de \(0\text{,}\) alors \(f(x)\) possède un nombre impair de \(0\text{,}\) car \(f(x)\) en possède un de plus ou un de moins que \(x\text{.}\) On peut définir \(f^{-1}:B\to A\) de la même façon, et on vérifie facilement que \(f(f^{-1}(x))=f^{-1}(f(x))=x\text{.}\) Ainsi, \(f\) est une fonction bijective.
