Aller au contenu
Réussir mon BTS SIO

Tape une notion, une commande ou le nom d'une épreuve.

Par exemple

Exercice 5 / 9Moyen

Calculer des restes modulo n

À toi

  1. Quel est le reste de 1 234 × 5 678 dans la division par 9 ?
  2. Quel est le reste de 3¹⁰⁰ dans la division par 7 ?
  3. Quel est le chiffre des unités de 7²⁰²⁷ ?
  4. Le 1ᵉʳ janvier 2027 est un vendredi. Quel jour de la semaine sera-t-on 100 jours plus tard ?

Arithmétique modulaire et chiffrement

La division euclidienne

Pour a entier naturel et b entier naturel non nul, il existe un unique couple (q, r) tel que a = b × q + r avec 0 ≤ r < b. À la calculatrice, q est la partie entière de a ÷ b, et r = a − b × q (jamais la partie décimale). Exemple : 2 026 = 7 × 289 + 3, avec 0 ≤ 3 < 7. En Python : 2026 // 7 donne 289, 2026 % 7 donne 3.

Nombres premiers et décomposition

Pour savoir si n est premier, on teste les nombres premiers jusqu'à √n. Pour décomposer n, on le divise par le plus petit nombre premier possible, et on recommence avec le quotient jusqu'à 1 :

Nombre36018090451551
Divisé par222335

360 = 2³ × 3² × 5. Un diviseur de 360 s'écrit 2ᵃ × 3ᵇ × 5ᶜ avec a de 0 à 3, b de 0 à 2, c de 0 à 1 : 360 a 4 × 3 × 2 = 24 diviseurs.

Le PGCD par l'algorithme d'Euclide

Si a = b × q + r, alors PGCD(a, b) = PGCD(b, r). On divise, puis le diviseur devient le dividende et le reste devient le diviseur, jusqu'à un reste nul. Le PGCD est le dernier reste non nul.

abDivision euclidienneReste
252180252 = 180 × 1 + 7272
18072180 = 72 × 2 + 3636
723672 = 36 × 2 + 00

PGCD(252, 180) = 36. Deux entiers sont premiers entre eux quand leur PGCD vaut 1.

Les congruences

a ≡ b [n] (« a est congru à b modulo n ») si a − b est un multiple de n, c'est-à-dire si a et b ont le même reste dans la division par n. On peut additionner, multiplier et élever à une puissance des congruences : remplace chaque nombre par son reste le plus tôt possible.

Pour une grande puissance, on cherche une puissance qui vaut 1. Modulo 5 : 2¹ ≡ 2, 2² ≡ 4, 2³ ≡ 3, 2⁴ ≡ 1. Comme 2 026 = 4 × 506 + 2, 2²⁰²⁶ = (2⁴)⁵⁰⁶ × 2² ≡ 4 [5]. Les jours de la semaine reviennent tous les 7 jours : ils se comptent modulo 7.

L'inverse modulo n

a' est l'inverse de a modulo n si a × a' ≡ 1 [n]. Il existe si et seulement si PGCD(a, n) = 1. Pour le trouver modulo 26, cherche parmi 27, 53, 79, 105… (les nombres 1 + 26k) le premier divisible par a : pour a = 7, 105 = 7 × 15, l'inverse de 7 est 15.

Pour résoudre 7x ≡ 3 [26], on multiplie par l'inverse : x ≡ 15 × 3 = 45 ≡ 19 [26]. On ne divise jamais une congruence.

César et chiffrement affine

ABCDEFGHIJKLM
0123456789101112
NOPQRSTUVWXYZ
13141516171819202122232425
  • César de clé k : y ≡ x + k [26] ; on déchiffre avec x ≡ y − k [26]. Après Z, on revient à A.
  • Affine de clé (a, b) : y ≡ ax + b [26], avec PGCD(a, 26) = 1. On déchiffre avec x ≡ a'(y − b) [26], où a' est l'inverse de a.

Exemple avec la clé (7, 3) : R (17) donne 7 × 17 + 3 = 122 = 4 × 26 + 18, soit S. Pour déchiffrer, x ≡ 15(y − 3) = 15y − 45 ≡ 15y + 7 [26].

Casser un chiffrement affine : deux lettres devinées donnent deux congruences. Si E (4) est codé F (5) et T (19) est codé G (6) : 4a + b ≡ 5 et 19a + b ≡ 6. En soustrayant, 15a ≡ 1 [26], donc a = 7 (l'inverse de 15), puis b ≡ 5 − 28 = −23 ≡ 3 [26].

Tes réponses

Jour, 100 jours après le vendredi 1ᵉʳ janvier 2027

Connecte-toi pour faire cet exercice

C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.

Le site garde ton nom et ton email, rien d'autre. Tes données