Si j'ai bien compris ton "calcul", la traduction mathématiques des valeurs de ta variable s correspond à la suite :
\( s_0=s \) et, pour \(n \in \mathbb{N}\), \(s_{n+1}= \text{ reste de }ms_n \text{ divisé par }p\)
Et ensuite tu te demandes : est-ce que \(s_{p-1} \text{ ou }s_p=s_0\) ? C'est bien ça ?
Si c'est bien le cas, on remarque que \(s_n\) est congru mod \(p\) à \(m^ns_0\)
Or, si \(p\) est premier, comme \(m\) n'est pas un multiple de \(p\), d'après le petit théorème de Fermat, on a \(m^{p-1}\equiv 1\) mod \(p\) d'où ton résultat : au bout de \(p-1\) opérations, on retombe sur la valeur initiale
Maintenant, si \(p\) n'est pas premier, je te laisse chercher la généralisation du théorème de Fermat avec la fonction indicatrice d'Euler : dans ce cas, pour retomber sur le nombre initial, ton \(m\) doit être premier avec \(p\) et le nombre d'opération ne sera plus \(p-1\) mais \(\varphi(p)\) (indicatrice d'Euler de \(p\)).
Pour ta question finale, je ne vois pas trop de quel ensemble tu parles...
Je n'avais pas saisi que tu cherchais le premier moment auquel tu revenais exactement au nombre initial !
Par contre, désolé d'insister, mais pour p premier, le petit théorème de Fermat te dit qu'au bout de p-1 opérations, tu reviens bien à ton nombre initial ! Relis dans mon post précédent la définition de la suite qui correspond à ta variable, il s'agit exactement de ta "suite" s, s', s'' !!
Mais effectivement, ce théorème ne dit pas si ta suite revient au nombre initial avant p-1 opérations !
Donc rentrons un peu dans la théorie (je suppose \(p\) premier et \(m\) compris entre 1 et p-1) : ton problème revient à chercher le premier \(n \in \mathbb{N}^*\) tel que \(m^n \equiv 1 \text{ mod }p\). En théorie des groupes, cela revient à chercher l'ordre \(n\) de \(m\) dans le groupe \((\mathbb{Z}/p\mathbb{Z})^{\times}\) des inversibles de l'anneau \(\mathbb{Z}/p\mathbb{Z}\).
Comme ce groupe est de cardinal \(p-1\) (car \(p\) est premier), on sait, d'après le théorème de Lagrange, que le nombre cherché \(n\) divise \(p-1\) (tu remarqueras au passage que ton 8 divise bien 257-1=256). On vient d'ailleurs de démontrer le petit théorème de Fermat
Donc forcément, ton nombre d'étapes \(n\) sera un diviseur de \(p-1\) ! Et ta question est, quand peut-on dire que \(n=p-1\) : dans le langage "groupien", cela revient à dire que l'ordre de \(m\) est égal à \(p-1\) et donc que \(m\) est un générateur de \((\mathbb{Z}/p\mathbb{Z})^{\times}\) !
Et j'ai le malheur de t'annoncer que c'est un problème très difficile dans le cas général ! Je ne connais pas de méthode simple et systématique de caractérisation des générateurs de \((\mathbb{Z}/p\mathbb{Z})^{\times}\) - qu'on appelle également élément primitif de \(\mathbb{F_p}=\mathbb{Z}/p\mathbb{Z}\) si ça peut t'aider dans tes recherches.
Mais si quelqu'un connaît un méthode accessible pour cela je suis preneur
Edit : A oui, au passage, ce que tu appelles "sous-intervalle des nombres de 0 à p-1" a bien un nom et une notation (que j'emploie plus haut) c'est l'anneau \(\mathbb{Z}/p\mathbb{Z}\) (qui est un corps si p est premier) obtenu par quotient du groupe des entiers relatifs \(\mathbb{Z}\) par son sous-groupe \(p\mathbb{Z}\) et en le munissant d'opérations plus et fois définies à partir des plus et fois des entiers et des propriétés des congruences.
Re-edit : petit remarque dans cette recherche des \(m\) qui conviennent pour un \(p\) premier (c'est à dire les \(m\) tel que tu retombes sur tes pattes après EXACTEMENT \(p-1\) opérations) :
si tu en trouves un, disons \(m_0 \), (par exemple pour \(p=65537\) tu as trouvé un \(m_0\) égal à \(75\)); et bien tu peux trouver exactement tous les autres \(m\) qui fonctionnent !
Il s'agit des \(m=m_0^{k}\%p\) où \(1\leq k \leq p-1\) et \(k\) premier avec \(p-1\) (Il y a donc \(\varphi(p-1)\) nombre \(m\) qui conviennent).
Ce n'est pas très satisfaisant car il reste le problème de trouver un \(m_0\) pour démarrer, et c'est cette étape qui n'est pas simple mathématiquement parlant !
C'est un fait expérimental que je retourne au nombre initial en un nombre d'étapes qui est un diviseur de p-1.
Et je vais forcément y retourner après p-1 étapes.
Ma problématique était justement que ce nombre doit être exactement p-1.
Dans ce cas précis, la suite des valeurs s, s' s", etc. passe par tous les nombres de l'intervalle [1, p-1] dans un ordre quelconque.
C'est le principe de plusieurs générateurs de nombres pseudo-aléatoires.
Pour reprendre mon exemple où p=257 et m=15, j'ai changé m de 15 à 14 et mon cycle est passé de 32 à 256.
Le but de ce post était justement de savoir s'il existe une règle pour me dire comment trouver de tels nombres.
D'après ce que je comprend, il n'existe pas, à priori, une telle règle.
Le Tout est souvent plus grand que la somme de ses parties.
Groupe cyclique modulo p
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.