SG2 Mathématiques (spé)

Congruences
Professeur : Bou Maroun F.
1/10/2019
Soit n un entier naturel supérieur à 1
On dit que a est congru à b modulo n
S’il existe un entier relatif k tel que a=b+kn
On note a ≣ b [n]
Exemple : 38 ≣ 3[5] car 38=3+7×5
On dit que a est congru à b lorsque a et b ont le même reste
dans la division euclidienne par n.
On note a≣b [n] ou a≣b (mod n)
a≣b [n] signifieque :

 (a-b) est divisible par n

 a et b ont le même reste de la division
euclidienne par n
 Il existe un entier k tel que a =b+kn

Exemple : 31≣ 10 [7]

31-10 = 21 qui est divisible par 7

31 7 10 7 donc 31 et 10 ont le même reste de

la
3 4 3 1 de la division par 7

31 = 10+7×3 il existe l’ entier 3 tel que 31 = 10+7×3

Propriétés :
 a ≣ 0 [n] signifie que « a est divisible par n »

 a≣b [n] équivaut à : n divise a-b

Exemple : 145 ≣119 [13] car 145-119=26=2×13
 a≣0[n] equivaut à :a est un multiple de n
 si a≣b [n] et b≣c[n] alors a≣c[n]
 si a≣b [n] alors ∀ c, a+c ≣ b+c [n]
 si a≣b [n] alors ∀ k, ak ≣ bk [n] avec k ϵ ℤ
 Si a≣b [n] alors ∀ m, aᵐ ≣ bᵐ [n] avec m ϵ ℕ
 Si a≣b [n] alors il existe k tel que a=b+kn

 On peut simplifier des congruences en enlevant des

multiples du module pour obtenir des nombres plus petits.

Exemple : considérons les congruences modulo 4.

 -4 -3 -2 -1 0 1 2 3 4 5 6 ……. 58 59 60 61
62

mod 4: 32
Exemple -3 congru
n à 1 ( on
≣ 2n (5) 1 congru à 56 ×5 )
a enlevé 5 congru à 61

Donc lorsqu’on étudie une congruence modulo n , n est toujours

un entier naturel non nul .Mais on peut étudier tout entier
relatif a modulo n et on peut toujours le rendre congru à un
entier naturel, en ajoutant un multiple de n .
Ainsi -27≣-27+8×4 (8) donc -27≣ 5 (8)

 8 divise n peut se traduire par :

 Il existe q entier tel que n =8q ou encore
 n ≣ 0 ( 8)

 Penser que «  a est divisible par b » équivaut à a≣ 0 (b)

 En général, on n’obtient pas une congruence équivalente en
divisant les deux membres par un même nombre
Exemple :
2 ≣ 14 (mod 4) en divisant par 2 les deux membres, on aurait
tendance à écrire qu’alors 1≣ 7(mod4) mais 7-1 =6 n’est pas un
multiple de 4, donc cette congruence est fausse .
Exercice résolu : Prouvons que 243 ≣ 3 (mod 5)
24 = 16, donc 24 ≣ 1 (mod 5)
Or 243 = 24 × 10+3 , c’est-à-dire 243 = (24)10 × 23
Alors comme 24 ≣1 (mod 5)
 Donc (24)10 ≣ 110 (mod 5)
Et (24)10× 23≣ 110× 23 (mod 5)
Mais 23 = 8 donc (24)10× 23≣ 8 (mod 5)
Par suite (24)10× 23≣ 3 (mod 5)
Donc 243 ≣ 3 (mod 5).
 Quel est le reste dans la division euclidienne de 2341 par 7 ?
On observe les restes dans la division de 23n pour les premières
valeurs de n. (Dans ce type d’exercice on essaie de déterminer un
exposant k tel que xk ≣1 (n))

Puissance 23 232 233 234

de 23
Reste 2 4 1 2

Alors 23≣1 (7) , d’où l’idée de diviser 41 par 3 Or 41+ 3×13+2

Donc 2341 = 233x 13+2 =(233)13× 232
23≣1 (7), =(233)13≣113 (7) , (233)13× 232≣113 × 232 (7)
Mais 232 ≣ 4(7), (233)13× 232≣1 × 4(7) et donc 2341≣4(7)
  Montrer que
si n≥2 a,b,c,d quatre entiers relatifs
et Si a≣b [n] et c≣d [n] alors a+c ≣ b+d [n]
----------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------

 et si a≣b[n] et c≣d[n] alors a×c=b×d [n]

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--

Attention:

 On peut additionner, soustraire et multiplier des congruences

de même module, mais en général on ne peut pas diviser une
congruence par un entier.
27 ≣ 15[12] mais 9 n’est pas congru à 5 modulo 12

 La règle : Un produit est nul si un des facteurs au moins est

nul ne s’applique pas avec les congruences
65≣0[15] mais ni 6 ni 5 n’est congru à 0 mod 15
  Montrer que pour tout ϵ ℕ 5²ⁿ - (-23)ⁿ est divisible par 24
5²ⁿ-(-23)=(5²)ⁿ-(-23)ⁿ donc 5²ⁿ-(-23)ⁿ =25ⁿ -(-23)ⁿ
Or -23≣1[24]
25≣1[24]
Donc 5²ⁿ -(-23)ⁿ ≣ 1ⁿ-1ⁿ [24]
5²ⁿ -(-23)ⁿ≣0 [24]

 Pour quelles valeurs de n

