Aller au contenu
Réussir mon BTS SIO

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

Par exemple

Exercice 4 / 9Moyen

Des kits identiques avec le PGCD

À toi

Le service informatique du laboratoire GSB a reçu 336 clés USB chiffrées et 252 badges d'accès. Il veut préparer des kits identiques, le plus grand nombre possible, en utilisant toutes les clés et tous les badges.

  1. Combien de kits peut-il préparer ?
  2. Combien de clés et combien de badges y aura-t-il dans chaque kit ?
  3. Les nombres 35 et 64 sont-ils premiers entre eux ?

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

35 et 64 sont-ils premiers entre eux ?

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