# Arithmétique élémentaire

L’arithmétique élémentaire regroupe les rudiments de la connaissance des nombres telle qu'elle est présentée dans l'enseignement des mathématiques. Elle commence avec la comptine numérique, autrement dit la suite des premiers entiers à partir de 1, apprise comme une liste ou une récitation et utilisée pour dénombrer de petites quantités. Viennent ensuite les opérations d'addition et de multiplication par le biais des tables d'addition et de multiplication. Ces opérations permettent, dans le cadre de l'algèbre, de définir leurs opérations réciproques : la soustraction et la division. Ce savoir n'est pas couvert par cet article.
L'apprentissage des tables de multiplication conduit ensuite à la reconnaissance des critères de divisibilité par 2, par 3, par 5, par 9 et par 10, puis à la décomposition des entiers en facteurs premiers. L'unicité de cette décomposition permet la définition du plus grand commun diviseur (pgcd) et du plus petit commun multiple (ppcm). La division euclidienne est utilisée dans l'algorithme d'Euclide pour calculer le pgcd de deux nombres sans connaître leur décomposition en facteurs premiers.
Un premier niveau de savoir se dégage, avec quelques lemmes et théorèmes clés, comme le lemme d'Euclide, l'identité de Bézout et le théorème fondamental de l'arithmétique. Il suffit à démontrer quelques résultats comme le petit théorème de Fermat, celui de Wilson et quelques équations peuvent être résolues. Les équations en question sont dites diophantiennes, c'est-à-dire qu'elles sont à coefficients entiers et les solutions recherchées sont entières. L'identité de Brahmagupta permet de trouver une solution à l'équation X$^2$ – 83Y$^2$ = 1 dès le VIe siècle. Ces méthodes permettent encore à Euler, un mathématicien suisse du XVIIIe siècle, de résoudre l'équation X$^2$ + Y$^2$ = p, qui correspond au théorème des deux carrés de Fermat, ici p désigne un nombre premier. Ce sont ces méthodes, couramment considérées comme de l'arithmétique élémentaire, qui sont exposées dans cet article.
Comprendre plus profondément l'arithmétique des nombres entiers impose l'usage de structures abstraites, comme celles des groupes finis, par exemple dans le cadre de l'arithmétique modulaire, ou des anneaux. On quitte alors l'arithmétique élémentaire pour entrer dans la théorie algébrique des nombres.

## Division euclidienne
### Théorème de la division

L'ensemble étudié dans cet article, noté ℤ, est celui des nombres entiers, qu'ils soient positifs ou négatifs. L'existence de nombres négatifs offre un avantage trop puissant pour que l'on puisse aisément s'en passer. Initialement, il introduit une petite complexité, comment définir la division euclidienne sur ℤ ? Il est nécessaire de modifier un peu le résultat déjà connu pour les entiers positifs.
Division euclidienne pour les nombres entiers — Soit a et b deux nombres entiers tel que b soit non nul. Il existe au moins un couple d'entiers (q, r) tel que a soit égal à b.q + r et tel que r soit en valeur absolue strictement plus petit que b.
Par rapport à la division euclidienne dans les nombres entiers positifs, une propriété a été perdue, l'unicité de la solution n'est maintenant plus toujours vraie. Considérons l'entier 10 que l'on souhaite diviser par 3, il peut s'écrire de deux manières : 3×3 + 1 ou encore 3×4 + (–2). Autoriser les nombres négatifs, en particulier pour le reste, impose d'admettre deux solutions au lieu d'une, ce qui s'avère n'être que peu gênant. La démonstration de ce résultat est proposée dans l'article détaillé.

### Sous-ensembles stables

