Remplacer les grands calculs par une structure de restes

Pour a entier et b entier strictement positif, il existe un unique couple (q,r) tel que $\text{a=bq+r}$ et . Dire $\text{a≡r}$ [b] signifie que b divise $\text{a−r}$, donc que a et r ont le même reste modulo b. Cette relation classe les entiers selon un cycle de restes.

Les congruences sont compatibles avec addition, soustraction, multiplication et puissances entières positives. La division n'est pas libre : on ne simplifie par un facteur que sous des conditions sur son inversibilité modulo n. Vérifier quelques restes ne remplace pas une preuve pour tout entier.

Le PGCD de deux entiers non tous nuls est leur plus grand diviseur commun positif. L'algorithme d'Euclide repose sur $\text{pgcd(a,b)=pgcd(b,r)}$, où r est le reste de la division de a par b. Les restes diminuent strictement jusqu'à zéro ; le dernier reste non nul est le PGCD.

L'algorithme fournit une preuve et non une simple recette : remplacer a par $\text{a−bq}$ ne change pas les diviseurs communs. Il est beaucoup plus efficace qu'une liste de tous les diviseurs pour de grands entiers. Chaque division conserve le quotient pour la remontée de Bézout.

Le théorème de Bézout affirme que $\text{pgcd(a,b)=d}$ peut s'écrire $\text{ax+by=d}$ avec x,y entiers. En particulier, a et b sont premiers entre eux si et seulement s'il existe x,y tels que $\text{ax+by=1}$. La remontée de l'algorithme d'Euclide construit ces coefficients.

Le théorème de Gauss dit que si a divise bc et si a est premier avec b, alors a divise c. La condition de coprimalité est essentielle : 6 divise $\text{3×4}$ mais ne divise ni 3 ni 4. Une preuve par Bézout multiplie $\text{ax+by=1}$ par c et utilise les divisibilités.

Un nombre premier est un entier naturel supérieur ou égal à 2 dont les seuls diviseurs positifs sont 1 et lui-même. Tout entier $\text{n≥2}$ se décompose de manière unique, à l'ordre près, en produit de nombres premiers. Cette structure permet de lire divisibilité, PGCD et PPCM sur les exposants.

Pour tester si n est premier, il suffit de chercher un diviseur premier inférieur ou égal à sqrt(n). En effet, si $\text{n=ab}$ avec $\text{a,b>1}$, l'un des deux est au plus sqrt(n). Ne trouver aucun diviseur dans une petite liste arbitraire ne suffit pas ; la borne justifie l'arrêt.

Si p est premier et a n'est pas divisible par p, alors $\text{a⁽p−1⁾≡1}$ [p]. Cette propriété réduit de grands exposants modulo p. Elle donne aussi $\text{a⁽p−2⁾}$ comme inverse de a modulo p. La réciproque générale est fausse : certains nombres composés passent des tests de type Fermat.

Un inverse de a modulo n existe si et seulement si $\text{pgcd(a,n)=1}$. Bézout le construit dans tous les modules ; Fermat offre une méthode particulière quand le module est premier. Une solution de $\text{ax≡b}$ [n] exige que le PGCD soit compatible avec b.

Une équation diophantienne cherche des solutions entières. L'équation $\text{ax+by=c}$ admet des solutions si et seulement si pgcd(a,b) divise c. Une solution particulière issue de Bézout engendre ensuite toutes les solutions en ajoutant des multiples adaptés.

Dans un chiffrement affine modulo n, la transformation $\text{x→ax+b}$ est déchiffrable seulement si a est inversible modulo n, donc si $\text{pgcd(a,n)=1}$. L'exemple apprend les congruences ; il n'offre pas une sécurité moderne. Une application cryptographique réelle exige protocoles, tailles de clé et analyse bien plus avancés.