Corrigé du devoir

Questions de cours :  

1. Il suffit de vérifier que l'ensemble des multiples de $a$ est stable par addition et passage à l'opposé. Si $s$ et $t$ sont deux entiers, alors $sa-ta=(s-t)a$ est bien un multiple de $a$, d'où le résultat.
2. Le groupe $G$ peut être réduit à $\{0\}=0\mathbb{Z}$. Sinon, il contient un élément non nul, et son opposé. Il contient donc forcément un élément strictement positif. Donc $G\cap \mathbb{N}^*$ est non vide. Notons $a$ le plus petit élément de $G$ strictement positif. Puisque $G$ est un sous-groupe de $\mathbb{Z}$, $a\mathbb{Z}\subset G$. Nous voulons montrer que $G\subset a\mathbb{Z}$. Soit $b$ un élément quelconque de $G$. Effectuons la division euclidienne de $b$ par $a$ : $b=aq+r$, avec $r\in\{0,\ldots,a-1\}$. Or $b$, $aq$ et $r=b-aq$ appartiennent à $G$. Puisque $a$ est le plus petit élément strictement positif de $G$, $r=0$, donc $b=aq\in a\mathbb{Z}$.
3. D'après la question précédente, il suffit de vérifier que l'ensemble proposé est un sous-groupe de $\mathbb{Z}$, non réduit à $\{0\}$.
   $$G=\{ sa+tb ,\;s,t\in\mathbb{Z} \}\;.$$
   Observons que $G$ n'est pas réduit à $\{0\}$ car $a$ et $b$ sont non nuls. Soient $s,s',t,t'$ 4 entiers :
   $$(sa+tb)-(s'a+t'b)=(s-s')a+(t-t')b\in G\;.$$
   Donc $G$ est bien un sous-groupe de $\mathbb{Z}$. Donc $G=d\mathbb{Z}$, où $d$ est le plus petit élément strictement positif de $G$.
4. Soit $k$ un diviseur commun à $a$ et $b$ : $k$ divise tout entier de la forme $sa+tb$, donc tout élément de $G$, en particulier $d$. Donc $d$ est le pgcd de $a$ et $b$.
5. Si $a$ et $b$ sont premiers entre eux, leur pgcd est $1$ et le groupe $G$ de la question 3 est $\mathbb{Z}$ tout entier. Donc il existe deux entiers $s$ et $t$ tels que $sa+tb=1$. Multiplions les deux membres par $c$ : $sac+tbc=c$. Or $a$ divise $ac$ et $bc$, donc $sac+tbc$. D'où le résultat.

Exercice 1 :  

1. La propriété est vraie pour $n=0$ : $a_0=2$ et $b_0=1$. Supposons-la vraie pour $n\in\mathbb{N}$.
   

   $$(2+\sqrt{3})^{n+1} = (2+\sqrt{3})(a_n+b_n\sqrt{3})$$

   $$= (2a_n+3b_n)+(a_n+2b_n)\sqrt{3}\;.$$

   
   Donc la propriété est vraie pour $n+1$, avec :
   $$a_{n+1}=2a_n+3b_n$$   et$$\quad b_{n+1}=a_n+2b_n\;.$$

2. Il suffit d'utiliser les relations de récurrence donnant $a_{n+1}$ et $b_{n+1}$ en fonction de $a_n$ et $b_n$.
   

   $$(2u-v)a_{n+1}+(2v-3u)b_{n+1} = (2u-v)(2a_n+3b_n)+(2v-3u)(a_n+2b_n)$$

   $$= ua_n+vb_n\;.$$

   
   
3. La propriété est vraie pour $n=0$, car $a_0=1$ et $b_0=1$ sont premiers entre eux. Supposons-la vraie pour $n$ : il existe deux entiers $u$ et $v$ tels que $ua_n+vb_n=1$. D'après la question précédente, $(2u-v)a_{n+1}+(2v-3u)b_{n+1}=1$, donc $a_{n+1}$ et $b_{n+1}$ sont premiers entre eux. Donc pour tout $n\in\mathbb{N}$, $a_n$ et $b_n$ sont premiers entre eux.
4. Reprenons la relation donnant $b_{n+1}$ en fonction de $a_n$ et $b_n$ : $b_{n+1}=a_n+2b_n$. Soit $d$ un entier divisant à la fois $b_n$ et $b_{n+1}$. Alors $d$ divise $a_n$. Or le seul diviseur commun de $a_n$ et $b_n$ est $1$, d'après la question précédente. Donc le seul diviseur commun à $b_n$ et $b_{n+1}$ est $1$ : $b_n$ et $b_{n+1}$ sont premiers entre eux.
5. Soit $d$ un diviseur commun à $a_n$ et $b_{n+1}$. Alors $d$ divise $b_{n+1}-a_n= 2b_n$. Or puisque $d$ divise $a_n$, $d$ est premier avec $b_n$, donc $d$ divise $2$, d'après le lemme de Gauss.

Exercice 2 : On pose $a=960$ et $b=528$.

1. $$\begin{array}{lcl\vert lcl} 960&=&528\time 1+432 &48&=&5\tim... ...es 4+ 48&48&=&432-4\times 96\\ 96&=& 48\times 2+0& \end{array}$$
   Le pgcd de $a$ et $b$ est $48$. Le ppcm est leur produit divisé par $48$, soit $10560$.
