Corrigé DS 3 : Arithmétiques.

Groupes cycliques.
Suites numériques.
MPSI-Maths. Source disponible sur :
Mr Mamouni & El Hassani : myismail1@[Link] c [Link]

Lundi 10 Décembre 2007.

Durée: 3 heures 30mn.

Problème 1. (Fonction indicatrice d’Euler.) a) On vérifie d’abord que θ(1, 1) = 1, θ(a + c, b + d) = ϕ(a, b) +
ϕ(c, d) et enfin θ(a c, b d) = θ(a, b) θ(c, d)
1) n est premier ⇐⇒ k ∧ n = 1, ∀ 1 ≤ k ≤ n ⇐⇒ ϕ(n) = 1.
Injection : Montrer que Ker (θ) = {(0, 0)}.
2) k ∧ n = 1 ⇐⇒ ∃u, v ∈ Z tel que nu + kv = 1 Surjection : Les ensembles de départ et d’arrivées ont même
⇐⇒ ∃v ∈ Z tel que kv ≡ 1 [n] cardinal.
⇐⇒ ∃v ∈ Z tel que k v = 1
⇐⇒ k est inversible dans Z/nZ
3) (Z/nZ, +, ×) est un corps ⇐⇒ ∀ 1 ≤ k ≤ n, k est inversible b) x inversible dans Z/nZ, y inversible dans Z/mZ, est evident
dans Z/nZ par définition de l’inversiblilié.
⇐⇒ ∀ 1 ≤ k ≤ n, k ∧ n = 1 (x, y) inversible dans Z/nZ × Z/mZ ⇐⇒ θ(x, y)xy inversible
⇐⇒ n est premier dans Z/nmZ, car θ est un isomorphisme.

4) cardU (Z/nZ) = card{k ∈ [|1, n|] tel que k ∧ n = 1} = ϕ(n)

5) Soit (m, n) ∈ N∗ tel que n ∧ m = 1. c) D’aprés la question précédente, on a :

MPSI-Maths DS 3: Arithmétique, groupes cycliques & suites. [Link]

Mrs El Hassani & Mamouni Page 1 sur 4 myismail1@[Link]
 n k
ϕ(nm) = card (U (Z/nmZ)) 3) a) On a o(a) = n, donc an = e et (ak ) n∧k = (an ) n∧k = e, d’où
= card (U (Z/nZ × Z/mZ)) n
m = o(ak ) divise , d’autre part amk = (ak )m = e, donc
= card (U (Z/nZ) × U (Z/mZ)) n∧k
n k n V k
= ϕ(n)ϕ(m) o(a) = n divise mk, donc n divise m n , or ,
n∧k n∧k
n ∧ k n ∧ k
6) Par récurrence sur r. n
donc divise m.
7) ϕ(pα ) = card{k ∈ [|1, pα |] tel que k ∧ pα = 1} n∧k
= pα − card{k ∈ [|1, pα |] tel que k ∧ p 6= 1} n
b) G = ak ⇐⇒ cardG = o(ak ) ⇐⇒ n = ⇐⇒ k ∧ n = 1.
= pα − card{k ∈ [|1, pα |] tel que p divise k} n∧k
= pα − card{k = qp tel que q ∈ [|1, pα−1 |]} c) Le nombre des générateurs de G est celui des entier
= pα − pα−1 k, tel que 1 ≤ k ≤ n tel que k ∧ n = 1, c’est à dire ϕ(n).
zn
8) Application : 4) Il est clair que 1 ∈ Un . Soit z1 , z2 ∈ Un , alors (z1 z2−1 )n = 1n , donc
r z2
z1 z2−1 ∈ U, d’où U est un sous-groupe de (C∗ , ×).
Y
a) Posons n = pαi i , avec p1 < · · · < pr , donc ϕ(n) = 2kπ 2π

! i=1 D’autre part : Un = {ei n , 0 ≤ k ≤ n − 1} =< w > où w = ei n ,

