Sujet : Algèbre, Eléments d'algèbre générale, Indicatrice d'Euler

[http://mp.cpgedupuydelome.fr] édité le 26 juillet 2013

Indicatrice d’Euler

Exercice 1[ 02655 ][correction]
Combien y a-t-il d’éléments inversibles dansZ78Z?

Enoncés

Exercice 2[ 00151 ][correction]
Pourn∈N?, on noteϕ(n)le nombre d’éléments inversibles dans(ZnZ×).
a) Calculerϕ(p)etϕ(pα)pourppremier etα∈N?.
b) Soientmetnpremiers entre eux.
On considère l’applicationf:ZmnZ→ZnZ×ZmZdéfinie parf(¯x) = (ˆx x˜).
Montrer quefdéfinie et réalise un isomorphisme d’anneaux.est bien
c) En déduire queϕ(mn) =ϕ(m)ϕ(n).
d) Exprimerϕ(n)selon la décomposition primaire den.

Exercice 3[ 00257 ][correction]
Etablir
∀n>3 ϕ(n)

nln 2
>lnn 2+ l
n

Exercice 4[ 02374 ][correction]
Montrer que pour tout entiern>3,ϕ(n)est un nombre pair.

Exercice 5[ 00152 ][correction]
Pourn∈N?, on noteϕ(n)le nombre d’éléments inversibles dans(ZnZ×).
Etablir
∀a∈(ZnZ)? aϕ(n)= 1

Exercice 6[ 00153 ][correction]
Pourn∈N?, on noteϕ(n)le nombre de générateurs de(ZnZ+).
a) Montrer que siHest un sous-groupe de(ZnZ+), il existeadivisantn
vérifiantH=< a¯>.
b) Observer que sid|nil existe un unique sous-groupe de(ZnZ+)d’ordred.
c) Justifier que sid|nle groupe(ZnZ+)possède exactementϕ(d)éléments
d’ordred.
d) Montrer
∀n∈N?Xϕ(d) =n
d|n

Exercice 7[ 03634 ][correction]
On noteϕla fonction indicatrice d’Euler.
a) Soitdun diviseur positif den∈N?. Combien y a-t-il d’entierskvérifiant

b) En déduire

k∈[1 n]et pgcd(k n) =d?

n=Xϕ(d)
d|n

Exercice 8[ 02381 ][correction]
SoientT= (tij)∈ Mn(R)déterminée par
siidivis
tij=01esinonj

etD=diag(ϕ(1)     ϕ(n))∈ Mn(R)matrice diagonale.
On rappelle la propriété
∀n∈N? n=Xϕ(d)
d|n

a) Calculer le coefficient d’indice(i j)de la matricetT DTen fonction de
pgcd(i j).
b) En déduire la valeur du déterminant de la matrice de Smith
S=dpcggcdp(2(111))pgccddpg(1(2))22∙∙∙∙∙∙pggpddcc1(2(nn))
pgcd.(n1)pgcd.(n2)∙ ∙ ∙pgcd.(n n)

1

Diffusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 26 juillet 2013

Corrections

Corrections

Exercice 1 :[énoncé]
Les inversibles dansZ78Zsont les classes associés aux entiers de{1    78}qui
sont premiers avec78 = 2×3×13. Il suffit ensuite de dénombrer les multiples de
2313compris entre 1 et 78. On conclut qu’il y a 24 éléments inversible dans
Z78Z. On peut aussi calculerϕ(78) = 1×2×12 = 24.

Exercice 2 :[énoncé]
Les éléments inversibles de(ZnZ×)sont les éléments représentés par un nombre
premier avecn.
a)ϕ(p) =p−1. Etre premier avecpαéquivaut à tre premier avecpi.e. à ne pas
tre divisible parppuisquep∈ P. Il y apα−1multiples depcompris entre 1 etpα
doncϕ(pα) =pα−pα−1.
b) Six=y[mn]alorsx=y[n]etx=y[m]doncfest bien définie.
ϕ1¯()=(ˆ1)˜1et sia=x+yxy[mn]alorsa=x+yxy[n]doncϕest un
morphisme d’anneaux.
Sif(x¯) =f(y¯)alorsx=y[m]etx=y[n]alorsm n|y−xet puisque
m∧n= 1alorsmn|y−xdonc¯ ¯ [mn].
x=y
fest injective puis bijective par l’égalité des cardinaux.
c) Les inversibles deZmnZcorrespondent aux couples formés par un inversible
deZnZet un inversible deZmZ. Par suiteϕ(mn) =ϕ(m)ϕ(n).
N N
d) Sin=Qpiαialorsϕ(n) =Qpiαi−1(pi−1).
i=1i=1

