Divisibilité et congruences en Terminale maths expertes

Divisibilité et congruences en Maths expertes : cours complet

L'arithmétique étudie les entiers : divisibilité, congruences, restes. C'est la base de la cryptographie et de l'informatique théorique.

Divisibilité

Définition

Soit $a,b\in \mathbb{Z}$a, b ∈ ℤ. On dit que $a$a divise $b$b, noté $a|b$a | b, s'il existe $k\in \mathbb{Z}$k ∈ ℤ tel que $b=ak$b = ak.

Propriétés

• $a|a$a | a (réflexive).
• $a|b$a | b et $b|c⟹a|c$b | c ⇒ a | c (transitive).
• $a|b$a | b et $a|c⟹a|(b+c)$a | c ⇒ a | (b + c) et $a|(b-c)$a | (b - c).
• $a|b⟹a|bc$a | b ⇒ a | bc.

Division euclidienne

Théorème

Pour tout $a\in \mathbb{Z}$a ∈ ℤ et $b\in {\mathbb{N}}^{\ast }$b ∈ ℕ^(*), il existe un unique couple $(q,r)$(q, r) tel que :

$$a=bq+r\text{avec}0\le r<b$$a = bq + r avec 0 ≤ r < b

• $q$q : quotient.
• $r$r : reste.

Exemple

$17=5\times 3+2$17 = 5 × 3 + 2 : quotient $3$3, reste $2$2.

Congruences

Définition

Soit $a,b\in \mathbb{Z}$a, b ∈ ℤ et $n\in {\mathbb{N}}^{\ast }$n ∈ ℕ^(*). On dit que $a$a est congru à $b$b modulo $n$n, noté $a\equiv b(\mathrm{mod}n)$a ≡ b pmodn, ssi :

$$n|(a-b)$$n | (a - b)

Équivalent : $a$a et $b$b ont le même reste dans la division par $n$n.

Exemple

$17\equiv 2(\mathrm{mod}5)$17 ≡ 2 pmod5 car $17-2=15=5\times 3$17 - 2 = 15 = 5 × 3.

Propriétés

$$a\equiv b(\mathrm{mod}n)\text{ et }c\equiv d(\mathrm{mod}n)⟹a+c\equiv b+d(\mathrm{mod}n)$$a ≡ b pmodn et c ≡ d pmodn ⇒ a + c ≡ b + d pmodn

$$⟹a-c\equiv b-d(\mathrm{mod}n)$$⇒ a - c ≡ b - d pmodn

$$⟹ac\equiv bd(\mathrm{mod}n)$$⇒ ac ≡ bd pmodn

$$a\equiv b(\mathrm{mod}n)⟹a^k\equiv b^k(\mathrm{mod}n)$$a ≡ b pmodn ⇒ a^(k) ≡ b^(k) pmodn

Application : critères de divisibilité

Divisibilité par $9$9

$$N\equiv \text{somme de ses chiffres}(\mathrm{mod}9)$$N ≡ somme de ses chiffres pmod9

Donc $N$N est divisible par $9$9 ssi la somme de ses chiffres l'est.

Divisibilité par $3$3

Idem que pour $9$9 : somme des chiffres divisible par $3$3.

Divisibilité par $11$11

$$N\equiv \text{somme alterneˊe des chiffres}(\mathrm{mod}11)$$N ≡ somme alternée des chiffres pmod11

Exemple : $1727$1727 → $1-7+2-7=-11\equiv 0$1 - 7 + 2 - 7 = -11 ≡ 0, donc $1727$1727 est divisible par $11$11.

Calculs de restes (modulaire)

Exemple 1

Reste de $7^{100}$7¹⁰⁰ par $5$5 ?

$7\equiv 2(\mathrm{mod}5)$7 ≡ 2 pmod5, donc $7^{100}\equiv 2^{100}(\mathrm{mod}5)$7¹⁰⁰ ≡ 2¹⁰⁰ pmod5.

$2^4=16\equiv 1(\mathrm{mod}5)$2⁴ = 16 ≡ 1 pmod5, donc $2^{100}=(2^4{)}^{25}\equiv 1(\mathrm{mod}5)$2¹⁰⁰ = (2⁴)²⁵ ≡ 1 pmod5.

Reste : $1$1.

Exemple 2

Reste de $5^{1000}$5¹⁰⁰⁰ par $7$7 ?

$5^2=25\equiv 4$5² = 25 ≡ 4, $5^3\equiv 20\equiv 6$5³ ≡ 20 ≡ 6, $5^6=(5^3{)}^2\equiv 36\equiv 1(\mathrm{mod}7)$5⁶ = (5³)² ≡ 36 ≡ 1 pmod7.

$1000=6\times 166+4$1000 = 6 × 166 + 4, donc $5^{1000}\equiv 5^4(\mathrm{mod}7)$5¹⁰⁰⁰ ≡ 5⁴ pmod7.

$5^4=625=7\times 89+2$5⁴ = 625 = 7 × 89 + 2, donc $5^4\equiv 2(\mathrm{mod}7)$5⁴ ≡ 2 pmod7.

Reste : $2$2.

Petit théorème de Fermat (introduction)

Énoncé

Si $p$p est premier et $a$a n'est pas divisible par $p$p :

$$a^{p-1}\equiv 1(\mathrm{mod}p)$$a^(p-1) ≡ 1 pmodp

Conséquence

$$a^p\equiv a(\mathrm{mod}p)\forall a\in \mathbb{Z}$$a^(p) ≡ a pmodp ∀ a ∈ ℤ

Exemple

$2^{10}=1024=11\times 93+1$2¹⁰ = 1024 = 11 × 93 + 1 → $2^{10}\equiv 1(\mathrm{mod}11)$2¹⁰ ≡ 1 pmod11 ✓ (avec $p=11$p = 11).

Tables de congruences

Pour un module $n$n, on peut dresser des tables de multiplication, addition, puissances.

Table d'addition modulo $5$5

Erreurs fréquentes à éviter

• Mauvais signe dans les congruences : $-3\equiv 2(\mathrm{mod}5)$-3 ≡ 2 pmod5, pas $-3\equiv -3(\mathrm{mod}5)$-3 ≡ -3 pmod5 (les deux sont vraies mais on préfère $\ge 0$≥ 0).
• Diviser des congruences : pas toujours possible (sauf si on connaît l'inverse).
• Confondre $a\equiv b(\mathrm{mod}n)$a ≡ b pmod n et $a=b$a = b tout court.
• Mauvais reste dans la division euclidienne.

FAQ — Divisibilité et congruences

Pourquoi étudier l'arithmétique ?

C'est la base théorique de la cryptographie (RSA, courbes elliptiques), de l'informatique, de la théorie des codes.

À quoi servent les congruences ?

Au calcul modulaire : restes de grandes puissances, vérifications, hash, codes correcteurs.

Comment savoir si un nombre est premier ?

On teste sa divisibilité par tous les premiers $\le \sqrt{n}$≤ √(n). (Tests plus efficaces existent : Fermat, Miller-Rabin.)

Le petit théorème de Fermat sert à quoi ?

À simplifier les calculs de puissances modulo un premier, et à construire des tests de primalité.