Arithmétique

L'arithmétique ne travaille que sur les entiers, et cette restriction change tout : une division ne tombe plus juste, et c'est précisément le reste qui devient intéressant. Le chapitre est court en outils et long en raisonnements — c'est celui où l'on démontre le plus, avec le moins de calcul.

Divisibilité et division euclidienne

$b$ divise $a$, noté $b \mid a$, s'il existe un entier $k$ tel que $a = kb$.

La division euclidienne de $a$ par $b > 0$ fournit un unique couple $(q;r)$ tel que

L'encadrement du reste fait partie de l'énoncé du théorème : sans lui, l'écriture n'est pas unique, et l'unicité est ce qui donne au reste toute sa valeur. Retenir que $b \mid a \iff r = 0$.

PGCD et algorithme d'Euclide

Le PGCD de $a$ et $b$ est le plus grand entier divisant les deux. Il se calcule sans factoriser, par l'observation suivante :

On itère jusqu'à un reste nul ; le dernier reste non nul est le PGCD. C'est l'algorithme d'Euclide, et son efficacité est remarquable : il traite des nombres de plusieurs centaines de chiffres là où la factorisation échoue.

$a$ et $b$ sont premiers entre eux si $\operatorname{pgcd}(a,b) = 1$. Attention à ne pas confondre avec « nombres premiers » : 8 et 9 sont premiers entre eux sans qu'aucun des deux ne soit premier.

Bézout et Gauss

Théorème de Bézout. $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers $u$ et $v$ tels que

L'équivalence se lit dans les deux sens, et les deux servent. De gauche à droite, elle fournit un couple $(u;v)$ qu'on calcule par l'algorithme d'Euclide remonté. De droite à gauche, elle démontre une primalité relative : exhiber une combinaison égale à 1 suffit, sans calculer le moindre PGCD.

Théorème de Gauss. Si $a \mid bc$ et si $a$ et $b$ sont premiers entre eux, alors $a \mid c$.

L'hypothèse de primalité relative est indispensable : $6 \mid 4 \times 3$ sans que 6 divise ni 4 ni 3. C'est le théorème le plus employé du chapitre, et l'oubli de son hypothèse la faute la plus fréquente.

Nombres premiers

$p \geqslant 2$ est premier s'il n'admet que 1 et lui-même comme diviseurs positifs.

Deux résultats structurent le chapitre. Il existe une infinité de nombres premiers — la démonstration d'Euclide, par l'absurde, tient en trois lignes et tombe régulièrement. Et tout entier $n \geqslant 2$ se décompose de manière unique en produit de facteurs premiers.

De la décomposition se lisent le nombre de diviseurs, le PGCD et le PPCM. Un test de primalité n'exige d'essayer les diviseurs que jusqu'à $\sqrt{n}$ : au-delà, le cofacteur serait plus petit et aurait déjà été trouvé.

Cette relation évite de calculer le PPCM séparément.

Congruences

$a \equiv b \pmod{n}$ signifie que $n$ divise $a - b$, c'est-à-dire que $a$ et $b$ ont le même reste dans la division par $n$.

Les congruences se manipulent comme des égalités pour l'addition, la soustraction, la multiplication et l'élévation à une puissance :

Mais pas pour la division. $6 \equiv 12 \pmod 6$ sans que $1 \equiv 2 \pmod 6$. Simplifier une congruence exige que le facteur soit premier avec le module — c'est encore Gauss.

L'usage principal est de remplacer un calcul par un petit reste. Pour trouver le dernier chiffre de $7^{2024}$, on travaille modulo 10 : $7^1 \equiv 7$, $7^2 \equiv 9$, $7^3 \equiv 3$, $7^4 \equiv 1$, et le cycle recommence. Comme $2024 = 4 \times 506$, on a $7^{2024} \equiv 1 \pmod{10}$ : le dernier chiffre est 1.

Petit théorème de Fermat

Si $p$ est premier et $a$ non divisible par $p$ :

Il réduit instantanément les grands exposants modulo un nombre premier, et fonde le chiffrement RSA — c'est le pont entre ce chapitre et la cryptographie.

Équations diophantiennes

L'équation $ax + by = c$ en entiers admet des solutions si et seulement si $\operatorname{pgcd}(a,b)$ divise $c$. La méthode est fixe :

1. Calculer $d = \operatorname{pgcd}(a,b)$ et vérifier que $d \mid c$ ; sinon, aucune solution.
2. Trouver une solution particulière, par l'algorithme d'Euclide remonté.
3. Écrire la solution générale : $x = x_0 + k\,b/d$ et $y = y_0 - k\,a/d$, $k$ entier.

L'étape 3 mérite attention : les coefficients $b/d$ et $a/d$ sont croisés et de signes opposés. Les intervertir donne une famille qui ne vérifie pas l'équation, ce qu'une vérification sur $k=1$ détecte aussitôt.

À vous

// L'algorithme d'Euclide donne le PGCD. Sa version « étendue » donne en
// prime les coefficients de Bézout, et c'est elle qui résout les équations.

// 1. PGCD par divisions successives.
function pgcd(a, b) {
  while (b !== 0) {
    // à compléter : remplacer (a, b) par (b, reste de a par b)
  }
  return a;
}

// 2. Euclide étendu : trouver u et v tels que a·u + b·v = pgcd(a, b).
function bezout(a, b) {
  if (b === 0) return { d: a, u: 1, v: 0 };
  const { d, u, v } = bezout(b, a % b);
  return { d, u: 0, v: 0 }; // à corriger
}

console.log("pgcd(1071, 462) =", pgcd(1071, 462)); // attendu : 21

const { d, u, v } = bezout(1071, 462);
console.log("d =", d, " u =", u, " v =", v);
console.log("vérification :", 1071 * u + 462 * v, "doit valoir", d);

function pgcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

// Si b·u' + (a mod b)·v' = d, alors en écrivant a mod b = a − ⌊a/b⌋·b
// on obtient a·v' + b·(u' − ⌊a/b⌋·v') = d.
function bezout(a, b) {
  if (b === 0) return { d: a, u: 1, v: 0 };
  const { d, u, v } = bezout(b, a % b);
  return { d, u: v, v: u - Math.floor(a / b) * v };
}

console.log("pgcd(1071, 462) =", pgcd(1071, 462)); // 21

const { d, u, v } = bezout(1071, 462);
console.log("d =", d, " u =", u, " v =", v); // 21, −3, 7
console.log("vérification :", 1071 * u + 462 * v, "doit valoir", d);

// Le couple (u, v) n'est pas unique : (u + k·b/d, v − k·a/d) convient aussi.
// C'est ce qui donne l'infinité de solutions d'une équation diophantienne.

À retenir