Exercice 3 :[énoncé]
Notonsp1     prles facteurs premiers den. On sait
ϕ(n) =n1−p11 1−p12  1−p1r

En ordonnant lesp1 p2     pr, on peut affirmer

∀16i6r pi>1 +i

et donc
1−p11 1−p12  1−p1r>1−12 1−31  1−+11r



Par produit télescopique
1 2r
1−p11 1−p12  1−p1r>2 3∙ ∙ ∙r+ 1r
=

Or on a aussi

et donc

On en déduit

n>p1   pr>2r

n
r6
ln 2

n nln 2
=
ϕ(n)6lnn2+ 1n+ ln 2

1
+ 1

Exercice 4 :[énoncé]
Sinpossède un facteur premier impairpalors on peut écriren=pαmavecm
premier avecp. On a alors

ϕ(n) =ϕ(pα)ϕ(m) = (pα−pα−1)ϕ(m)

2

Puisquepα−pα−1est un nombre pair (par différence de deux impairs), on obtient
queϕ(n)est pair.
Sinpas de facteurs premiers impairs, on peut écrirene possède n= 2αavec
α>2et alorsϕ(n) = 2α−1est un nombre pair.

Exercice 5 :[énoncé]
Soitf:x7→axde(ZnZ)?vers lui-mme.
Cette application est bien définie, injective et finalement bijective par cardinalité.
Ainsi
Yx=Yax=aϕ(n)Yx
x∈(ZnZ)?x∈(ZnZ)?x∈(ZnZ)?
puisaϕ(n)= 1car l’élémentQxest inversible.
x∈(ZnZ)?

Exercice 6 :[énoncé]
a) SoitHun sous-groupe deZnZ.
SiH={0}alorsH=< n >.
Sinon, on peut introduirea= mink∈N?k∈H.
¯
La division euclidienne denparadonnen=qa+rd’oùr¯∈Hpuisr= 0. Ainsi
a|n.

Diffusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 26 juillet 2013

Corrections

O¯ Ha >et par division euclidienne on montreH⊂<¯a >d’où< a >=H.
n a<⊂
b) Siadivisen, on observe que<¯a >est de cardinal ’ordrena. Ainsi< nd >
est l’unique sous-groupe d’ordredde(ZnZ+).
c) Un élément d’ordreddeZnZest générateur d’un sous-groupe àdéléments
donc générateur de< nd >. Inversement, tout générateur de< nd >est
élément d’ordreddeZnZ. Or< nd >est cyclique d’ordreddonc isomorphe à
ZdZet possède ainsiϕ(d)générateurs. On peut donc affirmer queZnZpossède
exactementϕ(d)élément d’ordred.
d) L’ordre d’un élément deZnZest cardinal d’un sous-groupe deZnZet donc
diviseur den. En dénombrantZnZselon l’ordre de ses éléments, on obtient
Xϕ(d) =n
d|n

Exercice 7 :[énoncé]
a) On peut écriren=dm.
Sik∈[1 n]vérifie pgcd(k n) =dalorsddiviseket donc on peut écrirek=d`
avec`∈[1 m].
De plus pgcd(k n) =pgcd(d` dm) =ddonne`∧m= 1.
Inversement, sik=d`avec`∈[1 m]et`∧m= 1alorsk∈[1 n]et
pgcd(k n) =pgcd(d` dm) =d.
Ainsi, il y a autant dekcherché que de`éléments de[1 m]premiers avecm, à
savoirϕ(m).
b) En partitionnant[1 n]selon les valeurs possiblesddu pgcd de ses éléments
avecn(ce qui détermine un diviseur den), on peut écrire
[1 n]=[{k∈[1 n]pgcd(k n) =d}
d|n

Puisque c’est une union d’ensembles deux à deux disjoints, on obtient
Card[1 n]=XCard{k∈[1 n]pgcd(k n) =d}
d|n

ce qui donne

n=Xϕ(nd) =Xϕ(δ)
d|n δ|n

en procédant pour l’étape finale à une réindexation de la somme.

Exercice 8 :[énoncé]
a) Le coefficient d’indice(i j)de la matriceDT