EX 1

a) Initialisation : immédiat, si $u=v=𝜀$

b) Hérédité :

Sans perte de généralité : $|u|\le |v|$ :

• Si $u=𝜀$ : immédiat
• Sinon :

$v\stackrel{\scriptscriptstyle\mathrm{def}}{=}u{v}^{\prime }$, et $uu{v}^{\prime }=u{v}^{\prime }u$

d’où

$u{v}^{\prime }=v^{\prime }u$ et par hypothèse de réc, il vient que : il existe un mot $w$ tq :

• $u=w^n$
• $v^{\prime }=w^m$

donc $v=w^{n+m}$, et le résultat est acquis.

EX 2

On remarque que si $|u|=|v|$, $n=m$, et $u=v$.

( Par réc sur $|u|+|v|$ : il existe un mot $w$ tel que

a) Initialisation : immédiat, si $u=v=𝜀$

b)

• Si $u=𝜀$ : immédiat
• Sinon :

Sans perte de généralité : $|u|<|v|$, donc $m>n$.

De plus, on peut supposer que $|u|\wedge |v|=1$, car sinon : $u^m=v^n$ et il vient que $u^{n^{\prime }}=v^{m^{\prime }}$ ) _____

• Sans perte de généralité : $|u|<|v|$, donc $m>n$.

• Supposons que $|u|\wedge |v|=1$

Bézout ⟶ $\exists a,b\in \mathbb{N};a|v|-b|u|=1$, avec

• $a<|u|$
• $b<|v|$

Pour toute lettre $w_i$ ($i<|v|$ )

$w_i=w_{i+a|v|}=w_{i+a|v|-b|u|}=w_{i+1}$

NB : $w_{i+a|v|-b|u|}$ reste une lettre, car :

$i+a|u|\le (a+1)|u|\le |u||v|\le |w|$ car $|u|,|v|/|w|$ et $|u|\wedge |v|=1$

donc $\exists a\in 𝛴;u,v,w\in a^{\ast }$

Puis, dans le cas général, on trvaille sur l’alphabet : on pose $A_{a_1\cdots a_d}\stackrel{\scriptscriptstyle\mathrm{def}}{=}{a}_1\cdots a_d,\dots$

on ne s’écrit qu’avec une seule lettre sur cet alphabet, d’où :

EX 3

⟹ : $z=x$

⟸ :

• Si $|u|\ge |z|$ : $u=zx$ et $v=xz$ (par l’identité dont on dispose)

• Si $|z|>|u|$ : Par réc sur la taille de $z$ :

$z=ux$ et $z=xv$ ⟶ HR : $u$ et $v$ conjugués, car $|x|<|z|$

EX 5

Soit $M$ un monoïde fini.

C’est le quotient du monoïde $M^{\ast }$ par la relation d’équivalence “$u$ et $v$ ont la même image par le morphisme de monoïde qui envoie les lettres sur les lettres”

EX 6

1) Principe des tiroirs.

2)

a) évident, sinon $x^{j-i}$ contredit la minimalité de $l$ (où $0\le i<j\le l-1$ vérifient $x^i=x^j$)

b) évident, par division euclidienne des exposants par $l$

c) $x^p{x}^r=x^{p+r}=x^{p+l-k}=x^l{x}^{p-k}=x^k{x}^{p-k}=x^p$

est un homomorphisme de $Ker$ trivial : isomorphisme.

d) $x^r$ est idempotent, et c’est le seul car c’est un groupe (un seul idempotent : le neutre).

EX 11

1)

Existence :

On considère les orbites de l’action définie précédemment :

et :

Unicité :

Si $𝜎=\prod _i{𝛾}_i=\prod _i{𝜎}_i$ sont des décompositions en cycles à support disjoints,

alors pour toute orbite $O$, il existe $i,j$ tq ${𝛾}_i=O={𝜎}_j$

2) C’est le ppcm des ordres des cycles.

3) C’est le max des ppcm des toutes les décompositions de l’entier 6 :

• 1, 2, 3
• 2, 2, 2
• 6

$o{r}_{max,{𝕾}_6}=6$

4) On dessine le graphe de $𝜎$ : les cycles du graphe sont les cycles de la décomposition de $𝜎$.

a) b) 8

EX 12

1)

M1 :

Tout cycle s’écrit en produit de transpositions.

2) M2 :

Par réc sur $n$

• Initialisation : immédiate pour $n=2$

• Hérédité :

  • Si $𝜎(n+1)=n+1$ : on se ramène au cas précédent
  • Sinon, on multiplie $𝜎$ par $(𝜎(n+1),n+1)$ et on se ramène au point précédent.

$(1,n) = ()

3)