Indicatrice d’Euler

1) Cyclicite

a) Il suffit de montrer que pour tout (m,n) ∈ Z2, fg(m + n) = fg(m).fg(n).Or soit (m,n) ∈ Z2, fg(m + n) = gm+n = gm.gn = fg(m).fg(n), d’ou la conclusion.

b) L’element g engendre le groupe G si, et seulement si, pour tout h ∈ G, il existe un n ∈ Ztel que h = gn donc si, et seulement si, pour tout h ∈ G, il existe un n ∈ Z tel que h = fg(n)donc si, et seulement si, fg est surjective.

c) Le morphisme fg n’est pas injectif, si et seulement si, ker(fg) ≠ {0} ssi il existe un n ≠ 0tel que gn = e ssi g est d’ordre fini dans (G, ⋅).Si en outre fg est surjective g est d”ordre fini et engendre (G, ⋅) donc le groupe G estfini. C’est alors un groupe cyclique.. comme annonce par le titre de la question !

2) Indicatrice d’Euler

a) A la main : ϕ(1) = 1 car 1 est premier avec tout le monde donc avec 0.

Dans ⟦0,9⟧ : les nombres premiers avec 10 sont 1,3,7,9 donc ϕ(10) = 4.

Pour p premier tous les nombres dans ⟦1, p − 1⟧ sont premiers avec p, et 0 n’est paspremier avec p donc ϕ(p) = p − 1.

Remarque : pour 10 = 2 × 5 avec 2 ∧ 5 = 1, on verra plus loin au e) que ϕ(10) =ϕ(2)ϕ(5) = 1 × 4, on retrouve le resultat precedent.

b) Vue la derniere ligne, pour que l’algorithme fonctionne, il faut qu’a la fin de la boucleprincipale for i in range(2,n//2+1), on ait pour tout i = 2, . . . , n − 1, table[i] = 1 siet seulement si i est premier avec n.

Les modifications faites dans table consistent a mettre des entrees a 0, sachant qu’audepart toutes les entrees de table sont a 1 (sauf l’entree 0 car 0 n’est pas premier avecn, si n > 1).

Montrons que la propriete P (i) suivante est verifiee pour chaque valeur de i dans laboucle principale :

P (i) : a la fin du i-ieme tour de la boucle principale, toutes les entrees de la formetable[k.j] avec 2 ≤ j ≤ i, j diviseur de n, k ≥ 1, k ≤ (n − 1)//j sont mises a 0.

La preuve de P (i) par rec. est immediate puisque le role du i-ieme tour de boucle estexactement si i est un diviseur de n, de mettre a 0 les entrees table[ki] avec k ≥ 1,k ≤ (n − 1)//i.Or pour k entier, la condition k ≤ (n− 1)//i = ⌊(n− 1)/i⌋ equivaut a k ≤ (n− 1)/i et donca ki ≤ (n − 1).Donc P (i) s’ecrit encore : a la fin du i-ieme tour de la boucle principale, toutes les entreesde la forme table[k.j] avec 2 ≤ j ≤ i, j diviseur de n, k ≥ 1, kj ≤ (n− 1) sont mises a 0.

Ainsi P (n//2) (derniere valeur prise par i dans la boucle) dit que a la fin de la boucle,toutes le entrees de la forme table[kj] avec j ≤ n/2 et j diviseur de n, kj ≤ (n− 1) sontmises a 0.

Or tout facteur premier p d’un nombre n sera inferieur ou egal a n//2, donc a l’issu de laboucle on aura bien mis a zero toutes les entrees de table de la forme kp pour p facteurpremier quelconque de n et la conclusion.

c) def phi(n):

return len(premAvec(n))

d) On conjecture que si a ∧ b = 1 alors ϕ(ab) = ϕ(a)ϕ(b).e) Question pas si facile par des methodes elementaires !

(M1) Avec un peu d’algebre superieure :

Rappel – Si on definit ϕ(n) comme le nombre d’entiers q k ∈ [[0, n − 1]] tels quek ∧ n = 1, alors par caracterisation des inversibles dans Z/nZ, on a pour tout n ≥ 2,ϕ(n) = CardU(Z/nZ) (le nombre d’elements inversibles de Z/nZ).

1

Mais si on considere l’application : C ∶ Z/(ab)Z ↦ Z/aZ × Z/bZ, xab ↦ (xa, xb), qui aune classe modulo ab associe le couple forme de classe modulo a et de la classe modulob, il est evident que C est un morphisme d’anneau et le theoreme chinois dit que C estun isomorphisme.

(M2) La ≪ meme ≫ redigee de maniere plus ≪ elementaire ≫ (ce qui ne signifiepas plus simple)...

Une autre facon de comprendre le theoreme Chinois est le

Lemme : Si a∧ b = 1 alors ∀k ∈ ⟦0, ab− 1⟧, ∃ ! (u, v) ∈ ⟦0, b− 1 ⟧× ⟦0, a− 1⟧, k = au+ bv.

