Utilisation des congruences. TS Spé maths janvier 2016
EXERCICE 1
Déterminer le reste de la division euclidienne de 14123 par 3.
---------------------------------------------------------------------------------------------------------
REPONSE:
Si vous prenez votre calculatrice il y aura "ERR:OVERFLOW",
c'est-à-dire un dépassement de capacité.
Nous allons procéder en plusieurs étapes.
1. Nous allons nous occuper d'abord du 14.
Regardons, d'abord , s'il est possible de trouver un plus petit entier naturel
non nul k tel que 14 k ≡ 1 [ 3 ]
Testons pour cela les premiers entiers naturels non nuls:
• 141 ≡ 2 [ 3 ] car 14 = 2 + 3 x 4
• Ainsi : 14 2 ≡ 22 [ 3 ] c-à-d 14 2 ≡ 4 [ 3 ] Mais 14 = 1 + 3
Donc 14 2 ≡ 1 [ 3 ]
L'entier naturel non nul le plus petit qui convient est k = 2.
2 . Ecrivons à présent la division euclidienne de 123 par k = 2.
On a : 123 = 2 x 61 + 1 avec 0 ≤ 1 < 2
Le reste de la division euclidienne de 123 par 2 est 1.
3. Synthétisons nos deux observations.
On a vu d'abord que: 14 2 ≡ 1 [ 3 ]
On va essayer de faire apparaître en exposant de 14 le 123
Ainsi ( 14 2 ) 61 ≡ 161 [ 3 ]
c-à-d 14 2 x 61 ≡ 1 [ 3 ]
Donc : 14 2 x 61 x 14 ≡ 1 x 14 [ 3 ]
c-à-d 14 2 x 61+1 ≡ 14 [ 3 ]
c-à-d 14 2 x 61+1 ≡ 2 [ 3 ] avec 0 ≤ 2 < 3
c-à-d 14123 ≡ 2 [ 3 ] avec 0 ≤ 2 < 3
Nous pouvons conclure:
Conclusion : Le reste de la division de 14123 par 3 est 2.
On a pu obtenir ce reste sans même calculer 14 123 .
grace aux propriétés des congruences et à la division euclidienne.
--------------------------------------------------------------------------------------------------