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

Description

[http://mp.cpgedupuydelome.fr] édité le 26 juillet 2013 Enoncés 1 Indicatrice d’Euler Exercice 7 [ 03634 ] [correction] On note ϕ la fonction indicatrice d’Euler. ?a) Soit d un diviseur positif de n∈N . Combien y a-t-il d’entiers k vérifiantExercice 1 [ 02655 ] [correction] Combien y a-t-il d’éléments inversibles dansZ/78Z? k∈ [1,n] et pgcd(k,n) =d? b) En déduire XExercice 2 [ 00151 ] [correction] n = ϕ(d)?Pour n∈N , on note ϕ(n) le nombre d’éléments inversibles dans (Z/nZ,×). α ? d|na) Calculer ϕ(p) et ϕ(p ) pour p premier et α∈N . b) Soient m et n premiers entre eux. On considère l’application f :Z/mnZ→Z/nZ×Z/mZ définie par f(x¯) = (x,ˆ x˜). Exercice 8 [ 02381 ] [correction]Montrer que f est bien définie et réalise un isomorphisme d’anneaux. Soient T = (t )∈M (R) déterminée pari,j nc) En déduire que ϕ(mn) =ϕ(m)ϕ(n). d) Exprimer ϕ(n) selon la décomposition primaire de n. 1 si i divise j t =i,j 0 sinon Exercice 3 [ 00257 ] [correction] et D = diag(ϕ(1),...,ϕ(n))∈M (R) matrice diagonale.nEtablir On rappelle la propriétén ln 2 X∀n> 3,ϕ(n)> ?∀n∈N ,n = ϕ(d)lnn + ln 2 d|n ta) Calculer le coefficient d’indice (i,j) de la matrice TDT en fonction deExercice 4 [ 02374 ] [correction] pgcd(i,j).Montrer que pour tout entier n> 3, ϕ(n) est un nombre pair. b) En déduire la valeur du déterminant de la matrice de Smith   pgcd(1, 1) pgcd(1, 2) ··· pgcd(1,n)Exercice 5 [ 00152 ] [correction]  pgcd(2, 1) pgcd(2, 2) ··· pgcd(2,n)?

Sujets

• Classe préparatoire aux grandes écoles
• Mathématiques, physique et sciences de l'ingénieur
• Public Readiness and Emergency Preparedness Act
• exercices
• Spécialité

Informations

• Publié par: algebre-mpsi
• Nombre de lectures: 530
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

[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