Preuve du lemme : on peut considerer l’application ψ ∶ ⟦0, b−1 ⟧×⟦0, a−1⟧→ ⟦0, ab−1⟧,(u, v)↦ au + bv.

On veut montrer que ψ est bijective.

Il suffit, par egalite des cardinaux de verifier l’injectivite.

Or bu + av ≡ bu′ + av′ [ab]⇒ bu ≡ bu′[a] et comme b ∧ a = 1 ceci equivaut a u ≡ u′[a].De meme pour v ≡ v′[b].Application du lemme – Soit k ∈ ⟦0, ab − 1⟦, qu’on ecrit (ecriture unique) k = au + bvcomme dans le lemme.

Alors k ∧ ab = 1 ⇔ (au + bv) ∧ ab = 1⇔ (au + bv) ∧ a = 1 et (au + bv) ∧ b = 1

Ceci equivaut a bv ∧ a = 1 et (au) ∧ b = 1.

Finalement encore a u ∧ a = 1 et v ∧ b = 1.

3) Convolution

a) (i) Propriete bien connue : (CN∗ ,+) est un groupe abelien.

(ii) Proprietes de ∗ (produit de Dirichlet) :

Notation : Pour tout entier n naturel, on note Dn l’ensemble des diviseurs de n dansN.

● Commutativite : l’application ψ ∶ Dn →Dn, x ↦ n/x est bijective, car ψ ○ ψ = id.

En appliquant le changement d’indice induit par ψ, on a immediatement la commutati-vite.

Une autre ecriture, plus symetrique du produit de Dirichlet est de l’ecrire : (f ∗ g)(n) =∑

(a,b)∈N2, ab=n

f(a)g(b).

● Associativite :

Soit (f, g, h) ∈ E3. Pour tout n ∈ N∗, on peut ecrire f ∗ (g ∗ h)(n) = ∑(a,b)∈N∗2

f(a)(g ∗

h)(b) = ∑ab=n

f(a) ∑cd=b

g(c)h(d) = ∑acd=n

f(a)g(c)h(d). Cette ecriture est invariante par

toute permution de f, g, h.

● Neutre : soit δ la fonction definie par δ(1) = 1 et ∀n ≥ 2, δ(n) = 0.

On verifie immediatement que e est neutre pour ∗. (On rappelle que si le neutre existe,il est unique).

(iii) Distributivite de ∗ par rapport a + :

Par def., avec des notations evidentes, ((f+g)∗h)(n) = ∑d∈Dn

(f+g)(d)h(nd) = ∑

d∈Dn

f(d)h(nd)+

∑d∈Dn

g(d)h(nd) = f ∗h(n)+ g ∗h(n). D’ou la conclusion (la distributivite d’un cote suffit

car ∗ est commutative).

b) L’egalite admise 1 ∗ ϕ = id equivaut a ∀n ∈ N, ∑d∣n

ϕ(d) = n.

Cette formule dite parfois formule de Mobius, peut se montrer en considerant que si Gest un groupe cyclique a n elements alors G est l’union disjointe des ensembles Gd formesde ses elements d’ordre exactement d.

La fonction µ de l’enonce s’appelle aussi fonction de Mobius.

Avec l’egalite admise on sait que ϕ = id∗1−1 ou 1−1 designe l’inverse de la fonctionconstante egale a 1.

2

Donc pour montrer l’egalite demandee, il suffit de montrer que µ = 1−1.

N.B. Ceci rend l’introduction de cette fonction µ naturelle (plus que sa definition) :c’est l’inverse de la fonction constante egale a 1 pour ∗.

Preuve de l’egalite µ = 1−1

Il s’agit de montrer que µ ∗ 1 = δ.Autrement dit que : µ(1) = 1 et que pour tout n ≥ 2, ∑

d∣n

µ(d) = 0.

Or pour n ≥ 2 et n = pα1

1 . . . pαrr , la forme generale d’un diviseur de n est m = pβ1

1 . . . pβrr

avec 0 ≤ βi ≤ αi pour tout i = 1, . . . , r.

Mais si l’un des βi ≥ 2, on aura µ(m) = 0 donc :

∑d∣n

µ(d) = ∑(β1,...,βr)∈[[0,1]]r

µ(pβ1

1 . . . pβrr ) = ∑

(β1,...,βr)∈[[0,1]]r(−1)β1+⋯+βr .

Or, pour chaque k = 0, . . . , r l’ensemble des (β1, . . . , βr) ∈ [[0,1]]r tels que β1+⋯+βr = kest de cardinal (r

k) (choix des k elements valant 1, les autres valant 0).

Donc :

∑d∣n

µ(d) =r

∑k=0

(rk)(−1)k = (1 − 1)r = 0,

grace a la formule du binome.

3