L'énoncé
Question 1
Quel est le reste de la division euclidienne de \(6^{10}\) par 11 ? Justifier.
On sait que : \(6^2 = 36= 3\times 11 + 3\)
Ainsi : \(6^2 \equiv 3[11]\) donc d'après les propriétés des congruences :
\(6^{10} \equiv 3^5[11]\)
Or, \(3^5 = 243\) et \(243=22\times 11+1\) donc \(6^{10} \equiv 1[11]\)
Le reste de la division euclidienne de \(6^{10}\) par 11 est donc 1.
On peut également utiliser le petit théorème de Fermat :
11 est un nombre premier, 6 et 11 sont premiers entre eux donc \(6^{11-1} \equiv 1[11]\)
A quoi est congru \(6^2\) modulo 11 ?
\(6^{10} = (6^2)^5\) et \(3^5 \equiv ?[11]\)...
Question 2
Quel est le reste de la division euclidienne de \(6^4\) par 5 ? Justifier.
\(6 \equiv 1[5]\) donc \(6^4 \equiv 1^4[5]\) soit : $6^4\equiv 1[5]$
Le reste de la division euclidienne de \(6^4\) par 5 est donc 1.
Question 3
En déduire que \(6^{40} \equiv 1[11]\) et \(6^{40} \equiv 1[5]\).
Comme \(6^{40} = (6^{10})^4\) et \(6^{40} = (6^4)^{10}\) , alors en utilisant les deux questions précédentes, on a :
\(6^{40} \equiv 1[11]\) et \(6^{40} \equiv 1[5]\).
\(6^{40} = (6^{10})^4 = (6^4)^{10}\)
Question 4
Démontrer que \(6^{40}-1\) est divisible par 55.
D'après les questions précédentes, en utilisant la définition de la congruence, il existe \(k\) et \(k'\) entiers naturels tels que :
\(6^{40}-1=5k=11k'\)
5 et 11 sont premiers entre eux et 5 divise \(11k'\) donc, d'après le théorème de Gauss, 5 divise \(k'\).
Ainsi il existe \(k''\) tel que \(6^{40}-1=11\times 5k''\)
Soit : \(6^{40}-1=55k''\)
Finalement, \(6^{40}-1\) est multiple de 55.
Avez-vous utilisé le théorème de Gauss ? Sinon regardez la vidéo sur ce théorème accessible depuis les prérequis.
11 et 5 sont premiers entre eux, donc \(6^{40}-1\) est divisible par 55.
Question 5
Soit \(x\) et \(y\) deux entiers relatifs.
Montrer que léquation \((E): 65x-40y=1\) na pas de solution.
\(65x-40y=5(13x-8y)\) donc 5 divise \(65x-40y\).
5 ne divise pas 1 donc l'équation \((E)\) n'a pas de solution.
Avez-vous raisonné par l’absurde ? Si il existe un couple solution, alors 5 divise 1 !
Question 6
Montrer que l'équation \((E) 17x-40y=1\) admet au moins une solution.
17 et 40 sont premiers entre eux donc d'après le théorème de Bezout, il existe un couple \((u,v)\) tel que : \(17u+40v=1\)
On pose $x=u$ et $y=-v$. On a donc : \((E) 17x-40y=1\)
\((E)\) admet donc au moins une solution.
17 et 40 sont premiers entre eux, donc…
Question 7
Déterminer à l'aide de l'algorithme d'Euclide un couple d'entiers relatifs solution de l'équation \((E)\).
\(40=17 \times 2 + 6\)
\(17 =6 \times 2 + 5\)
\(6 =5 \times 1 + 1\)
Aisni : \(1 = 6-5\)
\(1 = 6-(17-6\times 2)\)
\(1 = 6\times 3 -17\)
\(1 = -17 + (40-17\times 2)\times 3\)
\(1 = 3 \times 40 - 7\times 17\)
\(1 = -7\times 17 - (-3)\times 40\)
Le couple \((-7,-3)\) est donc solution de \((E)\).
Question 8
Résoudre l'équation \((E)\).
En déduire qu'il existe un unique entier naturel \(x_0\) inférieur à 40 tel que \(17x_0 \equiv 1[40]\).
On a : \(\left\{ \begin{array}{left} 1 = 17(-7)-40(-3) \\ 1 = 17x-40y \end{array}\right. \)
En soustrayant membre à membre, on obtient : \(17(x+7)=40(y+3)\).
Comme 17 et 40 sont premiers entre eux, d'après le théorème de Gauss, 17 divise \(y+3\) et il existe un entier \(k\) tel que \(y+3=17k\)
Ainsi,, \(17(x+7)=40\times 17k\) et \((x+7)=40k\).
Si \((x,y)\) est solution de \((E)\), alors il existe \(k\) tel que : \(\left\{ \begin{array}{left} x+7 = 40k \\ y+3=17k \end{array}\right. \)
Réciproquement, \(17(40k-7)-40(17k-3)=1\)
L'unique entier \(x_0\) inférieur à 40 est obtenu pour \(k=1\), c'est 33.
On a bien : \(17x \equiv 1[40]\)
Pensez à soustraire membre à membre puis à regrouper les facteurs 17 d’une part du signe égal et 40 de l’autre.
Utilisez le théorème de Gauss pour conclure.
\(17(x+7) = 40(y+3)\). Comme 17 et 40 sont premiers entre eux, d’après le théorème de Gauss, 17 divise \(y+3\)et il existe un entier k tel que \(y+3=17k\).
Pour trouver la valeur de \(x\) correspondante, il ne vous reste qu’à remplacer dans l’expression \(17(x+7) = 40(y+3)\)
N’oubliez pas la réciproque ! Une fois le couple trouvé, il faut vérifier qu’il est bien solution de \((E)\).