Arithmétique et compteurs

[invite3f535f29]

Bonjour à tous,

Voilà un problème auquel je suis confronté dans le cadre d'un stage que j'effectue durant cet été. Je précise que je n'ai pas de formation en Mathématiques. J'espère qu'une âme généreuse ici sur ce forum pourra me venir en aide.

Le problème est en fait assez simple, j'ai un compteur se remettant à 0 modulo un certain nombre L.
Par exemple pour L = 8, le compteur fait 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 1 .. et ainsi de suite
.
A partir de ce compteur, je dois sélectionner un échantillon tous les M coups ( par exemple pour le compteur avec L = 8 et pour M = 3 la suite extraite est 0 3 6 1 4 7 2 5 0 3 6 .. et ainsi de suite).

J'aimerais savoir si il existe une relation générale entre le nombre L, le nombre M et le nombre de coups du compteur qu'il faut attendre avant que la suite ne se repète.
Par exemple dans le cas ci-dessus, pour L = 8 et M = 3. il y a 7 occurences du compteur avant que celui-ci ne repasse par la valeur 0.

Voilà si quelqu'un à une idée.

Merci beaucoup à tous,

Florian
-----

[Seirios]

Bonjour,

Au final, tu cherches le plus petit k tel que , c'est-à-dire le plus petit k tel que L divise kM. Tu as donc .

[invite029139fa]

Simple question avant de tenter d'étudier le problème : M peut-il être supérieur à L ?

[invite9617f995]

Bonjour,

Pour extraire notre suite on prend un nombre tous les M nombres, donc le k-ième nombre que l'on prend est le M*k-ième nombre de notre liste modulo L. Or cette liste commence à 0 donc le k-ième nombre que l'on prend est M*k [L] (ce qui signifie M*k modulo L), sachant que je considère que le premier chiffre que l'on prend est en fait le 0-ième.

Il y a alors 2 cas :
- L et M sont premiers entre eux, dans ce cas là M*K = 0 [L] équivaut à k = 0 [L] et donc k va prendre les L valeurs différentes entre 0 et L avant de reboucler sur 0 (comme dans le cas L=8 et M=3)
- L et M ne sont pas premiers entre eux, on note p=pgcd(M,L), il existe donc m et l premiers entre eux tels que M=p*m et L=p*l. On a alors M*k = 0 [L] <=> p*m*k = 0 [p*l] <=> m*k = 0 [l] or m et l sont premiers entre eux donc on a k = 0 [l] donc la suite va prendre l valeur différentes avant de reboucler sur 0.

Donc en résumé le nombre que tu cherches est l=L/p où p est le pgcd de M et L (la formule marche aussi lorsque M et L sont premiers entre eux car dans ce cas, pgcd(M,L)=1).

J'espère avoir été clair,
Silk


Edit : grillé par phys2

[A voir en vidéo sur Futura]

[invite029139fa]

Par exemple dans le cas ci-dessus, pour L = 8 et M = 3. il y a 7 occurences du compteur avant que celui-ci ne repasse par la valeur 0.

Plutôt 8 en fait.

[Seirios]

Simple question avant de tenter d'étudier le problème : M peut-il être supérieur à L ?

Cela reviendrait au même de considérer M ou la classe de M modulo L, donc on peut considérer que M est plus petit que L.

[invite3f535f29]

Merci à toi pour ta réponse courte, claire et rapide !

[invite3f535f29]

et aussi à Silk78 pour sa réponse un peu plus longue mais tout aussi claire