2n²-10n+8 est-il divisible par 5 ?

n=… [5] 0 1 2 3 4
2n²≣..[5] 0 2 3 3 2
-10n+8 =… [5] 3 -2 -2 -2 -2
2n²-10n+8≣ …[5] 3 0 1 1 0

Donc 5 divise 2n²-10n+8

Si n=1+5k
Ou n=4+5k avec k ϵ ℤ

 Trouver suivant les valeurs de n ϵ ℕ le reste de la division

de 4ⁿ par 7
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
 Trouver suivant les valeurs de n les valeurs de n ϵ ℕ, le
reste de la division de A=851³ⁿ + 851ⁿ +2 par 7
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
……………………………………………………………………………………………………
…………………………………………………………………………………………………….
 Montrer que 3²ⁿ - 2ⁿ est divisible par 7 pour tout n ϵ ℕ
……………………………………………………………………………
……………………………………………………………………………
……………………………………………………………………………
……………………………………………………………………………
……………………………………………………………………………
Comment déterminer le reste dans la division euclidienne de aᵇ par n?
 Trouver le reste de la division euclidienne de 599¹²³⁴ par 9.
SAVOIR FAIRE :
- On cherche le reste de 599 de la division euclidienne par 9
- On cherche ensuite le plus petit entier n non nul tel que rⁿ soit congru à
1 modulo 9
- On effectue enfin la division euclidienne de 1234 par n

Division euclidienne de 599 par 9:

599 = 9 x66 + 5
Donc 599 ≡ 5 [9]

Tableau des congruences:

On dresse un tableau des congruences de 5ⁿ modulo 9 selon les valeurs
de l’entier n jusqu’à obtenir 1
N 0 1 2 3 4 5 6

Congruences 1 5 7 8 4 2 1
de 5ⁿ
modulo 9

Le plus petit entier non nul tel que 5ⁿ ≡ 1[9] est 6.

Division euclidienne de 1234 par 6:

1234= 6x205+4
On a 599¹²³⁴≡5¹²³⁴ [9]=(5⁶)²⁰⁵ x5⁴[9]≡1²⁰⁵ x 5⁴[9]= 5⁴[9]
Or d’après le tableau on a 5⁴≡ 4[9]
Le reste de la division euclidienne de 599¹²³⁴ par 9 est 4.
  Montrez que 237¹²⁵¹ -3 est divisible par 3
On prouve que 237¹²⁵¹ -3≡ 0[5]
Division euclidienne de 237 par 5:
237=5x47+2
Donc on obtient 237≡ 2[5]
Ainsi 237¹²⁵¹ -3≡ 2¹²⁵¹ -3[5]

Étude de 2¹²⁵¹ modulo 5:

On étudie les puissances de 2 modulo 5
On dresse un tableau des congruences de 2ⁿ modulo 5 selon les valeurs
de l’entier n jusqu’à obtenir 1
2¹≡ 2[5]
2²≡ 4[5]
2³= 8 ≡ 5+3 ≡ 3[5]
2⁴=16 ≡ 5x3 +1 ≡ 1[5]
N 1 2 3 4

Congruence 2 4 3 1
s de 2ⁿ
modulo 5

Le plus petit entier non nul tel que 2ⁿ = [5] est 4

Division euclidienne de 1251 par 4 :

1251= 4x312 +3
On a 237¹²⁵¹ ≡ 2¹²⁵¹ ≡ 2⁴˟³¹²⁺³ ≡ (2⁴) ³¹² x 2³
Or 2⁴ ≡ 1(5)
237¹²⁵¹ ≡ 1³¹² * 2³(5)
237¹²⁵¹ ≡ 8[5]
237¹²⁵¹ ≡ 3[5]
Donc 237¹²⁵¹ -3 ≡ 2¹²⁵¹ -3 ≡ 3-3 ≡ 0[5]
On conclut que 237¹²⁵¹ -3 est divisible par 5.

 Montrer que 33201981 -5 est divisible par 13

---------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------

 Étudiez la valeur de 2ⁿ modulo 5 en fonction de n.( n entier naturel)

……………………………………………….
………………………………………………………………….
……………………………………………………………………………………………………………
………………………………………………………………………………………………………….
……………….
……………………………………………………………………………………………………………
……………………………………….………………………………………………….
…………………………………………………………………………………
 Pour quelles valeurs de n l’entier A(n) = n3+n2-5n+1 est – il
multiple de 3  ?
……………………………………………………………………………………………………
……………………………………………….
………………………………………………………………….
……………………………………………………………………………………………………
……………………………………………………………………………………………………
…………….……………….
……………………………………………………………………………………………………
……………………………………………….………………………………………………….
………………………………………………………………………………………………..
……………………………………………………………………………………………………
………………….
……………………………………………………………………………………………………
…………………………………………………………………………….
…………………………………….
……………………………………………………………………………………………………
………….
……………………………………………………………………………………………………
….…………………………………………..
……………………………………………………………………………………………………
……………………………………………….……………………….
……………………………………………………………………………………………………
……………………………………………………………………………………………………
…………….
……………………………………………………………………………………………………
……………………………………………………………………………….
……………………………………