2. Posons $a'=a/\mathrm{pgcd}(a,b)=20$ et $b'=b/\mathrm{pgcd}(a,b)=11$. Deux entiers $u$ et $v$ vérifient $au+bv=\mathrm{pgcd}(a,b)$ si et seulement si $a'u+b'v=1$. Par l'algorithme d'Euclide, nous avons déterminé deux entiers $u_0=5$ et $v_0=-9$ tels que $au_0+bv_0=\mathrm{pgcd}(a,b)$, soit $a'u_0+b'v_0=1$. Deux entiers $u$ et $v$ vérifient $a'u+b'v=1$ si et seulement si $a'(u-u_0)+b'(v-v_0)=0$. Or $a'$ et $b'$ sont premiers entre eux. Par le lemme de Gauss, $a'$ divise $(v-v_0)$ et $b'$ divise $(u-u_0)$. Donc deux entiers $u$ et $v$ vérifient $a'u+b'v=1$ si et seulement s'il existe un entier $k$ tel que $u=u_0+kb'$ et $v=v_0-ka'$. L'ensemble demandé est donc :
   $$\{ (5+11k,-9-20k) ,\;k\in\mathbb{Z} \}\;.$$

3. On trouve :
   $$a=2^6\times 3\times 5$$   et$$\quad b= 2^4\times 3\times 11\;.$$

4. De la décomposition de $a$ et $b$ en facteurs premiers, on déduit :
   $$\mathrm{pgcd}(a,b)=2^4\times3=48$$   et$$\quad \mathrm{ppcm}(a,b)=2^6\times 3\times 5\times 11=10560\;.$$

Exercice 3 :  

1. Le résultat est vrai pour $n=0$. Il est vrai aussi pour $n=1$, car $8^2=64=63+1\equiv 1\;[21]$. Supposons-le vrai pour $n\in\mathbb{N}$. Alors :
   $$8^{2(n+1)}=8^2 8^{2n}\equiv 1\times 1\equiv 1 \;[21]\;.$$
   Donc pour tout $n\in\mathbb{N}$, $8^{2n}\equiv 1\;[21]$.
2. Observons que pour tout entier $n$ :
   $$2^{4^{n+1}}-2^{4^n}=2^{4^n}\left(2^{4^{n+1}-4^n}-1\right) =2^{4^n}\left(2^{3\times 4^n}-1\right) =2^{4^n}\left(8^{4^n}-1\right)\;.$$
   Or pour $n\geqslant 1$, $8^{4^n}$ est une puissance paire de $8$, qui d'après la question précédente, est congrue à $1$ modulo 21. Donc pour $n\geqslant 1$, $2^{4^{n+1}}\equiv 2^{4^n}\;[21]$. Or $2^4+5=21\equiv 0\;[21]$. Le résultat s'ensuit, par récurrence.
3. On déduit de la première question que :
   $$64^{16^{8^{4^2}}}=8^{2\times 16^{8^{4^2}}}\equiv 1\;[21]\;.$$
   On déduit de la deuxième question que :
   $$2^{16^{8^{4^2}}}=2^{4^{2\times 8^{4^2}}}\equiv -5\;[21]\;.$$
   Or :
   $$64^{16^{8^{4^2}}}=2^{16^{8^{4^2}}} 32^{16^{8^{4^2}}}\;.$$
   Donc le reste de la division par $21$ de $32^{16^{8^{4^2}}}$ est l'entier $r$ compris entre 0 et $20$ tel que $-5r\equiv 1\;[21]$, à savoir $r=4$.

Exercice 4 :  

1. Observons que $18\equiv 4\;[7]$ et $31\equiv 3\;[7]$. Le tableau suivant donne les valeurs de $4x$ quand $x$ parcourt $\mathbb{Z}/7\mathbb{Z}$.
   $$\begin{array}{\vert r\vert ccccccc\vert} \hline x&0&1&2&3&4&5&6\\ \hline 4x&0&4&1&5&2&6&3\\ \hline \end{array}$$
   L'ensemble des solutions de l'équation $18x-31\equiv 0\;[7]$ est l'ensemble des entiers congrus à $6$ modulo $7$.
2. Procédons de même, en observant que $-11\equiv 3\;[7]$.
   $$\begin{array}{\vert r\vert ccccccc\vert} \hline x &0&1&2&3&4... ...x &0&3&6&2&5&1&4\\ 4x^2-3x&0&1&3&6&3&1&0\\ \hline \end{array}$$
   Donc l'ensemble des solutions de l'équation proposée est l'ensemble des entiers congrus à 2 ou à 4 modulo 7.
3. On procède comme dans les questions précédentes, après avoir ramené l'équation proposée à $4x^3+4x^2+4x \equiv 3\;[7]$.
   $$\begin{array}{\vert r\vert ccccccc\vert} \hline x &0&1&2&3&4... ...&1&6&1&6&6\\ 4x^3+4x^2+4x &0&5&0&2&0&4&3\\ \hline \end{array}$$
   L'ensemble des solutions est l'ensemble des entiers congrus à $6$ modulo $7$.