#Arithmétique dans Copier le lien

L'arithmétique étudie les propriétés des nombres entiers. C'est l'une des plus anciennes disciplines mathématiques : les Éléments d'Euclide datent d'environ 300 ans avant notre ère. Elle reste extraordinairement active et son importance pratique est immense : la cryptographie moderne, qui protège les transactions bancaires et les communications sur Internet, repose sur la factorisation des grands nombres et l'arithmétique modulaire.

#Prérequis et objectifsCopier le lien

Prérequis. La logique du module (quantificateurs, raisonnement par récurrence, contraposée) et le vocabulaire ensembliste de base.

Objectifs. Manipuler la divisibilité et la division euclidienne, calculer un PGCD par l'algorithme d'Euclide, déterminer des coefficients de Bézout, appliquer le théorème de Gauss, décomposer un entier en facteurs premiers et comprendre le principe du chiffrement RSA.

#DivisibilitéCopier le lien

La relation de divisibilité structure l'ensemble des entiers et caractérise les liens entre les nombres.

#DéfinitionCopier le lien

Soient . On dit que divise , noté , s'il existe un entier tel que .

On dit aussi que est un diviseur de et que est un multiple de .

Exemples :

• car ;
• car : tout entier non nul divise zéro ;
• pour tout entier ;
• car .

#Propriétés fondamentalesCopier le lien

1. Réflexivité : pour tout .

2. Transitivité : si et , alors . Preuve : si et , alors . ∎

3. Combinaisons linéaires : si et , alors pour tous :

   Preuve : et donnent . ∎ Cette propriété est cruciale pour l'algorithme d'Euclide et le théorème de Bézout.

4. Divisibilité et valeur absolue : si et , alors . Conséquence : un entier non nul n'a qu'un nombre fini de diviseurs.

#Division euclidienneCopier le lien

La division euclidienne est le fondement de toute l'arithmétique ; elle généralise la division apprise à l'école primaire.

Théorème (division euclidienne). Pour tout et tout , il existe un unique couple d'entiers tel que :

est le quotient et le reste de la division de par .

Idée de l'existence. L'ensemble est non vide (prendre de signe opposé à assez grand en valeur absolue) ; il admet un plus petit élément . Si , alors est encore dans et strictement plus petit : contradiction. Pour l'unicité, deux écritures donnent avec , ce qui force puis . ∎

Exemples :

• : quotient 5, reste 2.
• : quotient , reste 1. Attention au reste négatif : est une égalité vraie mais n'est pas la division euclidienne, car le reste doit vérifier .

L'existence et l'unicité garantissent que le reste est une fonction bien définie : c'est lui qui fonde les congruences du chapitre suivant.

#PGCD et algorithme d'EuclideCopier le lien

#Plus grand commun diviseurCopier le lien

Le PGCD de deux entiers et non tous deux nuls, noté ou , est le plus grand entier positif qui divise à la fois et (l'ensemble des diviseurs communs étant fini et non vide, ce plus grand élément existe).

Propriétés immédiates :

• ;
• ;
• si (avec ), .

Lorsque , on dit que et sont premiers entre eux (ou copremiers).

#Algorithme d'EuclideCopier le lien

L'algorithme repose sur la propriété fondamentale : si est la division euclidienne de par , alors :

Preuve : les diviseurs communs de et sont exactement ceux de et . En effet, si et , alors par combinaison linéaire ; réciproquement, si et , alors . Mêmes diviseurs communs, donc même PGCD. ∎

La suite des restes est strictement décroissante et à valeurs dans : l'algorithme termine toujours. Le pire cas est atteint par deux Fibonacci consécutifs ( demande exactement divisions): le nombre d'étapes grandit comme avec , soit moins de divisions par chiffre décimal (théorème de Lamé). Complexité logarithmique : c'est ce qui rend l'algorithme d'Euclide utilisable sur des nombres de milliers de chiffres.

#Théorème de BézoutCopier le lien

Théorème. Pour tous entiers et non tous deux nuls, il existe des entiers et (les coefficients de Bézout) tels que :

Corollaire fondamental : et sont premiers entre eux si et seulement s'il existe tels que .

Calcul pratique (Euclide étendu). On remonte l'algorithme d'Euclide en exprimant chaque reste par combinaison linéaire. Avec :

D'où .

Vérification : , , et .

Cette caractérisation est fondamentale en cryptographie : calculer l'inverse modulaire de modulo revient à trouver tel que .

#Théorème de GaussCopier le lien

Théorème (lemme de Gauss). Si et , alors .

Démonstration. Par Bézout, il existe avec . En multipliant par : . Or divise et (car ) ; par combinaison linéaire, . ∎

Intuition : si divise un produit mais n'a aucun facteur commun avec l'un des termes, tous ses facteurs doivent se trouver dans l'autre terme.

Application classique : résoudre dans . On ne peut pas « diviser par 3 » sans précaution ; on écrit , et l'équation après simplification par 3 n'a pas de solution car 5 est impair. La forme opératoire : exige avec et , de sorte que reste à résoudre, sans solution entière.

#Explorateur d'arithmétique modulaireCopier le lien

L'outil interactif ci-dessous permet d'expérimenter avec l'arithmétique modulaire : calculs de PGCD, coefficients de Bézout, inverses modulaires et exponentiation modulaire.

#Nombres premiersCopier le lien

Les nombres premiers sont les « atomes » de l'arithmétique : tous les entiers se construisent à partir d'eux.

#DéfinitionCopier le lien

Un entier naturel est premier s'il admet exactement deux diviseurs positifs : 1 et lui-même.

Les premiers nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...

Remarque : 2 est le seul nombre premier pair ; 1 n'est pas premier (un seul diviseur positif) ; 0 n'est ni premier ni l'inverse d'un premier.

Critère de primalité utile. Un entier est premier si et seulement s'il n'admet aucun diviseur premier . En effet, si avec , alors . Test sur : , on essaie 2, 3, 5, 7 ; or : non premier. Test sur : aucun des premiers (2, 3, 5, 7) ne divise 97 : premier.

#Infinité des nombres premiersCopier le lien

Théorème (Euclide). L'ensemble des nombres premiers est infini.

Démonstration par l'absurde. Supposons qu'il n'existe qu'un nombre fini de premiers . Considérons :

Ce nombre n'est divisible par aucun des : la division de par laisse toujours un reste égal à 1. Or tout entier possède au moins un diviseur premier. Ce diviseur est donc un premier différent de tous les : contradiction avec l'exhaustivité de la liste. ∎

#Théorème fondamental de l'arithmétiqueCopier le lien

Théorème. Tout entier s'écrit de manière unique (à l'ordre des facteurs près) comme produit de nombres premiers :

