Etant donné que ça n'a pas l'air d'emballer grand monde, je vais reprendre l'exercice depuis le début.
Un mot U de longueur n est une suite
de lettres. On dit qu'il est k-périodique si pour tout i tel que
on a
.
a)Montrer que si un mot de longueur 4 est à la fois 2-périodique et 3-périodique, il est constant, cad que toutes ses lettres sont égales.
Le mot est 2-périodique donc
.
donc
et .
Le mot est 3-périodique donc
.
donc
.
Donc
.
Donc le mot est constant. b)Soient a et b deux entiers premiers entre eux. Montrer que la suite
d'éléments de
prend une fois et une seule chaque valeur non nulle. Pour
,on définit
comme le représentant de
tel que
.
Montrons tout d'abord que a et a+b sont premiers entre eux: Soit d=pgcd(a,a+b)
On a: d|a et d|(a+b) donc
On prend m=-1 et n=1
On a d|((a+b)-a)
cad
d|b.
d|a et d|b donc d|pgcd(a,b)=1
donc
a et a+b sont premiers entre eux.On en déduit directement que
est générateur du groupe cyclique
.
Démonstration de la question posée: La suite
est une suite d'éléments de
et possède exactement a+b-1 éléments.
Comme
est générateur de
,
possède tous les éléments non nuls de
(puisque a et b sont premiers entre eux donc
, et on a
).
Pour résumer, la suite possède exactement a+b-1 éléments et possède chaque éléments compris entre 1 et a+b-1 (inclus) donc cette suite prend bien une fois et une seule chaque valeur non nulle de
.
c) Montrer que si U est un mot de longueur a+b-1 qui est à la fois a-périodique et b-périodique, on a
.
En déduire que U est constant.
Première partie: JE BLOQUE.... :marteau:
Deuxième partie: On déduit de la question précédente que
donc
.
Toutes les lettres sont égales donc U est constant.
d)Démontrer le théorème de Fine et Wilf: Soient a et b deux entiers naturels, et d leur pgcd. Si U est un mot a-périodique et b-périodique de longueur au moins a+b-d, alors u est d-périodique.
Prenons une lettre toutes les d lettres dans U (une lettre sur d). On a alors d mots de longueur a/d +b/d -1 constants d'après la question précédente, ce qui signifie que U est d-périodique puisqu'on a pris une lettre sur d.