Dat un ciclu $x \mapsto x^a$ cu punctul său de plecare $x_1$. Poate fi transformat un alt punct de plecare $x_2$ pentru a genera același ciclu?

În analiza unor astfel de cazuri, este util să ne uităm la comportamentele modulo $P$ și modulo $Q$ separat și apoi vedeți cum se combină. Voi adăuga în ipoteza că $P \ne Q$; nu ai spus-o în mod explicit; Cred că este rezonabil că ai presupus asta.

Când ne uităm la structura ciclului modulo $P$, vedem mai întâi asta $s_0 \bmod P$ este un rest patratic modulo $P$ (care este un mod matematic de a spune „este un pătrat”); de cand $a$ este o rădăcină primitivă a $p$, atunci vedem că există trei cicluri:

• Un ciclu de lungime 1 (valoarea 0)

• Un alt ciclu de lungime 1 (valoarea 1)

• Un ciclu de lungime $p-1$; asta pentru ca $a^i \bmod p-1$ sunt valori distincte în interval $[0, p-2]$, și $s_0$ are ordine $p-1$ (în acest grup, resturile pătratice altele decât 1 sunt întotdeauna aceeași ordine), și așa $s_0^{a^i}$ sunt $p-1$ valori distincte.

Obținem rezultate similare pentru modul de comportament $Q$.

Având în vedere aceste elemente de bază, cum se combină?

Ei bine, modulul ciclului $PQ$ se repetă numai când atât ciclul modulo $P$ se repetă și modul ciclului $Q$ se repetă; dacă $P$-ciclul este lungimea $\alpha$ si $Q$-ciclul este lungimea $\beta$, acest ciclu combinat are lungime $\text{lcm}(\alpha, \beta)$.

Aceasta înseamnă că orice combinație a celor două cicluri mari va avea lungime $\text{lcm}(p-1,q-1)$ (care este un rezultat pe care l-ați găsit deja). Și sunt $\gcd(p-1,q-1)$ moduri în care aceste două cicluri mari se pot combina.

Considerăm acum o combinație care include un ciclu mic; avem două combinații cu lungimea ciclului $p-1$, două combinații cu lungimea ciclului $q-1$, și patru combinații cu lungimea ciclului 1 (care include $s_0 = 0$ și $s_0 = 1$).

Prin urmare, numărul total de cicluri este $\gcd(p-1, q-1) + 8$.

Și, pentru a răspunde la întrebarea ta:

Există vreo modalitate de a se transforma $x_2$ deci va produce aceeași succesiune ciclică ca $x_1$ face?

Ei bine, pentru orice număr întreg $\beta$, avem $s_{i+1}^\beta = (s_i^\beta)^a$. Adică dacă luăm fiecare element al unui ciclu și îl ridicăm la putere $\beta$, mai avem un ciclu.

Deci, dacă avem valoarea $\beta$ pentru care $x_2^\beta = x_1$, atunci asta ne oferă o modalitate de a transforma un ciclu în altul.

Se dovedește că întotdeauna există o astfel de $\beta$ dacă cele două cicluri sunt ambele mari (adică de lungime $\text{lcm}(p-1, q-1)$). Pentru ciclurile degenerate (toate celelalte), nu vor exista - totuși, nu consider acest caz atât de interesant...

Desigur, găsirea unui astfel de $\beta$ dat $x_1, x_2$ este o problemă nebanală dacă $P, Q$ sunt mari...