r r r
Y Y Y donc monogène, or il est fini de cardinal, n, donc cyclique.
ϕ pαi i = ϕ(pαi i ) = pαi i −1 (pi − 1), si ϕ(n) divise n, Il y exactement ϕ(n) racines nème primitives de l’unité, ce sont
i=1 i=1 i=1
r
Y r
Y les w k tel que , 1 ≤ k ≤ n et k ∧ n = 1..
alors (pi − 1), qui est pair divise pi , ceci est impossible Pour n = 3, w = j, les racines primitives sont j et j 2 .
i=1
r
i=1 Pour n = 4, w = i, les racines primitives sont i et i3 = −i.
Y
si r ≥ 3 car 4 divisera pi , le seul cas possible est r = 2 5) a) Il est trés simple de montrer que Hd est un sous groupe de
i=1 (G, .), en vérifiant que, e ∈ H(ed = e) et que si (x, y) ∈ H 2 ,
avec p1 = 2, p2 = 3. (xd = y d = e), alors x.y −1 ∈ Hd car (x.y −1 )d = xd y −d = e. Mon-
n
k trons maintenant que Hd = a d , par double inclusion, en
b) Le nombre de fractions , tel que 1 ≤ k ≤ n qu’on peut
n utilisant surtout que o(a) = n.
a
mettre sous la forme , avec a ∧ d = 1 est ϕ(d), or au total – x ∈ Hd ⊂ G = hai =⇒ x = ap , xd = e
d X =⇒ x = ap , apd = e
il y a exactement n fraction, donc ϕ(d) = n.
=⇒ x = ap et n divise pd
d divise n
=⇒ x = ap et nd divise p = k nd
n n
=⇒ x = ak d ∈ a d
n n
– Inversement, x ∈ a d =⇒ x = ak d =⇒ xd = ank = e
Problème 2. (Groupes cycliques) =⇒ x ∈ Hd
1) Soit (x, y) ∈ G2 , or G = hai, donc ∃(p, q) ∈ Z2 tel que x = ap , y = aq , b) Soit H un sous groupe de (G, .).
donc x.y = ap+q = y.x. i. Cette question a été déjà traité en TD, les étapes à
2) Posons p = kq, donc x ∈ hap i =⇒ x = aαp = aαkq ∈ haq i. suivre sont les suivantes.

MPSI-Maths DS 3: Arithmétique, groupes cycliques & suites. [Link]

Mrs El Hassani & Mamouni Page 2 sur 4 myismail1@[Link]
 – Montrer que f est un morphisme de groupe. b) Par récurrence.
– En déduire que f −1 (H) est un sous-groupe de (Z, +), c) 0 ≤, δ, uk ≤ 1 =⇒ 1 − δuk ≥ 1 − δ ≥ 0 =⇒
donc de la forme pZ. 1 − δuk
ln xk+1 − ln xk = ln ≥ 0, d’autre part :
– Montrer par double inclusion que H = hap i.  1−δ 
ii. Puisque p ∧ n divise p, alors hap i ⊂ hap∧n i, d’autre part 1 − δuk δ(1 − uk ) δ(1 − uk ) δ
ln = ln 1 + ≤ ≤ (1 − a)q k .
n n 1−δ 1−δ 1−δ 1−δ
card hap∧n i = o(ap∧n ) = = = o(ap )
n ∧ (p ∧ n) p∧n d) Sn+1 − Sn = ln xn+1 − ln xn ≥ 0, donc Sn est croissante, d’autre
= card hap i n−1
X δ
part Sn ≤ (1 − a)q k
6) La surjection découle de la question [Link]), car pour tout 1 − δ
k=0
h ∈ H, ∃d = p ∧ n ∈ Dn tel que H = Hd . δ 1 − qn
L’injection, soit d1 , d2 ∈ Dn , = (1 − a)
1−δ 1−q
Φ(d1 ) = Φ(d2 ) =⇒ H D d1 =
E HdD 2 E , δ 1
n n ≤ (1 − a)
=⇒ a d1 = a d2 1−δ 1−q
donc majorée et par suite converge.
=⇒ o( dn1 ) = o( dn1 )
n n e) Sn est une somme téléscopique, avec Sn = ln xn − ln x0 qui
=⇒ n = converge vers S, donc ln xn = Sn + ln x0 converge vers S + ln x0
n ∧ d1 n ∧ dn2
=⇒ d1 = d2 , d’où xn converge vers µ = eS x0 == eS (1 − a) > 0, donc
donc Φ est bijective. 1 − un
xn = ∼ µ, donc 1 − un ∼ µ(1 − δ)n .
(1 − δ)n
7) Comme Φ est bijective, alors le nombre de sous groupes dans
yk+1 uk+1 1 − uk (1 + δ)n
G, est égale a celui des diviseurs de n = pα , qui sont les 3) a) On a : =
pk tel que 0 ≤ k ≤ α, il y en a exactement α + 1. yk uk 1 − uk+1 (1 + δ)n+1

