Arithmétique et PGCD
Divisibilité
On dit que \(a\) divise \(b\) (noté \(a \mid b\)) s'il existe un entier \(k\) tel que \(b = ka\).
Propriétés : si \(a \mid b\) et \(a \mid c\), alors \(a \mid (b+c)\) et \(a \mid (b-c)\). Si \(a \mid b\) et \(b \mid c\), alors \(a \mid c\).
Division euclidienne
Pour tous entiers \(a \in \mathbb{Z}\), \(b \in \mathbb{Z}^*\), il existe un unique couple \((q, r)\) avec \(0 \le r < |b|\) tel que :
\(q\) est le quotient, \(r\) le reste. On a \(b \mid a \iff r = 0\).
PGCD — Plus Grand Commun Diviseur
Le PGCD de \(a\) et \(b\) est le plus grand entier qui divise simultanément \(a\) et \(b\).
C'est la base de l'algorithme d'Euclide (divisions euclidiennes successives jusqu'à reste nul). Propriétés clés :
- \(\pgcd(a, 0) = a\)
- \(\pgcd(a, b) = \pgcd(b, a)\)
- Si \(\pgcd(a,b)=d\), alors \(\pgcd(a/d,\, b/d)=1\)
Entiers premiers entre eux (copremiers)
\(a\) et \(b\) sont premiers entre eux si \(\pgcd(a,b) = 1\).
Théorème de Bézout
Il existe une solution entière \((u, v)\) à \(au + bv = c\) si et seulement si \(\pgcd(a,b) \mid c\).
Lemme de Gauss
PPCM — Plus Petit Commun Multiple
Nombres premiers
Un entier \(p \ge 2\) est premier s'il a exactement deux diviseurs : 1 et lui-même. Pour tester si \(n\) est premier, il suffit de vérifier qu'aucun premier \(p \le \sqrt{n}\) ne le divise.
Congruences
\(a \equiv b \pmod{n}\) signifie \(n \mid (a-b)\). Les congruences sont compatibles avec \(+\) et \(\times\) :
Preuve : correction de l'algorithme d'Euclide
Énoncé : \(\pgcd(a, b) = \pgcd(b, r)\) où \(r = a \bmod b\).
Posons \(a = bq + r\) et \(d = \pgcd(a,b)\).
- \(d \mid a\) et \(d \mid b\) donc \(d \mid (a - bq) = r\). Ainsi \(d\) divise \(b\) et \(r\).
- Si \(d' \mid b\) et \(d' \mid r\), alors \(d' \mid (bq + r) = a\), donc \(d' \le d\).
Les ensembles de diviseurs communs de \((a,b)\) et de \((b,r)\) coïncident, donc leurs PGCD aussi. \(\square\)
Preuve : lemme de Gauss
Énoncé : Si \(a \mid bc\) et \(\pgcd(a,b)=1\), alors \(a \mid c\).
Par Bézout, il existe \((u,v) \in \mathbb{Z}^2\) tels que \(au + bv = 1\). En multipliant par \(c\) :
\[auc + bvc = c\]\(a \mid auc\) (trivial) et \(a \mid bc\) donc \(a \mid bvc\). Ainsi \(a \mid c\). \(\square\)
Preuve : infinité des nombres premiers
Par l'absurde (Euclide) : Supposons qu'il n'en existe qu'un nombre fini \(p_1, \ldots, p_k\). Posons \(N = p_1 p_2 \cdots p_k + 1\).
\(N > 1\) donc admet un diviseur premier \(p\). Comme \(p \mid N\) et \(p \mid p_1\cdots p_k\), on aurait \(p \mid 1\), impossible. Contradiction. \(\square\)
Méthode 1 : Euclide à la main — \(\pgcd(252, 98)\)
Dernier reste non nul : \(\pgcd(252, 98) = 14\).
Méthode 2 : Coefficients de Bézout (remontée)
Résultat : \(252 \times 2 + 98 \times (-5) = 14\).
Méthode 3 : Résoudre \(au + bv = c\)
- Calculer \(d = \pgcd(a,b)\). Si \(d \nmid c\), pas de solution.
- Trouver \((u_0, v_0)\) solution de \(au+bv=d\) par remontée d'Euclide.
- Multiplier par \(c/d\) : solution particulière \((u_1, v_1) = (u_0 c/d,\, v_0 c/d)\).
- Solution générale : \(u = u_1 + \dfrac{b}{d} k\), \(v = v_1 - \dfrac{a}{d} k\), \(k \in \mathbb{Z}\).
Méthode 4 : Tester la primalité de \(n\)
Diviser par tous les premiers \(p \le \sqrt{n}\). Si aucun ne divise \(n\), alors \(n\) est premier.
Exemple : \(n = 97\), \(\sqrt{97} \approx 9{,}8\). Tester 2, 3, 5, 7 : aucun ne divise 97, donc 97 est premier.
Méthode 5 : Puissance modulo \(n\) (exponentiation rapide)
Exemple : \(3^{10} \bmod 7\)
\(\pgcd(12, 8) = 4\) (plus grand commun diviseur), \(\text{ppcm}(12, 8) = 24\) (plus petit commun multiple). La formule \(\text{ppcm} = |ab|/\pgcd\) relie les deux.
\(au + bv = d\) avec \(d = \pgcd(a,b)\). Pour résoudre \(au+bv=c\), vérifier d'abord que \(d \mid c\). Si \(d \nmid c\), il n'existe aucune solution entière.
Sans \(\pgcd(a,b)=1\), \(a \mid bc\) n'implique pas \(a \mid c\). Contre-exemple : \(4 \mid 6 \times 2\) mais \(4 \nmid 6\) et \(4 \nmid 2\).
On peut diviser uniquement si \(\pgcd(k,n)=1\). Exemple : \(2\times3 \equiv 2\times6 \pmod{6}\) mais \(3 \not\equiv 6 \pmod{6}\).
Par définition, 1 n'est PAS premier (il n'a qu'un seul diviseur). Le plus petit nombre premier est 2. La décomposition en facteurs premiers exclut 1.
Calculatrice — PGCD intégré
TI : MATH → NUM → gcd(, ex. gcd(252, 98) → 14. Casio : menu RUN-MAT → CATALOG → GCD. NumWorks : console Python, import math; math.gcd(252, 98).
Python — algorithme d'Euclide
def pgcd(a, b):
while b != 0:
a, b = b, a % b
return abs(a)
print(pgcd(252, 98)) # 14
print(pgcd(35, 0)) # 35
print(pgcd(-12, 18)) # 6Python — coefficients de Bézout (Euclide étendu)
def bezout(a, b):
"""Retourne (d, u, v) tels que a*u + b*v = d = pgcd(a, b)."""
if b == 0:
return a, 1, 0
d, u1, v1 = bezout(b, a % b)
return d, v1, u1 - (a // b) * v1
d, u, v = bezout(252, 98)
print(f"pgcd = {d}, u = {u}, v = {v}")
print(f"Vérif : 252×{u} + 98×{v} = {252*u + 98*v}")
# pgcd = 14, u = 2, v = -5Python — test de primalité et crible d'Ératosthène
import math
def est_premier(n):
if n < 2: return False
if n == 2: return True
if n % 2 == 0: return False
for p in range(3, math.isqrt(n) + 1, 2):
if n % p == 0: return False
return True
def crible(N):
premier = [True] * (N + 1)
premier[0] = premier[1] = False
for i in range(2, math.isqrt(N) + 1):
if premier[i]:
for j in range(i*i, N+1, i):
premier[j] = False
return [i for i, p in enumerate(premier) if p]
print(crible(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]Python — module math et décomposition
import math
print(math.gcd(252, 98)) # 14 (Python ≥ 3.5)
print(math.lcm(12, 18)) # 36 (Python ≥ 3.9)
def facteurs_premiers(n):
f, d = [], 2
while d * d <= n:
while n % d == 0:
f.append(d); n //= d
d += 1
if n > 1: f.append(n)
return f
print(facteurs_premiers(360)) # [2, 2, 2, 3, 3, 5]Exercice 1 : Fraction irréductible
Réduire la fraction \(\dfrac{252}{98}\).
Solution : \(\pgcd(252, 98) = 14\), donc \(\dfrac{252}{98} = \dfrac{18}{7}\).
Exercice 2 : Équation diophantienne
Résoudre dans \(\mathbb{Z}^2\) : \(15u + 21v = 3\).
- \(d = \pgcd(15, 21) = 3\) et \(3 \mid 3\) : des solutions existent.
- Remontée : \(3 = 3\times15 - 2\times21\). Solution particulière : \(u_0=3,\, v_0=-2\).
- Solution générale : \(u = 3 + 7k,\quad v = -2 - 5k,\quad k\in\mathbb{Z}\).
Exercice 3 : Lien avec les complexes
Les racines \(n\)-ièmes de l'unité \(\omega_k = e^{2ik\pi/n}\) vérifient \(\omega_k^m = 1 \iff n \mid km\). Si \(\pgcd(k,n)=1\), par le lemme de Gauss \(n \mid m\) est forcé, donc \(\omega_k\) est d'ordre \(n\) (racine primitive).
Exercice 4 : Chiffre des unités de \(7^{100}\)
Puissances de 7 mod 10 : \(7, 49\equiv9, 7^3\equiv3, 7^4\equiv1\). Période 4. Comme \(100=25\times4\), on a \(7^{100}\equiv1\pmod{10}\).
Réponse : 1.
Exercice 5 : Pire cas d'Euclide — suite de Fibonacci
Les entiers consécutifs de Fibonacci \((F_n, F_{n+1})\) réalisent le pire cas : \(\pgcd(F_{n+1}, F_n) = 1\) avec \(n\) étapes. C'est le théorème de Lamé : la complexité de l'algorithme d'Euclide est en \(O(\log \min(a,b))\).
-
1. \(\pgcd(84, 36)\) vaut :
\(84 = 2\times36+12\), \(36=3\times12\). Dernier reste non nul : \(\pgcd(84,36) = 12\).
-
2. L'équation \(6u + 9v = 5\) admet-elle des solutions entières ?
\(\pgcd(6,9)=3\) et \(3 \nmid 5\), donc aucune solution entière (Bézout).
-
3. Si \(\pgcd(a,b)=1\) et \(a \mid 5b\), alors :
Lemme de Gauss : \(\pgcd(a,b)=1\) et \(a\mid 5b\) impliquent \(a\mid 5\). Donc \(a \in \{1, 5\}\).
-
4. Le chiffre des unités de \(3^{2025}\) est :
Puissances de 3 mod 10 : 3, 9, 7, 1 (période 4). \(2025 = 506\times4 + 1\), donc \(3^{2025} \equiv 3 \pmod{10}\).