On a successivement :
4 2 ≡
16 [7]
≡
2 [7]
4 4 ≡
4 [7]
4 8 ≡
16 [7]
≡
2 [7]
4 10 ≡ 4 8 × 4 2 [7]
≡
4 [7]
d’où
u n+1 ≡ 4[7].
H n+1 est donc vraie.
• En conclusion, on a u n ≡ 4[7] pour tout n ∈ N ∗ .
Comme 0 4 7 − 1, 4 est le reste de la division euclidienne de u n
par 7.
Pour passer de la congruence au reste il faut vérifier l’encadrement
0 4 7 − 1.
En effet, on a par exemple également u n ≡ −3[7] mais −3 n’en est pas pour
autant le reste de la division, vu qu’il ne vérifie pas cet encadrement.
Exercice 11.3 : Équation diophantienne (MPSI)
1. Déterminer l’entier d = pgcd(495,147) et deux entiers relatifs u et v tels que
147u + 495v = d.
2. Déterminer un couple (x 0 ,y 0 ) ∈ Z 2 tel que 147x 0 + 495y 0 = 12 .
3. En déduire tous les couples (x,y) ∈ Z 2 tels que 147x + 495y = 12.
1. Le pgcd peut être calculé par l’algorithme d’Euclide. Mieux encore : les calculs
que nous ferons pourront être réutilisés afin de déterminer les entiers u et v.
Il est bien plus efficace d’utiliser cet algorithme pour calculer un pgcd que de déterminer les décompositions en facteurs premiers ; le fait qu’il nous permette ensuite
de déterminer les coefficients de la relation de Bézout est une raison de plus pour
l’utiliser sans hésiter.
256
Partie 3 • Algèbre
9782100547678-Fresl-C11.qxd 5/07/10 8:49 Page 256
4 2 ≡
16 [7]
≡
2 [7]
4 4 ≡
4 [7]
4 8 ≡
16 [7]
≡
2 [7]
4 10 ≡ 4 8 × 4 2 [7]
≡
4 [7]
d’où
u n+1 ≡ 4[7].
H n+1 est donc vraie.
• En conclusion, on a u n ≡ 4[7] pour tout n ∈ N ∗ .
Comme 0 4 7 − 1, 4 est le reste de la division euclidienne de u n
par 7.
Pour passer de la congruence au reste il faut vérifier l’encadrement
0 4 7 − 1.
En effet, on a par exemple également u n ≡ −3[7] mais −3 n’en est pas pour
autant le reste de la division, vu qu’il ne vérifie pas cet encadrement.
Exercice 11.3 : Équation diophantienne (MPSI)
1. Déterminer l’entier d = pgcd(495,147) et deux entiers relatifs u et v tels que
147u + 495v = d.
2. Déterminer un couple (x 0 ,y 0 ) ∈ Z 2 tel que 147x 0 + 495y 0 = 12 .
3. En déduire tous les couples (x,y) ∈ Z 2 tels que 147x + 495y = 12.
1. Le pgcd peut être calculé par l’algorithme d’Euclide. Mieux encore : les calculs
que nous ferons pourront être réutilisés afin de déterminer les entiers u et v.
Il est bien plus efficace d’utiliser cet algorithme pour calculer un pgcd que de déterminer les décompositions en facteurs premiers ; le fait qu’il nous permette ensuite
de déterminer les coefficients de la relation de Bézout est une raison de plus pour
l’utiliser sans hésiter.
256
Partie 3 • Algèbre
9782100547678-Fresl-C11.qxd 5/07/10 8:49 Page 256