INFO DV n° 7 TS Spé. Math. 14 mars 2017 Arithmétique
EXERCICE .
1. Démontrons le Th. d Gauss.
Soit a ,b , c des entiers relatifs tels que: PGCD( a , b ) = 1 et a | bc
Montrons que cela implique a | c
Cela sous entend que ( a , b ) ≠ ( 0 , 0 )
Comme on suppose que a et b sont premiers entre eux,
d'après le Th. de Bezout:
Il existe un couple ( u , v ) d'entiers relatifs tels que
a u + b v = 1
Multiplions chaque membre par c , on obtient :
a× cu + bc × v = c
Mais on a supposé aussi que: a | bc .
Or on a également: a | a
D'où a | a × cu + bc × v
c-à-d a | c
On bien montré l'implication.
Conclusion :
Le Th. Gauss est démontré
2. Soit p, q deux entiers naturels premiers entre eux .
Soit a un entier relatif tels que : a ≡ 0 [ p ] et a ≡ 0 [ q ]
Montrons que : a ≡ 0 [ p q ] .
On a a ≡ 0 [ p ] qui se traduit par : Il existe un entier relatif k tel que a = k p
Mais a ≡ 0 [ q ] se traduit par q | a.
c-à-d q | k p
Or PGCD( p , q ) = 1
Alors, d'après le Th. de Gauss, q | k.
c-à-d il existe un entier relatif k ' tels que k = k ' q
Ainsi, en reportant, a = k ' q p
On peut dire: il existe un entier relatif k ' tels que a = k ' p q
c-à-d a ≡ 0 [ p q ]
L'implication est démontrée.
Conclusion : Le résultat est avéré.
Partie B.
On se propose de déterminer l'ensemble S des entiers relatifs n vérifiant le système:
n ≡ 9 [ 17 ]
n ≡ 3 [ 5 ]
1. Recherche d'un élément de S.
On désigne par ( u , v ) un couple d'entiers relatifs tel que 17 u + 5 v = 1
a. Justifier l'existence d'un tel couple ( u , v ).
Algorithme d'Euclide: 17 < 5
17 = 5 × 3 + 2
5 = 2 × 2 + 1
2 = 2 × 1 + 0
Donc PGCD( 17 , 5 ) = 1
D'après le Th de Bezout cité plus haut on peut en déduire
qu'il existe un couple d'entiers relatifs ( u , v ) tel que 17 u + 5 v = 1
Conclusion: L'existence est prouvée.
b. On pose n0 = 3 × 17 u + 9 × 5 v .
Démontrer que n0 appartient à S.
On sait que : 17 u + 5 v = 1 ( 1 )
• ( 1 ) s'écrit: 17 u = 1 − 5 v
Reportons dans n0 = 3 × 17 u + 9 × 5 v .
Il vient : n0 = 3 × ( 1 − 5 v ) + 9 × 5 v
c-à-d n0 = 3 − 3 × 5 v + 9 × 5 v
c-à-d n0 = 3 + 6 × 5 v
Donc: n0 ≡ 3 [ 5 ]
• ( 1 ) s'écrit aussi: 5 v = 1 − 17 u
Reportons dans n0 = 3 × 17 u + 9 × 5 v .
Il vient : n0 = 3 × 17 u + 9 × ( 1 − 17 u )
c-à-d n0 = 3 × 17 u + 9 − 9 × 17 u
c-à-d n0 = 9 − 6 × 17 u
Donc : n0 ≡ 9 [ 17 ]
• Ainsi finalement : n0 ≡ 9 [ 17 ]
et n0 ≡ 3 [ 5 ]
Conclusion : On a n0 qui est bien dans S
c. Donner un exemple d'entier n0 appartenent à S.
Il suffit de trouver deux entiers relatifs u et v qui vérifient
17 u + 5 v = 1 puis de les reporter dans n0 = 3 × 17 u + 9 × 5 v
pour trouver un n0 .
Reprenons l'algorithme d'Euclide:
17 = 5 × 3 + 2
5 = 2 × 2 + 1
Donc 1 = 5 − 2 × 2
Mais 2 = 17 − 5 × 3
D'où 1 = 5 − ( 17 − 5 × 3 ) × 2
c-à-d 1 = − 17 × 2 + 7 × 5
c-à-d 1 = ( − 2 ) × 17 + 5 × 7
Prenons: u = − 2 et v = 7
Alors n0 = 3 × 17 × ( − 2 ) + 9 × 5 × 7
c-à-d n0 = 213
Conclusion: n0 = 213
2. Caractérisation des éléments de S .
a. Soit un entier relatif appartenant à S.
Démontrer que n − n0 ≡ 0 [ 85 ] .
85 = 17 × 5
On a:
• n ≡ 9 [ 17 ] et n0 ≡ 9 [ 17 ]
Donc: n − n0 ≡ 9 − 9 [ 17 ] c-à-d n − n0 ≡ 0 [ 17 ] ( 2 )
• n ≡ 3 [ 5 ] et n0 ≡ 3 [ 5 ]
Donc: n − n0 ≡ 3 − 3 [ 5 ] c-à-d n − n0 ≡ 0 [ 5 ] ( 3 )
Comme PGCD( 17 , 5 ) = 1 , le résultat de la question 2. de la
partie A permet de dire :
n − n0 ≡ 0 [ 17× 5 ]
c-à-d n − n0 ≡ 0 [ 85 ]
Conclusion: On a bien montré que: n dans S implique n − n0 ≡ 0 [ 85 ]
b. En déduire qu'un entier relatif n appartient à S si et seulement
si n peut s'écrire sous la forme : n = 43 + 85 k où k est un entier relatif.
Soit n un entier relatif. On a montré que :
• On a montré que : n dans S ⇒ n − n0 ≡ 0 [ 85 ]
• Montrons que réciproquement: n − n0 ≡ 0 [ 85 ] ⇒ n dans S
n − n0 ≡ 0 [ 85 ] c-à-d n − n0 ≡ 0 [ 17× 5 ]
Cela implique n − n0 ≡ 0 [ 17 ] et n − n0 ≡ 0 [ 5 ]
Or n0 ≡ 9 [ 17 ] et n0 ≡ 3 [ 5 ]
Par somme respectives:
n − n0 + n0 ≡ 9 [ 17 ] et n − n0 + n0 ≡ 3 [ 5 ]
Ainsi : n ≡ 9 [ 17 ] et n ≡ 3 [ 5 ]
c-à-d n est dans S
L'équivalence est avérée.
Montrons la seconde équivalence.
On a vu que n0 = 213 convenait
n dans S ⇔ n − n0 ≡ 0 [ 85 ]
se traduit par: n dans S ⇔ n − 213 ≡ 0 [ 85 ]
c-à-d n dans S ⇔ n ≡ 213 [ 85 ]
Or 213 = 85 × 2 + 43
Donc : n dans S ⇔ n ≡ 43 [ 85 ]
c-à-d
n dans S ⇔ Il existe un entier relatif k tel que n = 43 + 85 k
Conclusion: L'équivalence est avérée.
3. Application:
Zoé sait qu'elle a entre 300 et 400 jetons.
• Si elle fait des tas de 17 jetons, il lui en reste 9.
• Si elle fait des tas de 5 jetons, il lui en reste 3.
Combien a-t-elle de jetons?
REPONSE:
Soit n le nombre de jetons de Zoé.
On a: 300 ≤ n ≤ 400
• Si elle fait des tas de 17 jetons, il lui en reste 9.
Cela se traduit par: le reste de la division de n par 17 est 9.
c-à-d n ≡ 9 [ 17 ]
• Si elle fait des tas de 5 jetons, il lui en reste 3.
Cela se traduit par: le reste de la division de n par 5 est 3.
c-à-d n ≡ 3 [ 5 ]
Ainsi n vérifie n ≡ 9 [ 17 ] et n ≡ 3 [ 5 ]
c-à-d n appartient à S
c-à-d Il existe un entier relatif k tel que n = 43 + 85 k
avec 300 ≤ n ≤ 400
Déterminons k grace à l'encadrement.
300 ≤ 43 + 85 k ≤ 400
c-à-d 300 − 43 ≤ 85 k ≤ 400 − 43
c-à-d 257 ≤ 85 k ≤ 357
c-à-d 257 / 85 ≤ k ≤ 357 / 85
Mais 257 / 85 ≈ 3,02 et 357 / 85 ≈ 4,2
Donc k = 4
Reportons dans n = 43 + 85 k
Il vient : n = 43 + 85 × 4 = 383
Conclusion: Zoé avait 383 jetons.
------------------------------------