Arithmétique : les théorèmes fondamentaux

I. Théorème fondamental de l'arithmétique

1) Définition

Ce théorème stipule que tout nombre entier supérieur à 1 peut être écrit comme un produit de nombres premiers de manière unique, à l'ordre près des facteurs. Cela signifie que pour tout entier $n$ supérieur à 1, il existe un ensemble de nombres premiers $p1$, $p2$, ..., $pk$ et des puissances positives $e1$, $e2$, ..., $ek$ tels que $n$ est égal à $p1^{e1} \times p2^{e2} \times ... \times pk^{ek}$, et cette représentation est unique.

2) Démonstration

La démonstration commence par montrer l'existence de cette décomposition, généralement en utilisant une approche constructive. Ensuite, l'unicité est prouvée, souvent par l'absurde, en supposant qu'il existe deux décompositions distinctes et en montrant que cela mène à une contradiction.

3) Applications

Cette propriété est fondamentale en théorie des nombres et a des implications directes en cryptographie, notamment dans la conception d'algorithmes de cryptage et de factorisation.

II. Théorème de Bézout

1) Énoncé

Pour deux entiers $a$ et $b$, non tous deux nuls, il existe des entiers $x$ et $y$ tels que $ax+by$ est égal au plus grand commun diviseur de $a$ et $b$. Cela signifie que le plus grand commun diviseur (PGCD) de $a$ et $b$ peut toujours être exprimé comme une combinaison linéaire de ces nombres.

2) Démonstration

La démonstration s'appuie généralement sur l'algorithme d'Euclide étendu. En utilisant cet algorithme, on trouve les coefficients $x$ et $y$ qui satisfont l'équation.

3) Applications

Essentiel pour le calcul des inverses modulaires et la résolution d'équations diophantiennes.

III. Petit théorème de Fermat

1) Énoncé

Si $p$ est un nombre premier et $a$ est un entier non divisible par $p$, alors $a^{(p-1)}$ est congruent à $1$ modulo $p$.

2) Démonstration

La preuve peut s'appuyer sur des concepts d'algèbre abstraite, notamment l'utilisation de groupes. Une méthode courante est la preuve par induction.

3) Applications

Important en cryptographie et dans les tests de primalité.

IV. Théorème des restes chinois

1) Énoncé

Si $n1$, $n2$, ...,$nk$ sont des entiers positifs qui sont deux à deux premiers entre eux, alors pour tout ensemble d'entiers $a1$, $a2$, ..., $ak$, il existe un entier $x$ tel que pour tout $i$, $x$ est congruent à $ai$ modulo $ni$. De plus, cet $x$ est unique modulo le produit $N=n1$, $n2...nk$.

2) Démonstration

La preuve implique la construction d'un tel $x$ en utilisant des principes d'algèbre modulaire et la démonstration de son unicité.

3) Applications

Utilisé en cryptographie, calcul parallèle et algorithmes de calcul distribué.

Je retiens

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

Tout nombre entier supérieur à 1 se décompose de manière unique en produit de facteurs premiers.

Théorème de Bézout

Le PGCD de deux nombres entiers peut s'exprimer comme une combinaison linéaire de ces nombres.

Petit théorème de Fermat

Pour un nombre premier $p$ et un entier $a$ non divisible par $p$, $a^{(p-1)}$ est congruent à 1 modulo $p$.

Théorème des restes chinois

Permet de résoudre des systèmes de congruences linéaires lorsque les moduli sont deux à deux premiers entre eux.