L'objectif de ce paragraphe est la recherche des sous-ensembles de ℤ qui sont à la fois non vides et stables pour l'addition et la soustraction. Cette démarche, consistant à étudier la structure de l'ensemble ℤ, est une des idées fondatrices de l'arithmétique au sens moderne du terme. Dans un contexte plus sophistiqué, ces sous-ensembles peuvent être vus comme des sous-groupes ou des idéaux. L'usage de ces concepts s'avère néanmoins inutile pour une étude qui se limite à l'arithmétique élémentaire.
Sous-ensembles stables — Soit M un sous-ensemble non vide de ℤ et stable pour l'addition et la soustraction, il existe un entier positif d tel que M soit égal à l'ensemble des multiples de d.
Si M est l'ensemble {0}, c'est bien un ensemble de multiples : ceux de l'entier 0.
Si M n'est pas réduit à l'ensemble {0}, il contient un élément a ainsi que son opposé –a. Autrement dit il contient un élément strictement positif. Soit d le plus petit élément strictement positif de M. On souhaite montrer que M est égal à l'ensemble des multiples de d.
* Tout multiple de d est élément de M : On remarque d'abord que 0 = 0.d est élément de M, en effet, d – d est élément de M car M est stable par soustraction. Soit ad un multiple de d, si a est strictement positif, ad peut être vu comme la somme de d : d + d + … + d répétée a fois, la stabilité de l'addition montre que ad est bien élément de M. Si a est strictement négatif, comme |a|d est élément de M, la stabilité de la soustraction montre que ad, égal à 0 – (|a|d), est encore élément de M, ce qui termine cette démonstration.
* Tout élément de M est un multiple de d : Soit b un élément de M, considérons la division euclidienne de b par d :$b=q\times d+r$Par soustraction, à la fois r et –r sont éléments de M, or l'un de ces deux entiers est positif. Il est non seulement positif mais aussi strictement plus petit que d, ce qui, par définition de d, montre que r est égal à 0. autrement dit, b est bien un multiple de d car égal à qd.
Ces deux propositions montrent bien que M est l'ensemble des multiples de d.

## Théorème fondamental de l'arithmétique
### Théorème de Bachet-Bézout

Une identité permet de venir à bout de toute équation diophantienne du premier degré. Une forme faible de l'identité est la suivante :
Identité de Bachet-Bézout — Deux nombres entiers a et b sont premiers entre eux si, et seulement si, il existe deux entiers m et n tel que :
$a\times m+b\times n=1\;$
Cette forme de l'identité de Bachet-Bézout peut paraître plus faible que celle de l'article détaillé et cela à deux titres. Tout d'abord, elle ne traite que du cas où a et b sont premiers entre eux (mais cela permet de traiter le cas de deux nombres quelconques en les divisant par leur pgcd), ensuite l'article détaillé donne une méthode effective pour trouver les valeurs de m et n, ce qui n'est pas le propos de ce paragraphe.
Si $a\times m+b\times n=1\;$ alors tout diviseur commun à a et b divise également 1, si bien que a et b n'ont que deux diviseurs communs : 1 et -1. Ils sont donc premiers en eux.
Pour la réciproque, on peut remarquer que l'ensemble M des nombres de la forme am + bn, si m et n décrivent tous les entiers, est non vide et stable pour l'addition et la soustraction. La proposition précédente montre l'existence d'un entier positif d tel que M soit l'ensemble des multiples de d. Si a et b sont premiers entre eux, l'entier d, qui divise a et b car ce sont des éléments de M, est nécessairement égal à 1. Or d est multiple de lui-même, donc appartient à M. Ainsi, M contient 1, ce qui montre l'existence d'une solution à l'identité.

### Lemme d'Euclide

Une application importante de l'identité du dernier paragraphe est le lemme d'Euclide :
Lemme d'Euclide — Si un nombre premier p divise un produit a.b de deux nombres entiers, il divise soit a soit b.
Ce lemme fait apparaître des nombres essentiels en arithmétique, les nombres premiers. Ce sont des nombres strictement positifs qui n'ont comme diviseurs positifs qu'eux-mêmes et 1. Le mathématicien Paul Erdős disaient d'eux : « Un nombre premier est un nombre qui ne se casse pas quand on le laisse tomber par terre. ». Ce lemme est une étape pour démontrer le théorème fondamental de l'arithmétique.
Sa démonstration fait appel à l'identité précédente et est démontrée dans l'article détaillé.

### Théorème fondamental de l'arithmétique