où les sont des nombres premiers distincts et les des entiers strictement positifs. Cette écriture est la décomposition en facteurs premiers.

Idée des deux preuves. Existence : par récurrence forte sur ; si est premier, fini ; sinon avec , et on applique l'hypothèse de récurrence à et . Unicité : si , alors divise le membre de droite ; par le lemme de Gauss itéré, divise l'un des , donc lui est égal ; on simplifie et on itère. ∎

Exemples :

• (vérification : )

Application au PGCD et au PPCM. Avec les décompositions et (en autorisant les exposants nuls) :

d'où l'identité . Exemple avec et : , , et .

#Crible d'ÉratosthèneCopier le lien

Pour dresser la liste des premiers jusqu'à : écrire les entiers de 2 à , entourer 2 puis barrer ses multiples, entourer le premier non barré suivant (3) et barrer ses multiples, etc., en s'arrêtant à . Les non barrés sont premiers. Complexité : opérations ; c'est le crible le plus simple et reste un standard pour des jusqu'à plusieurs milliards.

#Applications en cryptographieCopier le lien

La factorisation des grands nombres est un problème difficile : aucun algorithme classique connu ne factorise en temps raisonnable un produit de deux premiers de plusieurs centaines de chiffres (le meilleur algorithme général, le crible algébrique, est sous-exponentiel). Cette difficulté est exploitée par le système RSA :

1. On choisit secrètement deux grands nombres premiers et ;
2. On publie leur produit ;
3. Seul celui qui connaît et peut déchiffrer les messages.

La sécurité repose sur cette asymétrie : multiplier deux premiers est instantané, retrouver les facteurs à partir du produit est infaisable en pratique avec les moyens actuels. Les détails complets (exposants, inverses modulo ) sont traités dans la section sur les congruences.

#Exercices type d'examenCopier le lien

Exercice 1 (Euclide étendu). Calculer puis déterminer des coefficients de Bézout.

Correction. Divisions successives :

Dernier reste non nul : . Remontée : , donne ; avec : ; avec : .

Vérification : , , différence . Et , : cohérent.

Exercice 2 (équation diophantienne). Résoudre dans l'équation .

Correction. Une solution existe car divise 21 (condition de Bézout). Solution particulière déjà obtenue : . Solution générale : si est solution, , soit ; comme , le lemme de Gauss donne et pour :

Vérification pour : . Pour : .

Exercice 3 (Gauss). Montrer que si est tel que , alors .

Correction. Contraposée : supposons . Alors ou . Dans le premier cas , de reste 1 ; dans le second , de reste 1. Dans les deux cas . ∎

Variante par Gauss directement : est premier et divise ; s'il ne divise pas , il est premier avec , donc par le lemme de Gauss il diviserait : contradiction. Ce schéma généralise à tout premier , résultat central pour l'unicité de la décomposition en facteurs premiers.