Bases de l'arithmétique
Progression
#title: "Bases de l'arithmétique" description: "Divisibilité, PGCD, nombres premiers"
#Arithmétique dans
L'arithmétique est la branche des mathématiques qui étudie les propriétés des nombres entiers. C'est l'une des plus anciennes disciplines mathématiques—les travaux d'Euclide datent de 300 ans avant J.-C.—mais elle reste extraordinairement active aujourd'hui. Son importance pratique est immense : la cryptographie moderne, qui protège vos transactions bancaires et vos communications sur Internet, repose entièrement sur des résultats arithmétiques comme la factorisation des grands nombres ou l'arithmétique modulaire.
#Divisibilité
La relation de divisibilité structure l'ensemble des entiers et permet de caractériser les liens entre les nombres.
#Définition
Soient . On dit que divise , noté , s'il existe un entier tel que :
On dit aussi que :
- est un diviseur de
- est un multiple de
Exemples :
- car
- car (tout entier divise zéro)
- pour tout entier
#Propriétés fondamentales
La divisibilité possède des propriétés algébriques importantes :
-
Réflexivité : pour tout
-
Transitivité : Si et , alors
- Preuve : Si et , alors
-
Combinaisons linéaires : Si et , alors pour tous entiers :
Cette propriété est cruciale pour l'algorithme d'Euclide.
#Division Euclidienne
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 de la division
- est le reste de la division
Exemples :
- → Quotient = 5, Reste = 2
- → Quotient = -6, Reste = 1 (attention au signe !)
L'unicité du couple est essentielle : elle garantit que les opérations arithmétiques sont bien définies.
#PGCD et algorithme d'Euclide
#Plus Grand Commun Diviseur (PGCD)
Le PGCD de deux entiers et , noté ou , est le plus grand entier positif qui divise à la fois et .
Propriétés immédiates :
Lorsque , on dit que et sont premiers entre eux (ou copremiers).
#Algorithme d'Euclide
L'algorithme d'Euclide est une méthode remarquablement efficace pour calculer le PGCD. Il repose sur la propriété fondamentale :
où désigne le reste de la division euclidienne de par .
Calculons gcd(252, 105)
On effectue des divisions euclidiennes successives jusqu'à obtenir un reste nul.
252 = ? × 105 + reste
#Théorème de Bézout
Le théorème de Bézout établit un lien profond entre le PGCD et les combinaisons linéaires.
Théorème : Pour tous entiers et non tous deux nuls, il existe des entiers et (appelés coefficients de Bézout) tels que :
Corollaire important : et sont premiers entre eux si et seulement s'il existe tels que :
Cette caractérisation est fondamentale en cryptographie, notamment pour calculer les inverses modulaires.
#Théorème de Gauss
Théorème (Lemme de Gauss) : Si et si , alors .
Intuition : Si divise un produit mais n'a aucun facteur commun avec l'un des termes, alors tous ses facteurs doivent se trouver dans l'autre terme.
#Explorateur d'arithmétique modulaire
L'outil interactif ci-dessous vous permet d'expérimenter avec l'arithmétique modulaire : calculs de PGCD, coefficients de Bézout, inverses modulaires et exponentiation modulaire.
Explorer l’arithmétique modulaire
Choisissez un module et manipulez les résidus. Visualisez les classes d’équivalence et l’effet des opérations (addition, multiplication, puissances, inverse).
Module
12a
5b
8Puissance de a
3Résultats
- a + b
- 5 + 8 ≡ 1 (mod 12)
- a − b
- 5 − 8 ≡ 9 (mod 12)
- a × b
- 5 × 8 ≡ 4 (mod 12)
- a^3
- 5^3 ≡ 5 (mod 12)
- pgcd(a, n)
- pgcd(5, 12) = 1
- Inverse de a
- 5⁻¹ ≡ 5 (mod 12)
Classes d’équivalence de a
Tous ces entiers sont congrus entre eux modulo 12. Ils appartiennent à la même classe [ 5 ].
Cercle des résidus
#Nombres Premiers
Les nombres premiers sont les « atomes » de l'arithmétique : tous les entiers se construisent à partir d'eux.
#Définition
Un entier naturel est dit premier s'il n'admet exactement que 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. Tout nombre premier supérieur à 2 est impair.
#Infinité des nombres premiers
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 le nombre :
Ce nombre n'est divisible par aucun des (car le reste de la division est toujours 1). Donc soit est premier, soit a un diviseur premier différent de tous les . Dans les deux cas, contradiction. ∎
#Théorème fondamental de l'arithmétique
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 appelée la décomposition en facteurs premiers.
Exemples :
#Applications en cryptographie
La factorisation des grands nombres est un problème difficile : aucun algorithme connu ne permet de factoriser un nombre de 300 chiffres en temps raisonnable. Cette difficulté est exploitée par le système de cryptographie RSA :
- On choisit secrètement deux grands nombres premiers et
- On publie leur produit
- Seul celui qui connaît et peut déchiffrer les messages
La sécurité de vos transactions bancaires repose sur cette asymétrie : multiplier deux nombres premiers est instantané, mais retrouver les facteurs à partir du produit est (presque) impossible en pratique.