Si l'on considère un entier quelconque, on peut l'écrire sous la forme ε.a, où ε désigne soit 1 où –1 et a un nombre entier positif. Si a n'est pas premier, il se décompose en un produit c.b de nombres entiers positifs, opération que l'on peut recommencer. On finit par trouver une décomposition en facteurs premiers :
Théorème fondamental de l'arithmétique — Un nombre entier se décompose de manière unique en un produit comportant un terme ε égal à 1 ou –1 et les autres facteurs sont des nombres premiers.
Ce théorème est le résultat clé de l'arithmétique élémentaire, démontré dans l'article détaillé. Sous une forme plus ou moins générale, il est à la base de nombreux résultats qui se démontrent à l'aide de l'arithmétique élémentaire. En conséquence, la connaissance des nombres premiers s'avère essentielle. Cette connaissance est parfois difficile : leur répartition, par exemple, est en 2011 encore l'objet d'une des plus célèbres conjectures mathématiques (voir l'article hypothèse de Riemann qui dépasse de loin le cadre de l'arithmétique élémentaire). On dispose néanmoins aisément d'un premier résultat :
Nombre de nombres premiers — Il existe une infinité de nombres premiers.
Pour s'en rendre compte, il suffit de considérer un ensemble fini F de nombres premiers et de montrer que cet ensemble ne les contient pas tous. Soit m la somme de 1 et du produit de tous les nombres de F. L'entier m n'est divisible par aucun élément de F, soit il est premier, soit il est divisible par un nombre premier qui n'est pas dans la liste. En conséquence F ne contient pas tous les nombres premiers. Dire qu'aucun ensemble fini ne contient tous les nombres premiers, c'est dire qu'il en existe une infinité (cf. Théorème d'Euclide sur les nombres premiers).

## Conséquences directes
### Théorème de Wilson

Un exemple de résultat d'arithmétique qui peut se démontrer à l'aide des théorèmes énoncés dans cet article est maintenant appelé théorème de Wilson. Il a été démontré par le mathématicien arabe du Xe siècle Alhazen. Il s'énonce ainsi :
Théorème de Wilson — Un entier p > 1 est premier si et seulement s'il divise (p – 1) ! + 1, c'est-à-dire si et seulement si :
$(p-1)!+1\equiv 0{\pmod {p}}.$

### Petit théorème de Fermat

Pierre de Fermat est un mathématicien français du XVIIe siècle que s'est passionné pour l'arithmétique. Le bagage mathématique disponible à son époque était, en arithmétique, plutôt plus faible que celui présenté ici, car l'usage des nombres négatifs était encore problématique. Il a établi le résultat suivant :
Petit théorème de Fermat — Si a est un entier non divisible par p tel que p est un nombre premier, alors a$^{p–1}$ – 1 est un multiple de p.
L'article détaillé présente une démonstration uniquement à l'aide des outils étudiés dans le cadre de cet article. Par delà l'élégance du résultat, il sert aussi de théorème pour démontrer d'autres résultats d'arithmétiques. Il est utilisé, par exemple pour une démonstration élémentaire du théorème des deux carrés de Fermat. Ce résultat stipule que si p est un nombre premier ayant pour reste 1 s'il est divisé par 4, alors l'équation X$^2$ + Y$^2$ = p admet toujours une solution.

### Test de primalité

