Arithmétique

En arithmétique, nous travaillons principalement avec l'ensemble des entiers relatifs, noté $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$.

Définition d'un diviseur et d'un multiple

Soient $a$ et $b$ deux entiers relatifs. On dit que $b$ divise $a$ s'il existe un entier $k$ tel que $a = b \times k$. Dans ce cas, $b$ est un diviseur de $a$, et $a$ est un multiple de $b$. On note parfois $b | a$.

Exemple : 3 divise 12 car $12 = 3 \times 4$. Donc 3 est un diviseur de 12, et 12 est un multiple de 3. Attention : 0 est un multiple de tout entier ($0 = b \times 0$), mais 0 ne divise que 0. Tout entier non nul divise 0.

Propriétés de la divisibilité

Voici quelques propriétés importantes :

• Si $a | b$ et $b | c$, alors $a | c$ (transitivité).
• Si $a | b$ et $a | c$, alors $a | (b+c)$ et $a | (b-c)$. Plus généralement, $a | (nb+mc)$ pour tous entiers $n, m$.
• Si $a | b$, alors $|a| \le |b|$ (si $b \ne 0$).
• Tout entier $a$ non nul est divisible par 1, -1, $a$ et $-a$. Ces diviseurs sont appelés diviseurs triviaux.
• Si $a | b$ et $b | a$, alors $a = b$ ou $a = -b$.

Nombres premiers

Un nombre premier est un entier naturel supérieur à 1 qui n'admet que deux diviseurs positifs distincts : 1 et lui-même. Exemples : 2, 3, 5, 7, 11, 13, 17, 19, 23... Le nombre 1 n'est pas premier car il n'a qu'un seul diviseur positif (lui-même). Le nombre 2 est le seul nombre premier pair.

Théorème de la division euclidienne

Pour tous entiers relatifs $a$ (le dividende) et $b$ (le diviseur) avec $b \ne 0$, il existe un unique couple d'entiers relatifs $(q, r)$ tel que : $a = bq + r \quad \text{avec} \quad 0 \le r < |b|$ où $q$ est le quotient et $r$ est le reste de la division euclidienne de $a$ par $b$.

Exemple : Division de 25 par 4. $25 = 4 \times 6 + 1$. Ici, $a=25$, $b=4$, $q=6$, $r=1$. On a bien $0 \le 1 < 4$. Exemple : Division de -25 par 4. $-25 = 4 \times (-7) + 3$. Ici, $a=-25$, $b=4$, $q=-7$, $r=3$. On a bien $0 \le 3 < 4$. Attention : Le reste doit toujours être positif ou nul.

Applications de la division euclidienne

La division euclidienne est fondamentale en arithmétique. Elle permet notamment de :

• Déterminer si un nombre est pair ou impair : Un entier $n$ est pair si $n = 2q + 0$ (le reste est 0), et impair si $n = 2q + 1$ (le reste est 1).
• Catégoriser les entiers selon leur reste dans une division : Par exemple, les entiers peuvent être de la forme $3k$, $3k+1$ ou $3k+2$.
• Démontrer des propriétés sur les nombres. Par exemple, montrer que le carré d'un entier impair est de la forme $8k+1$. Si $n$ est impair, $n = 2q+1$. $n^2 = (2q+1)^2 = 4q^2 + 4q + 1 = 4q(q+1) + 1$. Comme $q(q+1)$ est toujours pair (produit de deux entiers consécutifs), on peut écrire $q(q+1) = 2k'$ pour un certain entier $k'$. Donc $n^2 = 4(2k') + 1 = 8k' + 1$.

Définition et propriétés des congruences

Soit $n$ un entier naturel non nul. On dit que $a$ est congru à $b$ modulo $n$, noté $a \equiv b \pmod{n}$, si $a$ et $b$ ont le même reste dans la division euclidienne par $n$. De manière équivalente, $a \equiv b \pmod{n}$ si et seulement si $n$ divise $(a-b)$. C'est-à-dire, $a-b = kn$ pour un certain entier $k$.

Exemple : $17 \equiv 3 \pmod{7}$ car $17 = 7 \times 2 + 3$ et $3 = 7 \times 0 + 3$. Ou encore $17-3 = 14$, et 14 est un multiple de 7. Exemple : $-5 \equiv 2 \pmod{7}$ car $-5 = 7 \times (-1) + 2$.

Les congruences ont des propriétés similaires à celles de l'égalité :

• Réflexivité : $a \equiv a \pmod{n}$.
• Symétrie : Si $a \equiv b \pmod{n}$, alors $b \equiv a \pmod{n}$.
• Transitivité : Si $a \equiv b \pmod{n}$ et $b \equiv c \pmod{n}$, alors $a \equiv c \pmod{n}$.

Calculs avec les congruences

Les congruences sont très utiles pour simplifier les calculs, surtout avec de grands nombres. Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors :

• $a+c \equiv b+d \pmod{n}$ (compatibilité avec l'addition).
• $a-c \equiv b-d \pmod{n}$ (compatibilité avec la soustraction).
• $ac \equiv bd \pmod{n}$ (compatibilité avec la multiplication).
• $a^k \equiv b^k \pmod{n}$ pour tout entier naturel $k \ge 0$ (compatibilité avec les puissances).

Attention : La division n'est pas toujours compatible avec les congruences. Par exemple, $10 \equiv 4 \pmod{6}$ mais en divisant par 2, $5 \not\equiv 2 \pmod{6}$.

Exemple de calcul : Quel est le reste de $3^{100}$ dans la division par 7 ? $3^1 \equiv 3 \pmod{7}$ $3^2 \equiv 9 \equiv 2 \pmod{7}$ $3^3 \equiv 3^2 \times 3 \equiv 2 \times 3 \equiv 6 \equiv -1 \pmod{7}$ $3^6 \equiv (3^3)^2 \equiv (-1)^2 \equiv 1 \pmod{7}$ On utilise le fait que $100 = 6 \times 16 + 4$. $3^{100} = 3^{6 \times 16 + 4} = (3^6)^{16} \times 3^4 \pmod{7}$ $3^{100} \equiv 1^{16} \times 3^4 \pmod{7}$ $3^{100} \equiv 1 \times (3^2)^2 \equiv 1 \times 2^2 \equiv 4 \pmod{7}$. Le reste est 4.

Critères de divisibilité

Les congruences permettent de justifier les critères de divisibilité que vous connaissez :

• Divisibilité par 3 (ou 9) : Un nombre est divisible par 3 (ou 9) si la somme de ses chiffres est divisible par 3 (ou 9). Explication : Tout nombre $N = d_k...d_1d_0$ peut s'écrire $N = \sum_{i=0}^k d_i 10^i$. Or $10 \equiv 1 \pmod{3}$ (et $\pmod{9}$). Donc $10^i \equiv 1^i \equiv 1 \pmod{3}$ (et $\pmod{9}$). Ainsi, $N \equiv \sum_{i=0}^k d_i \times 1 \equiv \sum_{i=0}^k d_i \pmod{3}$ (et $\pmod{9}$). Donc $N$ est divisible par 3 (ou 9) si et seulement si la somme de ses chiffres est divisible par 3 (ou 9).
• Divisibilité par 11 : Un nombre est divisible par 11 si la somme alternée de ses chiffres est divisible par 11. Explication : $10 \equiv -1 \pmod{11}$. Donc $10^i \equiv (-1)^i \pmod{11}$. $N = d_k...d_1d_0 = d_k 10^k + ... + d_1 10^1 + d_0 10^0$. $N \equiv d_k (-1)^k + ... - d_1 + d_0 \pmod{11}$.

Définition du PGCD

Soient $a$ et $b$ deux entiers relatifs non tous les deux nuls. Le Plus Grand Commun Diviseur de $a$ et $b$, noté $\text{PGCD}(a, b)$, est le plus grand des diviseurs communs positifs de $a$ et $b$. Par convention, $\text{PGCD}(a, 0) = |a|$ pour tout $a \ne 0$. $\text{PGCD}(0,0)$ n'est pas défini.

Exemple : Diviseurs de 12 : $\{1, 2, 3, 4, 6, 12\}$ Diviseurs de 18 : $\{1, 2, 3, 6, 9, 18\}$ Les diviseurs communs sont $\{1, 2, 3, 6\}$. Le plus grand est 6. Donc $\text{PGCD}(12, 18) = 6$.

Propriétés du PGCD

• $\text{PGCD}(a, b) = \text{PGCD}(b, a)$ (commutativité).
• $\text{PGCD}(a, b) = \text{PGCD}(|a|, |b|)$. On peut toujours travailler avec des entiers positifs.
• $\text{PGCD}(a, b) = \text{PGCD}(a-b, b)$. Plus généralement, $\text{PGCD}(a, b) = \text{PGCD}(a-kb, b)$ pour tout entier $k$. Cette propriété est la base de l'algorithme d'Euclide.
• Si $d = \text{PGCD}(a, b)$, alors $d$ est divisible par tout autre diviseur commun de $a$ et $b$.
• Si $k$ est un entier positif, alors $\text{PGCD}(ka, kb) = k \times \text{PGCD}(a, b)$.
• $\text{PGCD}(a, b) = d \iff$ il existe $a', b'$ entiers tels que $a = da'$, $b = db'$ et $\text{PGCD}(a', b') = 1$. (Les nombres $a'$ et $b'$ sont premiers entre eux).

Calcul du PGCD par liste de diviseurs

Cette méthode est efficace pour de petits nombres.

1. Lister tous les diviseurs positifs de $a$.
2. Lister tous les diviseurs positifs de $b$.
3. Identifier les diviseurs communs.
4. Le plus grand de ces diviseurs communs est le PGCD.

Exemple : $\text{PGCD}(30, 42)$ Diviseurs de 30 : $\{1, 2, 3, 5, 6, 10, 15, 30\}$ Diviseurs de 42 : $\{1, 2, 3, 6, 7, 14, 21, 42\}$ Diviseurs communs : $\{1, 2, 3, 6\}$. Donc $\text{PGCD}(30, 42) = 6$.

Principe de l'algorithme d'Euclide

L'algorithme d'Euclide est une méthode efficace pour calculer le PGCD de deux entiers. Il est basé sur la propriété suivante : Pour $a, b$ entiers avec $b \ne 0$, si $a = bq + r$, alors $\text{PGCD}(a, b) = \text{PGCD}(b, r)$. L'algorithme consiste à appliquer cette propriété de manière répétée :

1. Diviser $a$ par $b$ pour obtenir un reste $r_1$.
2. Si $r_1 = 0$, alors $\text{PGCD}(a, b) = b$.
3. Sinon, on recommence avec $b$ et $r_1$. Diviser $b$ par $r_1$ pour obtenir un reste $r_2$.
4. Continuer jusqu'à obtenir un reste nul. Le PGCD est le dernier reste non nul.

Mise en œuvre pour le calcul du PGCD

Exemple : Calculons $\text{PGCD}(1071, 1029)$ $1071 = 1029 \times 1 + 42$ $\text{PGCD}(1071, 1029) = \text{PGCD}(1029, 42)$

$1029 = 42 \times 24 + 21$ $\text{PGCD}(1029, 42) = \text{PGCD}(42, 21)$

$42 = 21 \times 2 + 0$ $\text{PGCD}(42, 21) = \text{PGCD}(21, 0) = 21$.

Donc $\text{PGCD}(1071, 1029) = 21$.

Démonstration de l'algorithme

La preuve repose sur le fait que l'ensemble des diviseurs communs de $(a, b)$ est identique à l'ensemble des diviseurs communs de $(b, r)$ lorsque $a=bq+r$. Soit $d$ un diviseur commun de $a$ et $b$. Alors $d|a$ et $d|b$. Puisque $r = a - bq$, $d$ divise aussi $r$ (propriété de la divisibilité). Donc $d$ est un diviseur commun de $b$ et $r$. Inversement, soit $d'$ un diviseur commun de $b$ et $r$. Alors $d'|b$ et $d'|r$. Puisque $a = bq + r$, $d'$ divise aussi $a$. Donc $d'$ est un diviseur commun de $a$ et $b$. Ainsi, l'ensemble des diviseurs communs est le même, et par conséquent, le plus grand de ces diviseurs est aussi le même. Le PGCD est conservé à chaque étape. Le dernier reste non nul est le PGCD car il divise le reste précédent (qui est un multiple de lui-même) et le reste nul.

Énoncé du théorème de Bézout

Soient $a$ et $b$ deux entiers relatifs non nuls. Il existe des entiers relatifs $u$ et $v$ tels que $au + bv = \text{PGCD}(a, b)$. Cette relation est appelée identité de Bézout.

Exemple : $\text{PGCD}(12, 18) = 6$. On peut trouver $u, v$ tels que $12u + 18v = 6$. Par exemple, $12 \times (-1) + 18 \times 1 = -12 + 18 = 6$. Donc $u=-1, v=1$ est une solution. Il existe une infinité de couples $(u,v)$ solutions.

Coefficients de Bézout

Les entiers $u$ et $v$ sont appelés coefficients de Bézout. On peut les trouver en "remontant" l'algorithme d'Euclide.

Exemple : Reprenons $\text{PGCD}(1071, 1029) = 21$. Les étapes de l'algorithme d'Euclide étaient :

1. $1071 = 1029 \times 1 + 42 \implies 42 = 1071 - 1029 \times 1$
2. $1029 = 42 \times 24 + 21 \implies 21 = 1029 - 42 \times 24$

On part de la dernière ligne où le PGCD apparaît : $21 = 1029 - 42 \times 24$ Maintenant, on remplace 42 par son expression de la ligne 1 : $21 = 1029 - (1071 - 1029 \times 1) \times 24$ $21 = 1029 - 1071 \times 24 + 1029 \times 1 \times 24$ $21 = 1029 \times (1 + 24) - 1071 \times 24$ $21 = 1029 \times 25 + 1071 \times (-24)$ Donc, $u=-24$ et $v=25$ sont des coefficients de Bézout pour $1071u + 1029v = 21$.

Application à la résolution d'équations

Le théorème de Bézout est crucial pour déterminer l'existence de solutions pour les équations diophantiennes linéaires (voir section dédiée plus bas). Une équation de la forme $ax + by = c$ a des solutions entières $(x,y)$ si et seulement si $\text{PGCD}(a,b)$ divise $c$.

Définition

Deux entiers relatifs $a$ et $b$ sont dits premiers entre eux si leur plus grand commun diviseur est 1. $\text{PGCD}(a, b) = 1$.

Exemple : $\text{PGCD}(15, 28) = 1$. Donc 15 et 28 sont premiers entre eux. Exemple : $\text{PGCD}(12, 18) = 6 \ne 1$. Donc 12 et 18 ne sont pas premiers entre eux.

Propriétés des nombres premiers entre eux

• Si $a$ et $b$ sont premiers entre eux, alors il existe des entiers $u, v$ tels que $au + bv = 1$ (c'est une conséquence directe du théorème de Bézout). Cette propriété est souvent utilisée comme définition alternative.
• Si $p$ est un nombre premier et $a$ un entier, alors soit $p | a$, soit $\text{PGCD}(p, a) = 1$.
• Si $a$ est premier avec $b$, et $a$ est premier avec $c$, alors $a$ est premier avec $bc$.
• Si $a | bc$ et $\text{PGCD}(a, b) = 1$, alors $a | c$ (c'est le théorème de Gauss que nous verrons plus loin).

Lien avec le théorème de Bézout

Le théorème de Bézout établit une équivalence fondamentale : $a$ et $b$ sont premiers entre eux $\iff$ il existe des entiers $u, v$ tels que $au + bv = 1$. Ceci est une condition nécessaire et suffisante pour que $a$ et $b$ soient premiers entre eux.

Définition du PPCM

Soient $a$ et $b$ deux entiers relatifs non nuls. Le Plus Petit Commun Multiple de $a$ et $b$, noté $\text{PPCM}(a, b)$, est le plus petit entier naturel non nul qui est un multiple de $a$ et de $b$.

Exemple : Multiples de 12 (positifs) : $\{12, 24, 36, 48, 60, ...\}$ Multiples de 18 (positifs) : $\{18, 36, 54, 72, ...\}$ Les multiples communs sont $\{36, 72, ...\}$. Le plus petit est 36. Donc $\text{PPCM}(12, 18) = 36$.

Relation entre PGCD et PPCM

Pour tous entiers naturels non nuls $a$ et $b$, on a la relation fondamentale : $\text{PGCD}(a, b) \times \text{PPCM}(a, b) = |a \times b|$ Cette propriété est très utile car elle permet de calculer l'un si l'on connaît l'autre.

Exemple : $\text{PGCD}(12, 18) = 6$. $\text{PPCM}(12, 18) = \frac{12 \times 18}{\text{PGCD}(12, 18)} = \frac{216}{6} = 36$. Cela correspond bien à notre calcul précédent.

Calcul du PPCM

1. Par la relation avec le PGCD : C'est souvent la méthode la plus simple, surtout si le PGCD est déjà calculé (par l'algorithme d'Euclide). $\text{PPCM}(a, b) = \frac{|a \times b|}{\text{PGCD}(a, b)}$.
2. Par décomposition en facteurs premiers : (Nous verrons cette méthode en détail plus tard) Pour $\text{PPCM}(12, 18)$ : $12 = 2^2 \times 3^1$ $18 = 2^1 \times 3^2$ On prend chaque facteur premier avec son exposant le plus élevé : $2^{\max(2,1)} \times 3^{\max(1,2)} = 2^2 \times 3^2 = 4 \times 9 = 36$.

Énoncé du théorème de Gauss

Soient $a, b, c$ des entiers relatifs non nuls. Si $a$ divise le produit $bc$ et si $a$ est premier avec $b$ (c'est-à-dire $\text{PGCD}(a, b) = 1$), alors $a$ divise $c$. ==Si $a | bc$ et $\text{PGCD}(a, b) = 1$, alors $a | c$.==

Exemple : On sait que $6 | (3 \times 4)$, c'est-à-dire $6 | 12$. Mais $\text{PGCD}(6, 3) = 3 \ne 1$. Gauss ne s'applique pas. Et effectivement, 6 ne divise pas 4. Par contre, si on prend $a=6, b=5, c=12$. $6 | (5 \times 12)$, c'est-à-dire $6 | 60$. Et $\text{PGCD}(6, 5) = 1$. Alors, d'après Gauss, $6 | 12$. Ce qui est vrai.

Démonstration du théorème

Puisque $\text{PGCD}(a, b) = 1$, d'après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que $au + bv = 1$. Multiplions cette égalité par $c$ : $auc + bvc = c$ On sait que $a | bc$ (hypothèse). Donc $bc = ka$ pour un certain entier $k$. Substituons $bc$ dans l'équation : $auc + (ka)v = c$ $a(uc + kv) = c$ Puisque $(uc + kv)$ est un entier, cette égalité montre que $a$ divise $c$.

Applications du théorème de Gauss

• Simplification de fractions : Si $a|c$ et $b|d$, alors $\frac{a}{b} = \frac{c}{d}$ implique $ad=bc$. Si $\text{PGCD}(a,b)=1$, alors $a|c$ et $b|d$.
• Démonstrations d'irrationalité : Par exemple, démontrer que $\sqrt{2}$ est irrationnel. Supposons $\sqrt{2} = \frac{p}{q}$ avec $p, q \in \mathbb{N}^*$ et $\text{PGCD}(p, q) = 1$. $2 = \frac{p^2}{q^2} \implies p^2 = 2q^2$. Ceci implique que $2 | p^2$. Puisque 2 est premier, si $2 | p^2$, alors $2 | p$. Donc $p = 2k$ pour un certain entier $k$. $(2k)^2 = 2q^2 \implies 4k^2 = 2q^2 \implies 2k^2 = q^2$. Ceci implique que $2 | q^2$. Puisque 2 est premier, si $2 | q^2$, alors $2 | q$. Nous avons $2 | p$ et $2 | q$. Cela signifie que 2 est un diviseur commun de $p$ et $q$. Ceci contredit l'hypothèse $\text{PGCD}(p, q) = 1$. Donc, l'hypothèse de départ est fausse, et $\sqrt{2}$ est irrationnel.

Résolution de problèmes utilisant PGCD et PPCM

Les problèmes peuvent impliquer de trouver des nombres, des dimensions ou des fréquences. Exemple : Deux engrenages ont 24 et 36 dents. Ils sont marqués au point de contact. Combien de tours doit faire le petit engrenage pour que les marques se retrouvent au même point pour la première fois ? Il faut trouver le plus petit nombre de dents qui soit un multiple de 24 et de 36. C'est le PPCM. $\text{PPCM}(24, 36)$: $\text{PGCD}(24, 36)$: $36 = 24 \times 1 + 12$; $24 = 12 \times 2 + 0$. Donc $\text{PGCD}(24, 36) = 12$. $\text{PPCM}(24, 36) = \frac{24 \times 36}{12} = 2 \times 36 = 72$. Le point de contact se retrouvera au bout de 72 dents. Le petit engrenage (24 dents) aura fait $72/24 = 3$ tours. Le grand engrenage (36 dents) aura fait $72/36 = 2$ tours.

Utilisation de Gauss dans des démonstrations

Le théorème de Gauss est souvent utilisé dans les démonstrations d'unicité ou de divisibilité. Par exemple, pour démontrer que si $p$ est un nombre premier et $p | ab$, alors $p | a$ ou $p | b$. Si $p | a$, la propriété est vérifiée. Si $p \nmid a$, alors comme $p$ est premier, $\text{PGCD}(p, a) = 1$. Puisque $p | ab$ et $\text{PGCD}(p, a) = 1$, d'après le théorème de Gauss, $p | b$. Ainsi, $p | a$ ou $p | b$. C'est une propriété fondamentale des nombres premiers.

• Répartition : Partager 120 billes rouges et 180 billes bleues en paquets identiques, contenant le même nombre de billes de chaque couleur, et le plus grand nombre possible de paquets. On cherche le PGCD de 120 et 180. $\text{PGCD}(180, 120)$: $180 = 120 \times 1 + 60$; $120 = 60 \times 2 + 0$. Donc $\text{PGCD}(180, 120) = 60$. On peut faire 60 paquets. Chaque paquet contiendra $120/60 = 2$ billes rouges et $180/60 = 3$ billes bleues.

Définition et propriétés

Un nombre premier est un entier naturel supérieur à 1 qui a exactement deux diviseurs positifs : 1 et lui-même. Exemples : 2, 3, 5, 7, 11, 13, ... Propriétés importantes :

• Tout entier naturel supérieur à 1 qui n'est pas premier est dit composé. Il peut s'écrire comme un produit de nombres premiers.
• Le seul nombre premier pair est 2.
• Tout nombre composé $N$ a au moins un diviseur premier $p$ tel que $p \le \sqrt{N}$. Cette propriété est la base des tests de primalité par division.

Infinité des nombres premiers

Euclide a démontré qu'il existe une infinité de nombres premiers. Démonstration par l'absurde (idée) : Supposons qu'il n'existe qu'un nombre fini de nombres premiers : $p_1, p_2, ..., p_n$. Considérons le nombre $P = (p_1 \times p_2 \times ... \times p_n) + 1$. Si $P$ est premier, alors c'est un nouveau nombre premier, ce qui contredit notre hypothèse. Si $P$ est composé, alors il est divisible par un nombre premier. Ce diviseur premier doit être l'un des $p_i$. Mais si $p_i | P$ et $p_i | (p_1 \times ... \times p_n)$, alors $p_i$ devrait diviser leur différence, c'est-à-dire $p_i | 1$. Ce qui est impossible pour un nombre premier. Donc $P$ n'est divisible par aucun des $p_i$. Il doit donc être premier lui-même, ou divisible par un nombre premier qui n'est pas dans notre liste. Dans les deux cas, cela contredit l'hypothèse de finitude. D'où l'infinité des nombres premiers.

Tests de primalité simples

Pour savoir si un entier $N$ est premier, on peut tester sa divisibilité par tous les nombres premiers $p$ tels que $p \le \sqrt{N}$. Si aucun de ces nombres premiers ne divise $N$, alors $N$ est premier.

Exemple : Tester si 101 est premier. $\sqrt{101} \approx 10,05$. Les nombres premiers à tester sont 2, 3, 5, 7.

• 101 n'est pas divisible par 2 (impair).
• Somme des chiffres $1+0+1=2$, non divisible par 3.
• Ne se termine ni par 0 ni par 5, donc non divisible par 5.
• $101 = 7 \times 14 + 3$, donc non divisible par 7. Puisqu'aucun de ces premiers ne divise 101, 101 est un nombre premier.

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

Tout entier naturel $N$ supérieur à 1 peut être écrit de manière unique (à l'ordre des facteurs près) comme un produit de nombres premiers. Cette décomposition est appelée décomposition en facteurs premiers ou factorisation première. $N = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}$ où $p_1, p_2, ..., p_k$ sont des nombres premiers distincts et $a_1, a_2, ..., a_k$ sont des exposants entiers positifs. Ce théorème est la pierre angulaire de l'arithmétique.

Méthodes de décomposition

Pour décomposer un nombre, on essaie de le diviser par les nombres premiers successifs (2, 3, 5, 7, ...). Exemple : Décomposer 360. $360 \div 2 = 180$ $180 \div 2 = 90$ $90 \div 2 = 45$ $45 \div 3 = 15$ $15 \div 3 = 5$ $5 \div 5 = 1$ Donc $360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5^1$.

Unicité de la décomposition

L'unicité est une propriété cruciale. Elle signifie qu'il n'y a qu'une seule façon d'écrire un nombre comme produit de nombres premiers (si on ne tient pas compte de l'ordre). Cette unicité est une conséquence du théorème de Gauss.

Calcul du PGCD et PPCM via décomposition

Soient $a = p_1^{a_1} \times ... \times p_k^{a_k}$ et $b = p_1^{b_1} \times ... \times p_k^{b_k}$ (on peut inclure des exposants nuls si un premier n'est pas présent dans la décomposition).

• PGCD : On prend les facteurs premiers communs avec le plus petit exposant. $\text{PGCD}(a, b) = p_1^{\min(a_1, b_1)} \times ... \times p_k^{\min(a_k, b_k)}$
• PPCM : On prend tous les facteurs premiers (communs ou non) avec le plus grand exposant. $\text{PPCM}(a, b) = p_1^{\max(a_1, b_1)} \times ... \times p_k^{\max(a_k, b_k)}$

Exemple : $a=360 = 2^3 \times 3^2 \times 5^1$ et $b=108 = 2^2 \times 3^3 \times 5^0$. $\text{PGCD}(360, 108) = 2^{\min(3,2)} \times 3^{\min(2,3)} \times 5^{\min(1,0)} = 2^2 \times 3^2 \times 5^0 = 4 \times 9 \times 1 = 36$. $\text{PPCM}(360, 108) = 2^{\max(3,2)} \times 3^{\max(2,3)} \times 5^{\max(1,0)} = 2^3 \times 3^3 \times 5^1 = 8 \times 27 \times 5 = 1080$.

Vérification de la relation $\text{PGCD} \times \text{PPCM} = ab$: $36 \times 1080 = 38880$ $360 \times 108 = 38880$. La relation est vérifiée.

Nombre de diviseurs

Si $N = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}$, le nombre de diviseurs positifs de $N$, noté $\tau(N)$, est donné par : $\tau(N) = (a_1+1)(a_2+1)...(a_k+1)$ Exemple : Nombre de diviseurs de $360 = 2^3 \times 3^2 \times 5^1$. $\tau(360) = (3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24$. 360 a 24 diviseurs positifs.

Carrés parfaits, cubes parfaits

Un entier est un carré parfait si tous les exposants de sa décomposition en facteurs premiers sont pairs. Exemple : $36 = 2^2 \times 3^2$. Les exposants 2 et 2 sont pairs. Un entier est un cube parfait si tous les exposants de sa décomposition en facteurs premiers sont des multiples de 3. Exemple : $216 = 6^3 = (2 \times 3)^3 = 2^3 \times 3^3$. Les exposants 3 et 3 sont multiples de 3.

Définition d'une équation diophantienne

Une équation diophantienne est une équation dont les solutions recherchées sont des entiers (généralement relatifs). Le terme vient du mathématicien grec Diophante d'Alexandrie.

Exemple : $x^2 + y^2 = z^2$ (triplets pythagoriciens). Les solutions sont des entiers. $3^2 + 4^2 = 5^2 \implies 9 + 16 = 25$.

Existence de solutions

L'existence de solutions entières n'est pas toujours garantie, même si des solutions réelles existent. Exemple : $2x = 3$. Solution réelle $x = 3/2$, mais pas de solution entière.

Cas particulier des équations linéaires

Nous nous intéresserons aux équations diophantiennes linéaires de la forme $ax + by = c$, où $a, b, c$ sont des entiers donnés, et nous cherchons les couples d'entiers $(x, y)$ solutions.

Condition d'existence de solutions (PGCD(a,b) divise c)

Une équation diophantienne linéaire $ax + by = c$ admet des solutions entières $(x, y)$ si et seulement si $\text{PGCD}(a, b)$ divise $c$.

Démonstration :

• Sens direct : Si $(x_0, y_0)$ est une solution, alors $ax_0 + by_0 = c$. Soit $d = \text{PGCD}(a, b)$. Alors $d | a$ et $d | b$. Donc $d | ax_0$ et $d | by_0$. Par propriété de la divisibilité, $d | (ax_0 + by_0)$, donc $d | c$.
• Sens réciproque : Si $d | c$, alors $c = kd$ pour un certain entier $k$. D'après le théorème de Bézout, il existe des entiers $u, v$ tels que $au + bv = d$. Multiplions cette égalité par $k$ : $a(ku) + b(kv) = kd = c$. Donc $(x_0, y_0) = (ku, kv)$ est une solution particulière de l'équation.

Méthode de résolution (Bézout et Gauss)

1. Vérifier la condition d'existence : Calculer $d = \text{PGCD}(a, b)$ (avec l'algorithme d'Euclide). Si $d \nmid c$, il n'y a pas de solutions entières.
2. Trouver une solution particulière :
   • Si $d=1$, utiliser l'algorithme d'Euclide étendu pour trouver $u, v$ tels que $au + bv = 1$. Alors $(x_0, y_0) = (uc, vc)$ est une solution particulière de $ax+by=c$.
   • Si $d > 1$, on peut diviser l'équation par $d$ : $a'x + b'y = c'$ où $a' = a/d$, $b' = b/d$, $c' = c/d$. On a $\text{PGCD}(a', b') = 1$. On résout alors $a'x + b'y = c'$ pour trouver une solution particulière $(x_0, y_0)$. On utilise l'algorithme d'Euclide étendu pour trouver $u, v$ tels que $a'u + b'v = 1$. Alors $x_0 = u c'$ et $y_0 = v c'$ est une solution particulière de $a'x + b'y = c'$.
3. Déterminer l'ensemble des solutions : Soit $(x_0, y_0)$ une solution particulière de $ax+by=c$. L'équation peut s'écrire $a(x-x_0) + b(y-y_0) = 0$, ou $a(x-x_0) = -b(y-y_0)$. Divisons par $d = \text{PGCD}(a, b)$ : $a'(x-x_0) = -b'(y-y_0)$ où $a'=a/d$ et $b'=b/d$. Puisque $\text{PGCD}(a', b') = 1$, et $a' | b'(y-y_0)$, par le théorème de Gauss, $a' | (y-y_0)$. Donc $y-y_0 = k a'$ pour un certain entier $k$. D'où $y = y_0 + k \frac{a}{d}$. En substituant dans l'équation, on trouve $x = x_0 - k \frac{b}{d}$. L'ensemble des solutions est donné par : $x = x_0 - k \frac{b}{\text{PGCD}(a, b)}$ $y = y_0 + k \frac{a}{\text{PGCD}(a, b)}$ où $k \in \mathbb{Z}$.

Exemple : Résoudre $6x + 15y = 33$.

1. $\text{PGCD}(6, 15) = 3$. $33$ est divisible par $3$. Il y a des solutions.
2. On divise l'équation par 3 : $2x + 5y = 11$. On cherche une solution particulière pour $2x + 5y = 11$. On sait que $\text{PGCD}(2, 5) = 1$. Algorithme d'Euclide pour 2 et 5 : $5 = 2 \times 2 + 1 \implies 1 = 5 - 2 \times 2$. Ici, $u=-2, v=1$ sont des coefficients de Bézout pour $2u+5v=1$. Pour $2x+5y=11$, une solution particulière est $x_0 = (-2) \times 11 = -22$ et $y_0 = (1) \times 11 = 11$. Vérification : $2(-22) + 5(11) = -44 + 55 = 11$. C'est correct.
3. L'ensemble des solutions est : $x = x_0 - k \frac{b}{\text{PGCD}(a, b)} = -22 - k \frac{5}{1} = -22 - 5k$ $y = y_0 + k \frac{a}{\text{PGCD}(a, b)} = 11 + k \frac{2}{1} = 11 + 2k$ où $k \in \mathbb{Z}$.

Problèmes de partage

Ces équations sont très utiles pour des problèmes de partage, de monnaie, de mélange, etc., où les quantités doivent être entières. Exemple : Un groupe d'amis a payé 33€ pour des pommes et des oranges. Une pomme coûte 2€ et une orange 5€. Combien de pommes et d'oranges ont-ils acheté ? C'est exactement l'équation $2x + 5y = 33$, où $x$ est le nombre de pommes et $y$ le nombre d'oranges. Les solutions sont $x = -22 - 5k$ et $y = 11 + 2k$. Puisque le nombre de fruits doit être positif : $x \ge 0 \implies -22 - 5k \ge 0 \implies -22 \ge 5k \implies k \le -22/5 \implies k \le -4.4$. $y \ge 0 \implies 11 + 2k \ge 0 \implies 2k \ge -11 \implies k \ge -11/2 \implies k \ge -5.5$. Donc $k$ doit être un entier tel que $-5.5 \le k \le -4.4$. La seule valeur possible pour $k$ est $-5$. Pour $k=-5$ : $x = -22 - 5(-5) = -22 + 25 = 3$ $y = 11 + 2(-5) = 11 - 10 = 1$ Ils ont acheté 3 pommes et 1 orange. Vérification : $2 \times 3 + 5 \times 1 = 6 + 5 = 11$. Ah, l'énoncé d'origine était $2x+5y=11$. Mon exemple est faux. Reprenons $2x+5y=11$. $x = -22 - 5k \ge 0 \implies k \le -4.4$. $y = 11 + 2k \ge 0 \implies k \ge -5.5$. Donc $k=-5$ est la seule solution. $x=3$ et $y=1$.

Cryptographie simple

Bien que la cryptographie moderne utilise des méthodes plus complexes, les équations diophantiennes et les congruences sont à la base de nombreux algorithmes. Par exemple, la recherche d'inverses modulaires est une forme d'équation diophantienne.

Les équations diophantiennes sont un sujet classique des compétitions mathématiques, nécessitant souvent une combinaison astucieuse du théorème de Bézout, de Gauss et des propriétés de divisibilité.

Énoncé du théorème

Soit $p$ un nombre premier. Pour tout entier relatif $a$ non divisible par $p$, on a : $a^{p-1} \equiv 1 \pmod{p}$ Une forme équivalente, valable pour tout entier $a$ (même si $p|a$), est : $a^p \equiv a \pmod{p}$

Exemple : Soit $p=5$ (nombre premier). Prenons $a=2$. $2^{5-1} = 2^4 = 16$. $16 \equiv 1 \pmod{5}$ car $16 = 5 \times 3 + 1$. Le théorème est vérifié. Prenons $a=3$. $3^{5-1} = 3^4 = 81$. $81 \equiv 1 \pmod{5}$ car $81 = 5 \times 16 + 1$. Le théorème est vérifié. Prenons $a=5$. $a$ est divisible par $p$. Le théorème ne s'applique pas directement sous la première forme. Par contre, $a^p \equiv a \pmod{p}$ donne $5^5 \equiv 5 \pmod{5}$, ce qui est $0 \equiv 0 \pmod{5}$. C'est vrai.

Démonstration pour les cas simples

La démonstration générale est un peu complexe, mais l'idée peut être comprise. Considérons l'ensemble des entiers $\{1, 2, ..., p-1\}$ modulo $p$. Multiplions chaque élément par $a$ (où $a$ n'est pas un multiple de $p$) : $\{a \times 1, a \times 2, ..., a \times (p-1)\}$ modulo $p$. Ces $p-1$ produits sont tous distincts modulo $p$ et aucun n'est congru à 0 modulo $p$. Donc, l'ensemble $\{a \times 1, a \times 2, ..., a \times (p-1)\}$ modulo $p$ est une permutation de l'ensemble $\{1, 2, ..., p-1\}$ modulo $p$. Le produit de tous les éléments du premier ensemble est congruent au produit de tous les éléments du second ensemble. $(a \times 1) \times (a \times 2) \times ... \times (a \times (p-1)) \equiv 1 \times 2 \times ... \times (p-1) \pmod{p}$ $a^{p-1} \times (1 \times 2 \times ... \times (p-1)) \equiv (1 \times 2 \times ... \times (p-1)) \pmod{p}$ Soit $M = (p-1)!$. Puisque $p$ est premier, $M$ n'est pas divisible par $p$. On peut donc "diviser" par $M$ modulo $p$. $a^{p-1} \equiv 1 \pmod{p}$.

Conditions d'application

• $p$ doit être un nombre premier. Si $p$ n'est pas premier, le théorème est faux. Exemple : $p=4$ (non premier). $a=3$. $3^{4-1} = 3^3 = 27$. $27 \not\equiv 1 \pmod{4}$ car $27 = 4 \times 6 + 3$.
• Pour la forme $a^{p-1} \equiv 1 \pmod{p}$, $a$ ne doit pas être un multiple de $p$. La forme $a^p \equiv a \pmod{p}$ est plus générale et fonctionne toujours.