Devoir surveillé No2
Samedi 12 octobre 2002
- Durée : 4 heures -
Les deux exercices et les deux problèmes sont totalement indépendants. Il est demandé de
rédiger les deux exercices et le premier problème sur un premier ensemble de copies relevé au
bout de trois heures trente minutes. Le second ensemble de copie relevé au bout des quatre heures
portera la rédaction du second problème.
On prendra bien soin de préciser toute notation non donnée dans l’énoncé. Toute affirmation
devra être justifiée. Les récurrences ne sauraient être commencées sans une formulation claire
de l’hypothèse de récurrence.
Il n’est pas interdit d’admettre certains éléments de démonstration (voire des questions
entières) afin de ne pas rester bloqué. Mais ils doivent absolument être mentionnés.
On laissera une marge à gauche.
Il est demandé de ne pas recopier l’énoncé, on mettra seulement en évidence les numéros
des questions traitées. Il est recommandé par contre d’annoncer ce qui va être démontré et
éventuellement par quel type de raisonnement (récurrence, absurde, contraposée...). Seules les
conclusions et les résultats mis en valeur seront pris en compte.
Enfin, les solutions doivent être rédigées et le formalisme utilisé avec parcimonie. La
présentation et la rédaction pourront représenter jusqu’à 15% de la note obtenue.
Exercice 1 : Morphismes de Z/nZ dans Z/mZ
1) Soient G, H deux groupes finis, a ∈ G, f : G −→ H un morphisme de groupes. Montrer
que l’ordre de f (a) dans H divise celui de a dans G.
2) On considère Z/nZ et Z/mZ muni de leur structure de groupes (n, m 2) et f :
Z/nZ −→ Z/mZ un morphisme de groupes. On note d l’ordre de x = f (1̄).
a . Montrer que d divise n et m.
b . Que peut-on dire de f lorsque n et m sont premiers entre eux (i.e. sans autre diviseur
positif commun que 1) ?
c . Exhiber un élément d’ordre d de Z/mZ.
3) Soit d un diviseur positif commun à n et m, x un élément d’ordre d dans Z/mZ.
Construire un morphisme de groupes f : Z/nZ −→ Z/mZ tel que f (1̄) = x.
Exercice 2 : Inversion binômiale
On admet dans cet exercice qu’étant données deux familles de Q, (an )n∈N et (bn )n∈N à
support fini pour +, le fait que
an x n = bn x n ,
n∈N n∈N
pour tout x ∈ Q, entraine que an = bn pour tout n ∈ N.
n
1) Soit x ∈ Q. En factorisant l’expression Cnk (x−1)k , puis en la développant, démontrer
k=0
que
n
0 si k < n
(−1)k−l Cnk Ckl =
k=l
1 si k = n
2) Soit (un )n∈N et (vn )n∈N deux suites de Q. Démontrer l’équivalence des propositions
suivantes
n
(i) pour tout n ∈ N, vn = Cnk uk ;
k=0
n
(ii) pour tout n ∈ N, un = (−1)n−k Cnk vk .
k=0
Problème : Le théorème de Frobénius
CardG
Soient G un groupe fini de cardinal n, H un sous-groupe de G. On suppose que =p
CardH
où p est le plus petit nombre premier divisant CardG (en particulier, si k 0 divise CardG,
k = 1 ou k p).
On note G/H l’ensemble des parties de G qui s’écrivent xH = {xh, h ∈ H} avec x ∈ G.
1) Soit x, y ∈ G. Démontrer que si xH et yH ont un élément en commun, xH = yH.
2) Démontrer que G/H constitue une partition de G.
Pour a, b ∈ G/H avec a = xH (x ∈ G), on note a ∼ b lorsqu’il existe g ∈ H tel que
b = (gx)H.
3) Démontrer que ∼ est une relation d’équivalence.
On note Ω1 , . . . , Ωr les classes déquivalences de G/H pour ∼. On choisit pour 1 i r,
xi ∈ G tel que xi H ∈ Ωi .
4) On suppose que Ω1 est la classe de 1H = H. Quel est le cardinal de Ω1 ?
5) Soit 1 i r. On considère f : H −→ Ωi qui à g ∈ H associe gxi H.
a . Démontrer que K = f <−1> ({xi H}) = {g ∈ H, gxi H = xi H} est un sous-groupe de H.
b . Soit g0 ∈ H. Démontrer que f <−1> ({g0 xi H}) = g0 K.
CardH
c . En déduire que CardΩi = .
CardK
6) Démontrer que toutes les parties Ωi sont de cardinal 1.
7) Conclure que H est un sous-groupe distingué i.e. pour tout x ∈ G,
xHx−1 ⊂ H.
Problème : Loi sur les parties finies de Z
Une suite arithmétique de raison r est une suite (xn )n∈N de Z telle que xk+1 = xk + r pour
tout k 0.
Une suite arithmétique finie de raison r est une suite (x0 , . . . , xn ) de Z telle que xk+1 = xk +r
pour tout 0 k n.
On note S l’ensemble des parties finies de Z.
Si S1 et S2 sont deux parties finies de Z, on note
S1 + S2 = {x1 + x2 , x1 ∈ S1 , x2 ∈ S2 }.
Étant donnée une partie finie de S, on note
n ∗ S = S + S +
· · · + S .
n termes
Par contre, nS désigne la partie {nx, x ∈ S}.
Enfin, pour a ∈ Z, on pose a + S = {a} + S.
I. Questions préliminaires.
1) Montrer que la loi + définie plus haut confère à S la structure de monoı̈de commutatif.
2) Est-il vrai que toute partie finie de Z est régulière ? (A est dite régulière si pour tout B
et C dans S, A + B = A + C entraine B = C)
3) a . On se donne deux suites finies arithmétiques (x0 , . . . , xn ) et (y0 , . . . , ym ) de Z de
même raison r. On note A = {x0 , . . . , xn } et B = {y0 , . . . , ym } les supports de ces suites.
Calculer Card(A + B) en fonction de CardA + CardB.
b . On note A1 , A2 , . . . , An le support de n suites arithmétiques finies de même raison r.
Calculer le cardinal de A1 + · · · + An en fonction de CardA1 + · · · + CardAn .
II . Cardinal de 2 ∗ S.
Dans cette partie, S désigne une partie finie non vide de Z de cardinal q. On note a1 < a2 <
. . . < aq les éléments de S.
1) En considérant l’ensemble
{2a1 , a1 + a2 , 2a2 , a2 + a3 , 2a3 , . . . , aq−1 + aq , 2aq },
établir que Card(2 ∗ S) 2CardS − 1.
2) On suppose réalisée l’égalité Card(2 ∗ S) = 2CardS − 1. Montrer en considérant les
nombres ai−1 + ai+1 que S est une progression arithmétique (i.e. l’ensemble des termes d’une
suite arithmétique finie).
III . Cardinal de S + T
Soient S et T deux parties finies non vides de Z, p = CardS, q = CardT . On supposera
p q et on notera a1 < a2 < . . . < ap les éléments de S et b1 < b2 < . . . < bq ceux de T .
1) En considérant l’ensemble
{a1 + b1 , a2 + b1 , a2 + b2 , a3 + b2 , . . . , ap + bp−1 , ap + bp , ap + bp+1 , . . . , ap + bq },
établir l’inégalité Card(S + T ) CardS + CardT − 1.
2) On suppose Card(S + T ) = CardS + CardT − 1.
a . Établir que
a1 + b2 = a2 + b1
a2 + b3 = a3 + b2
..
.
ap−1 + bp = ap + bp−1
ap−1 + bp+1 = ap + bp
ap−1 + bp+2 = ap + bp+1
..
.
ap−1 + bq = ap + bq−1 .
b. Soit T = {b1 , b2 , . . . , bp }. Montrer que T = (b1 −a1 )+S. En déduire que Card(2∗S) =
2p − 1.
c . Montrer que S et T sont des progressions arithmétiques de même raison.
IV . Cardinal de S1 + · · · + Sp
Soient S1 , . . . , Sp des parties finies non vides de Z.
1) En faisant une récurrence sur p, établir l’inégalité
Card(S1 + · · · + Sp ) CardS1 + · · · + CardSp − (p − 1).
2) On suppose p 2. Montrer que si
Card(S1 + · · · + Sp ) = CardS1 + · · · + CardSp − (p − 1),
alors les Si sont des progressions arithmétiques.