Le petit théorème de Fermat est à la base de nombreux tests de primalité. Pour en comprendre le principe appliquons sa forme naïve au cinquième nombre de Fermat, noté F$_5$ et égal à 2$^{32}$ + 1, ou encore à 4 294 967 297. Fermat a toujours cru que ce nombre était premier, il écrit « ... je n'ai pu encore démontrer nécessairement la vérité de cette proposition ». C'est la seule conjecture fausse que Fermat a émise.
La méthode simple et brutale consiste à calculer le reste de la division de a$^{(F5–1)}$ – 1 par F$_5$. Si le reste n'est pas nul, le nombre n'est pas premier. Avec deux astuces, les calculs sont beaucoup plus simples qu'il n'y paraît, choisissons a égal à 3. Son carré donne a$^2$, égal à 9. Le carré de ce nombre donne 3$^{22}$, égal à 81, son carré est égal à 3$^{23}$ soit 6 561. Comme F$_5$ – 1 est égal à 2$^{32}$, il suffit de 32 étapes pour conclure, ce qui est maintenant rapide avec les méthodes de calcul modernes.
La deuxième difficulté à résoudre est le caractère élevé des puissances successives, on finirait par devoir utiliser de très grands nombres qui imposent une écriture lourde des valeurs intermédiaires, ainsi 3$^{25}$ est égal à 1 853 020 188 851 841, alors que ce n'est que la cinquième valeur intermédiaire et qu'il faut en calculer 32. Il est néanmoins possible d'écrire ce nombre habilement, à l'aide d'une division euclidienne :
$3^{32}=1\;853\;020\;188\;851\;841=43\;1439\times F_{5}+3\;793\;201\;458=Q_{5}\times F_{5}+R_{5}$
Ce qui importe, c'est le reste de la division euclidienne de 3$^{(F5–1)}$ – 1 et non pas la valeur de Q$_5$. Ainsi, à l'étape d'après :
$3^{64}=(Q_{5}\times F_{5}+R_{5})^{2}=F_{5}\times (Q_{5}^{2}\times F_{5}+2\times Q_{5}\times R_{5})+R_{5}^{2}$
Il suffit de calculer le carré de R$_5$ et d'opérer une division euclidienne de ce carré par F$_5$ et on obtient :
$3^{64}=Q_{6}\times F_{5}+R_{6}\quad {\text{avec}}\quad R_{6}=1\;461\;798\;105$
Le calcul de Q$_6$, et en règle générale de Q$_n$ où n est un entier qui va jusqu'à 32, est inutile. De plus, la suite des R$_n$ ne dépasse jamais F$_5$, ce qui empêche une explosion de chiffres significatifs à calculer. En 32 étapes, on trouve que le reste de la division euclidienne de 3$^{(F5–1)}$ – 1 par F$_5$ est égal à 3 029 026 159 et non pas 0, le nombre F$_5$ n'est pas premier. Euler utilise une méthode plus habile, elle exhibe effectivement les diviseurs, sa méthode est exposée dans l'article Nombre de Fermat.

## Généralisations
### Anneau euclidien

Les questions d'arithmétiques sur les entiers s'avèrent rapidement complexes, Gauss, un mathématicien du XIXe siècle, indiquait : « Leurs charmes particuliers vient de la simplicité des énoncés jointe à la difficulté des preuves. ». D'autres idées sont nécessaires pour aller plus loin. Une méthode consiste à construire de nouveaux ensembles. Cette méthode est illustrée dans l'article Théorème des deux carrés de Fermat. Pour résoudre l'équation X$^2$ + Y$^2$ dans ℤ, on ne cherche cette fois plus les solutions dans ℤ, mais dans l'ensemble des nombres de la forme a + ib, où a et b sont des entiers et i l'unité imaginaire. Un élément de cet ensemble porte le nom d'entier de Gauss.
Un des charmes de cet ensemble est qu'il existe encore une division euclidienne. Les démonstrations des résultats énoncés dans cet article s'appliquent presque sans modification au nouvel ensemble. Les nombres premiers, cette fois sont un peu différents, 2 n'est pas premier car (1 + i)(1 – i) est égal à 2, en revanche, 1 + i l'est. La résolution de l'équation y est beaucoup plus facile.
L'anneau des entiers de ℚ(√5), l'ensemble des nombres de la forme a + b(1 + √5)/2, où a et b sont des entiers, est également euclidien. Il permet de démontrer la loi d'apparition des nombres premiers dans la suite de Fibonacci.
Cette logique permet aussi de construire une arithmétique des polynômes, à l'origine de résolutions d'équations algébriques complexes, comme l'équation cyclotomique.

### Arithmétique modulaire

Une autre idée essentielle consiste encore à créer de nouveaux ensembles de nombres, mais cette fois en s'y prenant différemment. Les nombres sont les restes d'une division euclidienne par un entier, souvent choisi premier. Les éléments de ce nouvel ensemble portent le nom de congruence sur les entiers. L'usage de cet ensemble est en filigrane dans le test de primalité recherché. Il permet de démontrer simplement la généralisation d'Euler du petit théorème de Fermat, et par la même occasion introduit la fonction indicatrice d'Euler, qui joue un rôle important en arithmétique.
Un exemple de résultat arithmétique obtenu avec ce type de méthode est la loi de réciprocité quadratique qui permet de résoudre des équations diophantiennes comme X$^2$ + pY + n = 0, où p est un nombre premier et n un entier.