1 + δ(1 − uk )
=
Problème 3. (Étude d’une suite récurrente) (1 + δ)(1 − δuk )
Préliminaire : Étudier la foction ln(1 + x) − x sur [−1, +∞[. (1 + δ)(1 − δuk ) + δ 2 uk
=
1) a) 1 − un+1 = (1 − un )(1 − δun ). (1 + δ)(1 − δuk )
b) On montre d’abord (facile) par récurrence que 0 ≤ un ≤ 1,
donc (un ) est croissante, car un+1 − un = δun (1 − un ), d’où δ 2 uk
=1+
un ≥ u0 = a. (1 + δ)(1 − δuk )
b) Onremarque d’abord  que :
c) (un ) est croissante, majorée par 1, donc converge versl (1 − a)yn yn
 
a

l tel que 0 = δl(1 − l) or un ≥ δ > 0, donc l ≥ δ > 0, d’où ln = ln − ln
a(1 − un )(1 + δ)n (1 − un )(1 + δ)n 1−a
l = 1.
= ln yn − ln y0
2) a) 1 − un+1 = (1 − δun )(1 − un ) ≤ (1 − δa)(1 − un ), car a ≤ un ≤ 1. = Tn

MPSI-Maths DS 3: Arithmétique, groupes cycliques & suites. [Link]

Mrs El Hassani & Mamouni Page 3 sur 4 myismail1@[Link]
 Donc lim (1 + δ)[ δ ] = et .
n−1 t
X yk+1 nδ 2
Il sufit donc de montrer que 0 ≤ Tn = ln ≤ . δ→0
yk 1 − δ2
c) Posons n = δt , donc nδ 2 = δt δ δ −→ 0,
   

k=0
En effet,
yk+1 δ 2 uk yk+1 nδ 2
=1+ ≥ 1 =⇒ ln ≥ 0 =⇒ Tn ≥ 0. or 0 ≤ Tn = ln yn − ln y0 ≤ , d’où lim yn = y0 , d’autre part
yk (1 + δ)(1 − δuk )  yk 1 − δ2 δ→0
un yn y0
yk+1 δ 2 uk
 yn = n
, donc un = 1 −→ , avec
D’autre part, ln = ln 1 + (1 − un )(1 + δ) yn + (1+δ)n y0 + e−t
yk (1 + δ)(1 − δuk ) a
δ 2 uk y0 = .
≤ 1−a
(1 + δ)(1 − δuk )
δ2 uk (1 − δ)
= 2
.
(1 − δ ) 1 − δuk
Exercice. (Groupe symétrique)
δ2 uk − δuk Vu en TD
= .
(1 − δ 2 ) 1 − δuk
δ2 1) (ασα−1 )α(i1 ) = (ασ)(i1 ) = α(i2 ), et ainsi de suite.
≤
(1 − δ 2 ) 2) (1 3 2)(1 2 3 4)(1 2 3)=(3 1 2 4), prendre α = (1 3 2) et
n−1 n−1
X yk+1 X δ2 δ2 σ = (1 2 3 4).
Donc, Tn = ln ≤ = n .
y k (1 − δ 2) (1 − δ 2)
3) ( 1 2 3 4)2 = (1 3)(2 4) et (1 2 3 4)3 = (1 4 3 2).
   k=0  k=0
   
t t t t t
4) a) ≤ ≤ + 1 =⇒ δ≤t≤ + 1 δ.
δ δ δ δ δ
      
t t t
b) δ≤t≤ + 1 δ =⇒ t − δ ≤ δ ≤ t,
δ   δ δ
t
donc lim δ = t.
δ→0 δ

Fin.
    
[ t
] t t ln(1 + δ)
ln(1 + δ) = δ ln(1 + δ) = δ −→ t.
δ δ δ

MPSI-Maths DS 3: Arithmétique, groupes cycliques & suites. [Link]

Mrs El Hassani & Mamouni Page 4 sur 4 myismail1@[Link]