Une généralisation du théorème d’Euler
Alexandre Bailleul
Théorème (Fermat). Soit p un nombre premier et soit a ∈ Z. Alors p divise
ap − a.
Cet énoncé peut se traduire par le fait que tout élément x de l’anneau Z/pZ
vérifie xp = x. En effet, p divise ap − a revient à dire que ap = a (mod p). Il existe
une démonstration très simple de ce théorème utilisant le théorème de Lagrange en
théorie des groupes. Tout d’abord si a est divisible par p alors le résultat évident.
Sinon, la classe de a modulo p est un élément du groupe (Z/pZ)× des éléments
inversibles de Z/pZ pour la multiplication, qui est de cardinal p − 1. Le théorème
de Lagrange donne alors que ap−1 = 1 (mod p), soit finalement ap = a (mod p).
Si on souhaite généraliser ce théorème au cas d’un entier n non premier, on est
amené à introduire l’indicatrice d’Euler ϕ, telle que
ϕ(n) = |(Z/nZ)× | = |{k ∈ {1, . . . , n − 1} | (n, k) = 1}|,
où (n, k) désigne le PGCD de n et k, la dernière égalité étant vraie car l’inversibilité
modulo n est équivalente à l’existence d’une relation de Bezout avec n. La même
démonstration fournit alors le
Théorème (Euler). Soit n ∈ N∗ et soit a un entier divisible par n ou premier
avec n. Alors
aϕ(n)+1 = a (mod n).
Cependant, cette égalité n’est pas forcément vérifiée pour tous les éléments de
Z/nZ. Par exemple 12 ne divise jamais 2k − 2 pour k ≥ 2, qui vaut toujours 2 ou
6 modulo 12. Mais 10 divise 25 − 2 = 30 alors que 2 n’est ni divisible par 10, ni
premier avec 10. Ces deux situations sont différentes car dans le second cas, 2 et
10/2 = 5 sont premiers entre eux, tandis que dans le premier cas, 2 et 12/2 = 6
ne le sont pas.
Définition. Soit n ∈ N∗ et a un diviseur de n. On dit que a est un diviseur
unitaire de n si (a, n/a) = 1.
1
Lemme 1. Soit n ∈ N∗ et a un diviseur unitaire de n. Alors
aϕ(n)+1 = a (mod n).
Démonstration. En effet, par hypothèse, a et n/a sont premiers entre eux, donc
d’après le théorème d’Euler (et après avoir simplifié par a, ce qui est possible car
a est inversible modulo n/a),
aϕ(n/a) = 1 (mod n/a).
De plus, comme ϕ est une fonction multiplicative (ce qui résulte du lemme chinois),
on a ϕ(n) = ϕ(a × n/a) = ϕ(a)ϕ(n/a) et donc
aϕ(n) = aϕ(n/a)ϕ(a) = 1ϕ(a) = 1 (mod n/a),
et donc en multipliant par a,
aϕ(n)+1 = a (mod n).
Remarque. On a en fait
aϕ(n/a)+1 = a (mod n).
Lemme 2. Soit n ∈ N∗ sans facteur carré (c’est-à-dire qui n’est divisible par
aucun carré de nombres premiers). Alors tout entier a ∈ {1, . . . , n − 1} est produit
d’un diviseur unitaire de n et d’un entier premier avec n.
Démonstration. En effet, si a n’est pas premier avec n, c’est qu’il admet certains
facteurs premiers en commun avec n. Notons d le produit de ces facteurs. Comme
n est sans facteurs carrés, chacun de ces nombres premiers n’apparaît qu’une seule
fois dans d, et donc d divise n. De plus d est un diviseur unitaire de n car les
facteurs premiers de n/d ne divisent pas d, encore une fois car n est sans facteur
carré. Enfin les facteurs premiers de a/d sont ceux de a qui ne divisent pas n, et
donc a/d est premier avec n. Finalement on a bien
a = d × a/d,
avec d diviseur unitaire de n et a/d premiers avec n.
2
Corollaire. Soit n ∈ N∗ sans facteur carré. Alors pour tout a ∈ Z,
aϕ(n)+1 = a (mod n).
Démonstration. Si a = 0 (mod n), le résultat est évident. Sinon on écrit a = cd
(mod n) par le lemme 2, avec c premier avec n et d diviseur unitaire de n. D’après
le théorème d’Euler,
cϕ(n)+1 = c (mod n)
et d’après le lemme 1,
dϕ(n)+1 = d (mod n).
Ainsi
aϕ(n)+1 = cϕ(n)+1 dϕ(n)+1 = cd = a (mod n).
Référence
[1] R. Hansen, L. Swanson, Unitary divisors, Mathematics Magazine, 1979
