2728 est-il divisible par 11 ?

Oui, car 2−7+2−8 = −11 ≡ 0 [11]

Le petit théorème de Fermat affirme que si p premier et p ∤ a :

aᵖ⁻¹ ≡ 1 [p]. Le petit théorème de Fermat : aᵖ⁻¹ ≡ 1 [p] si p est premier et p ne divise pas a.

2728 est-il divisible par 11 ?

Oui, car 2−7+2−8 = −11 ≡ 0 [11]. Critère par 11 : somme alternée 2−7+2−8 = −11 ≡ 0 [11]. Donc 2728 est divisible par 11.

Dans RSA, la clé privée d vérifie :

ed ≡ 1 [φ(n)]. d est l'inverse de e modulo φ(n) : ed ≡ 1 [φ(n)]. C'est ce qui permet le déchiffrement.

4. Par Fermat : 3⁶ ≡ 1 [7]. 100 = 6×16 + 4. Donc 3¹⁰⁰ = (3⁶)¹⁶ × 3⁴ ≡ 1 × 81 ≡ 81 mod 7 = 11×7 + 4, soit 4.

a ≡ b [n] signifie que :

n divise (a − b). a ≡ b [n] ⟺ n | (a−b) ⟺ a et b ont le même reste dans la division par n.

Peut-on simplifier 6 ≡ 12 [6] par 3 pour obtenir 2 ≡ 4 [6] ?

Non, car pgcd(3,6) ≠ 1. On ne peut simplifier ac ≡ bc [n] par c que si pgcd(c,n) = 1. Ici pgcd(3,6) = 3 ≠ 1, c'est interdit. (D'ailleurs 2 ≡ 4 [6] est faux.)

Maths expertes — Arithmétique

Arithmétique : congruences et applications

Q: 17 ≡ ? [5]

2. 17 = 3×5 + 2, donc le reste est 2 : 17 ≡ 2 [5].

Q: Si a ≡ 3 [7] et b ≡ 5 [7], alors ab ≡ ? [7]

1. ab ≡ 3 × 5 = 15 ≡ 1 [7] (car 15 = 2×7 + 1).

Q: Le reste de 2¹⁰ dans la division par 7 est :

2. Par Fermat : 2⁶ ≡ 1 [7]. Donc 2¹⁰ = 2⁶ × 2⁴ ≡ 1 × 16 ≡ 2 [7].

Q: Le critère de divisibilité par 9 repose sur le fait que :

10 ≡ 1 [9]. 10 ≡ 1 [9], donc 10ᵏ ≡ 1 [9]. Un nombre est congru modulo 9 à la somme de ses chiffres.

Congruences modulo n, propriétés, petit théorème de Fermat, applications à la cryptographie

Résumé synthétiqueFiche en 5 sectionsQuiz de 10 questionsGratuit, sans pub

Résumé

Deux entiers a et b sont congrus modulo n (noté a ≡ b [n]) si n divise a − b, autrement dit s'ils ont le même reste dans la division par n. Les congruences sont compatibles avec l'addition et la multiplication : si a ≡ b [n] et c ≡ d [n], alors a + c ≡ b + d [n] et ac ≡ bd [n]. Le petit théorème de Fermat affirme que si p est premier et a non divisible par p, alors aᵖ⁻¹ ≡ 1 [p]. Par exemple, 2⁶ = 64 ≡ 1 [7]. Ces outils sont essentiels en cryptographie : le chiffrement RSA repose sur la difficulté de factoriser le produit de deux grands nombres premiers, et utilise l'arithmétique modulaire pour chiffrer et déchiffrer. Les critères de divisibilité classiques (par 3, 9, 11) se démontrent élégamment avec les congruences.

Articles utiles

Maths

Toutes les formules de maths à connaître en Terminale

Maths

Comment réviser les maths en Terminale : méthode complète

Questions fréquentes

Les points clés à retenir sur Arithmétique : congruences et applications, extraits du quiz de révision.

17 ≡ ? [5]

Réponse : 2

17 = 3×5 + 2, donc le reste est 2 : 17 ≡ 2 [5].

Si a ≡ 3 [7] et b ≡ 5 [7], alors ab ≡ ? [7]

Réponse : 1

ab ≡ 3 × 5 = 15 ≡ 1 [7] (car 15 = 2×7 + 1).

Le reste de 2¹⁰ dans la division par 7 est :

Réponse : 2

Par Fermat : 2⁶ ≡ 1 [7]. Donc 2¹⁰ = 2⁶ × 2⁴ ≡ 1 × 16 ≡ 2 [7].

Le critère de divisibilité par 9 repose sur le fait que :

Réponse : 10 ≡ 1 [9]

10 ≡ 1 [9], donc 10ᵏ ≡ 1 [9]. Un nombre est congru modulo 9 à la somme de ses chiffres.

Résumé

Questions fréquentes

Les points clés à retenir sur Arithmétique : congruences et applications, extraits du quiz de révision.

17 ≡ ? [5]

Réponse : 2

17 = 3×5 + 2, donc le reste est 2 : 17 ≡ 2 [5].

Si a ≡ 3 [7] et b ≡ 5 [7], alors ab ≡ ? [7]

Réponse : 1

ab ≡ 3 × 5 = 15 ≡ 1 [7] (car 15 = 2×7 + 1).

Le reste de 2¹⁰ dans la division par 7 est :

Réponse : 2

Par Fermat : 2⁶ ≡ 1 [7]. Donc 2¹⁰ = 2⁶ × 2⁴ ≡ 1 × 16 ≡ 2 [7].

Le critère de divisibilité par 9 repose sur le fait que :

Réponse : 10 ≡ 1 [9]

10 ≡ 1 [9], donc 10ᵏ ≡ 1 [9]. Un nombre est congru modulo 9 à la somme de ses chiffres.

Arithmétique : congruences et applications

Résumé

Congruences : définition et propriétés

Calculs avec les congruences

Critères de divisibilité

Petit théorème de Fermat

Applications : cryptographie RSA

Quiz - Congruences et applications

Articles utiles

Questions fréquentes

Arithmétique : congruences et applications

Résumé

Congruences : définition et propriétés

Calculs avec les congruences

Critères de divisibilité

Petit théorème de Fermat

Applications : cryptographie RSA

Quiz - Congruences et applications

Articles utiles

Questions fréquentes