Cours Équations diophantiennes

Exercice - Congruences

L'énoncé

On se propose de déterminer tous les entiers relatifs $N$ tels que : \(\left\{ \begin{array}{left}N \equiv 5(13) \\N \equiv 1(17)\end{array}\right. \)

Question 1

Vérifier que 239 est solution de ce système.

On a : \(239 = 13 \times 18 + 5\) et  \(239 = 17 \times 14 + 1\)

Donc 239 est solution du système.

239 est solution de ce système si \(\left\{ \begin{array}{left} 239 \equiv 5(13) \\ 239 \equiv 1(17) \end{array}\right. \)
Retrouver dans le cours le lien entre reste dans la division euclidienne et congruences. Voir la vidéo sur les congruences.
Effectuer la division euclidienne de 239 par 13 puis par 17.

Question 2

Soit \(N\) un entier relatif solution de ce système.
Démontrer que \(N\) peut sécrire sous la forme :

\(N=1+17x=5+13y\) où \(x\) et \(y\) sont deux entiers relatifs vérifiant la relation \(17x-13y=4\).

On a : \(N \equiv 5(13)\) donc par définition de la congruence, il existe un entier \(y\) tel que : \(N = 5+13y\)
Pour les mêmes raisons,il existe \(x\) tel que : \(N = 1+17x\).

Finalement : \(N = 1+17x=5+13y\) avec \(17x-13y=4\).

Utiliser la définition de la congruence. En cas de doute, voir la vidéo de rappel dans les prérequis.

Question 3

Résoudre l'équation : \(17x-13y=4\) où \(x\) et \(y\) sont des entiers relatifs.

Le couple \((1,1)\) est une solution particulière de léquation.
Donc, pour tout : \((x,y) \in \mathbb{Z}^2 \):

\( 17x-13y=4 \)

\(\Leftrightarrow 17x-13y=17-13 \)

\(\Leftrightarrow 17(x-1)=13(y-1)\)

Comme 13 et 17 sont premiers entre eux, d'après le théorème de Gauss, 13 divise \((x-1)\).
Ainsi il existe \(k \in \mathbb{Z}\) tel que \(x-1=13k\).

On obtient alors : \(\left\{ \begin{array}{left} 17(x-1) = 13(y-1) \\ 17\times {13k} = 13(y-1) \\ 17k = y-1 \end{array}\right. \)
Donc si \((x,y)\) est solution de \(17x-13y=4\) alors il existe \(k \in \mathbb{Z}\) tel que: \(\left\{ \begin{array}{left} x=1+13k \\ y=1+17k \end{array}\right. \)

Réciproquement, tous les couples \((1+13k,1+17k)\) sont solutions.

Trouver une solution particulière simple.
Un théorème essentiel en arithmétique vous sera utile, il s’agit du théorème de Gauss. Voir le rappel vidéo sur le théorème de Bezout-Gauss et en particulier l'exercice 2.
Le théorème de Gauss ne donne qu’une implication, il ne faut donc pas oublier la réciproque !

Question 4

En déduire qu'il existe un entier relatif \(k\) tel que \(N = 18+221k\).

On sait que \(N = 1+17x\) et que \(x=1+13k\)
Donc : \(N=1+17(1+13k) = 18+221k\)

« EN DEDUIRE » signifie qu’il faut utiliser les questions précédentes !
Utiliser au choix l’expression de $N$ en fonction de \(x\) ou de \(y\).
D’après la question précédente \(N = 17x+1\) et \(x=1+13k \), exprimez donc \(N\) en fonction de \(k\).

Question 5

Démontrer l'équivalence entre \(\left\{ \begin{array}{left} N \equiv 5(13) \\ N \equiv 1(17) \end{array}\right. \) et \(N \equiv 18(221)\)

On a vu que si \(N\) est solution du système, alors \(N=18+221k\) d'où \(N \equiv 18(221)\)

Réciproquement, il existe \(k \in \mathbb{Z}\) tel que : \(N = 18+221k=18+13 \times 17k=5+13+13 \times 17k=5+13(1+17k)\)

On en déduit que \(N \equiv 5(13)\).
De même : \(N = 1+17+13 \times 17k=1+17(1+13k)\) et donc \(N \equiv 1(17)\) .
Ainsi : \(\left\{ \begin{array}{left} N \equiv 5(13) \\ N \equiv 1(17) \end{array}\right. \Leftrightarrow N \equiv 18(221)\)

Pour l’implication, pensez à utiliser les questions précédentes (2 et 4).
La réciproque est plus difficile à obtenir. Pensez à utiliser la division euclidienne, voir la vidéo de rappel sur la divisibilité via les prérequis.
Faire apparaitre les facteurs 13 puis 17 dans l’écriture de \(N : 221=13\times{17}\) et \(18=13+5\).

Question 6

Conclure en donnant les solutions du système.

On a démontré que \(\left\{ \begin{array}{left} N \equiv 5(13) \\ N \equiv 1(17) \end{array}\right. \Leftrightarrow N \equiv 18(221)\).
Les solutions du système sont donc les entiers \(N\) de la forme : \(N=18+221k\), \(k \in \mathbb{Z}\)

Que vous demande-t-on ? Relire le début de l’énoncé de l’exercice et répondre à la question posée.
On vient de démontrer que le système de départ équivaut à une seule équation \(N \equiv 18(221)\) dont les solutions sont…