Remplacer les grands calculs par une structure de restes

Ce que tu vas savoir faire

• Calculer et interpréter une division euclidienne.
• Calculer avec des congruences.
• Obtenir PGCD et coefficients de Bézout.
• Utiliser les théorèmes de Bézout et Gauss.
• Raisonner avec nombres premiers et Fermat.
• Résoudre une équation diophantienne et un chiffrement simple.

Vérifie tes prérequis

• Suivre la spécialité mathématiques en Terminale.
• Maîtriser calcul algébrique, fonctions, vecteurs et probabilités.

1. Division euclidienne et congruences

Pour a entier et b entier strictement positif, il existe un unique couple (q,r) tel que a=bq+r et 0≤r<b. Dire a≡r [b] signifie que b divise 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.

2. PGCD et algorithme d'Euclide

Le PGCD de deux entiers non tous nuls est leur plus grand diviseur commun positif. L'algorithme d'Euclide repose sur 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 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.

3. Bézout et Gauss : passer du PGCD à une preuve

Le théorème de Bézout affirme que pgcd(a,b)=d peut s'écrire 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 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 3×4 mais ne divise ni 3 ni 4. Une preuve par Bézout multiplie ax+by=1 par c et utilise les divisibilités.

4. Nombres premiers et décomposition unique

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 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 n=ab avec 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.

5. Petit théorème de Fermat et inverses modulaires

Si p est premier et a n'est pas divisible par p, alors a⁽p−1⁾≡1 [p]. Cette propriété réduit de grands exposants modulo p. Elle donne aussi 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 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 ax≡b [n] exige que le PGCD soit compatible avec b.

6. Equations diophantiennes et chiffrement affine

Une équation diophantienne cherche des solutions entières. L'équation 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 x→ax+b est déchiffrable seulement si a est inversible modulo n, donc si 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.

Erreurs fréquentes

L'essentiel à mémoriser

• Une congruence compare des restes ; simplifier exige un inverse ou une condition de coprimalité.
• Euclide remplace un couple par un couple plus petit sans changer ses diviseurs communs.
• Bézout transforme la coprimalité en combinaison linéaire ; Gauss en déduit une divisibilité.
• La borne sqrt(n) transforme un test fini en preuve de primalité.
• Fermat réduit les puissances modulo un nombre premier ; il ne suffit pas seul à certifier toute primalité.
• Une équation entière et un chiffrement affine se résolvent par le PGCD et l'inversibilité modulaire.

Vérifier sa compréhension

Réponds aux 8 questions. Ton score et les réponses justes ou fausses apparaissent immédiatement.

Réviser au bon moment

Révèle chaque réponse, puis indique la difficulté de ton rappel pour programmer la prochaine révision dans ce navigateur.

Poursuivre le parcours

Sources et traçabilité

Dernière vérification : 2026-08-15

1. Programme de mathématiques expertes de Terminale générale, Ministère de l'Éducation nationale, consulté le 2026-08-15.
2. Programmes et ressources en mathématiques, voie GT, Éduscol, consulté le 2026-08-15.