Cours Équations diophantiennes
Exercice

L'énoncé

Répondez aux questions suivantes en soignant particulièrement la rédaction.

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]\)

Avez-vous utilisé les congruences modulo 11 ? Puis les propriétés sur les règles de calcul des congruences ? Regardez la vidéo sur les congruences si vous ne les connaissez pas bien.
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.

C’est la même méthode !

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]\).

Connaissez-vous les propriétés des congruences ?
\(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.

D’après les questions précédentes, vous avez trouvé que \(6^{40}-1 \equiv 0[11]\) et \(6^{40}-1 \equiv 0[5]\).
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 factorisé \((E)\) par 5 ?
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.

Avez-vous utilisé le théorème de Bezout ? Si vous ne vous en souvenez pas, regardez la vidéo sur ce théorème et apprenez le par coeur.
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)\).

Connaissez-vous l’algorithme d’Euclide ? Sinon relisez la méthode dans votre cours ou regardez la vidéo sur le PGCD - PPCM, exercice 1.

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]\)

Avez-vous trouvé ce système \(\left\{ \begin{array}{left} 1 = 17(-7)-40(-3) \\ 1 = 17x-40y \end{array}\right. \) ?
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)\).