Tronc commun / Mathématiques / Arithmétique

Arithmétique

Module 1 de l'unité U21. L'arithmétique des entiers est le socle du codage de l'information et de la cryptographie asymétrique.

1. Divisibilité

Soient a et b deux entiers relatifs. On dit que b divise a, noté b | a, s'il existe un entier k tel que a = b × k. On dit alors que a est un multiple de b.

Propriétés utiles :

• Si b | a et c | b, alors c | a (transitivité).
• Si c | a et c | b, alors c divise toute combinaison au + bv.
• Tout entier divise 0 ; 1 divise tout entier.

2. Division euclidienne et PGCD

Pour a entier et b entier non nul, il existe un unique couple (q, r) tel que :

a = b × q + r      avec   0 ≤ r < |b|

q est le quotient, r le reste. En programmation ce sont les opérateurs / (division entière) et % (modulo).

Algorithme d'Euclide

Le PGCD (plus grand commun diviseur) se calcule par divisions successives : on remplace le couple (a, b) par (b, a mod b) jusqu'à obtenir un reste nul.

PGCD(1071, 462) :
  1071 = 462 × 2 + 147
   462 = 147 × 3 +  21
   147 =  21 × 7 +   0   →  PGCD = 21

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Deux entiers sont premiers entre eux si leur PGCD vaut 1. Le PPCM (plus petit commun multiple) s'en déduit : PPCM(a, b) × PGCD(a, b) = |a × b|.

L'algorithme d'Euclide est l'un des plus anciens algorithmes connus, et il reste extrêmement rapide : le nombre d'étapes est de l'ordre du nombre de chiffres des opérandes. C'est un bon exemple à citer en complexité algorithmique.

Théorème de Bézout

Si d = PGCD(a, b), il existe des entiers u et v tels que au + bv = d. L'algorithme d'Euclide étendu fournit ce couple, ce qui sert à calculer un inverse modulaire (voir RSA).

3. Nombres premiers

Un entier p ≥ 2 est premier s'il n'admet que 1 et lui-même comme diviseurs positifs. 2 est le seul nombre premier pair.

Théorème fondamental de l'arithmétique : tout entier ≥ 2 se décompose de manière unique (à l'ordre près) en produit de facteurs premiers.

360 = 2³ × 3² × 5

Test de primalité naïf : il suffit de tester les diviseurs jusqu'à √n, car si n = a × b avec a ≤ b, alors a ≤ √n.

def est_premier(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

4. Congruences

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 se comportent bien avec les opérations :

• si a ≡ b et c ≡ d [n], alors a + c ≡ b + d [n] ;
• et a × c ≡ b × d [n] ;
• donc a^k ≡ b^k [n].

Exemple : quel est le chiffre des unités de 7²⁰²⁴ ? On travaille modulo 10. Les puissances de 7 cyclent : 7, 9, 3, 1, 7, 9, 3, 1… de période 4. Comme 2024 ≡ 0 [4], le résultat est 1.

Applications informatiques : clé de contrôle d'un IBAN ou d'un numéro de sécurité sociale, fonctions de hachage, générateurs pseudo-aléatoires congruentiels, table de hachage (indice = clé % taille).

5. Changements de base

En base b, un nombre s'écrit comme somme de puissances de b. Les bases utiles en informatique sont 2 (binaire), 8 (octal) et 16 (hexadécimal).

Décimal → binaire : divisions successives par 2

On lit les restes de bas en haut : 45 = 101101₂.

Binaire → décimal : somme des puissances

101101₂ = 1×32 + 0×16 + 1×8 + 1×4 + 0×2 + 1×1 = 45

Passage binaire ↔ hexadécimal : on groupe les bits par paquets de 4, ce qui rend la conversion immédiate. 1111 1111 devient FF. C'est la raison pour laquelle l'hexadécimal sert à écrire les adresses MAC, les couleurs CSS et les adresses IPv6.

Les conversions dans tous les sens, les nombres décimaux, l'addition et la soustraction binaires, le complément à deux et les opérations logiques sont détaillés dans la fiche Bases, conversions et calcul binaire.

6. Application : chiffrement RSA

RSA repose entièrement sur cette arithmétique. Le principe, en version simplifiée :

1. Choisir deux grands nombres premiers p et q, puis n = p × q.
2. Calculer φ(n) = (p − 1)(q − 1).
3. Choisir e premier avec φ(n) : c'est la clé publique (n, e).
4. Calculer d, l'inverse de e modulo φ(n), par Euclide étendu : c'est la clé privée.
5. Chiffrer : c = m^e mod n. Déchiffrer : m = c^d mod n.

La sécurité vient d'une asymétrie de difficulté : multiplier p et q est instantané, mais factoriser n pour retrouver p et q est hors de portée quand n fait 2048 bits. Voir la fiche Preuve électronique pour l'usage en sécurité.