Cho một chu trình $x \mapsto x^a$ với điểm bắt đầu là $x_1$. Có thể biến đổi một điểm bắt đầu khác $x_2$ để tạo ra cùng một chu kỳ không?

Khi phân tích các trường hợp như thế này, sẽ rất hữu ích nếu xem xét các hành vi theo modulo $P$ và modulo $Q$ một cách riêng biệt, và sau đó xem cách chúng kết hợp. Tôi sẽ thêm vào giả định rằng $P \ne Q$; bạn đã không nói rõ ràng như vậy; Tôi tin rằng nó là hợp lý mà bạn giả định nó.

Khi chúng ta nhìn vào modulo cấu trúc chu kỳ $P$, đầu tiên chúng ta thấy rằng $s_0 \bmod P$ là dư lượng bậc hai modulo $P$ (đó là một cách toán học để nói "nó là một hình vuông"); từ $a$ là gốc nguyên thủy của $p$, thì chúng ta thấy rằng có ba chu kỳ:

• Chu kỳ có độ dài 1 (giá trị 0)

• Một chu kỳ khác có độ dài 1 (giá trị 1)

• Một chu kỳ dài $p-1$; điều này là bởi vì $a^i \bmod p-1$ là các giá trị riêng biệt trong phạm vi $[0, tr-2]$, và $s_0$ có đơn đặt hàng $p-1$ (trong nhóm này, dư lượng bậc hai khác 1 luôn luôn theo thứ tự đó), và vì vậy $s_0^{a^i}$ là $p-1$ những giá trị riêng biệt.

Chúng tôi nhận được kết quả tương tự khi xem xét modulo hành vi $Q$.

Với những điều cơ bản đó, làm thế nào để chúng kết hợp?

Chà, modulo chu kỳ $PQ$ chỉ lặp lại khi cả hai chu kỳ modulo $P$ lặp lại và modulo chu kỳ $Q$ lặp đi lặp lại; nếu $P$-chu kỳ là chiều dài $\alpha$ và $Q$-chu kỳ là chiều dài $\beta$, chu trình hỗn hợp này có độ dài $\text{lcm}(\alpha, \beta)$.

Điều này ngụ ý rằng bất kỳ sự kết hợp nào của hai chu kỳ lớn sẽ có độ dài $\text{lcm}(p-1,q-1)$ (đó là kết quả bạn đã tìm thấy). Và, có $\gcd(p-1,q-1)$ cách mà hai chu kỳ lớn này có thể kết hợp với nhau.

Bây giờ chúng tôi xem xét một sự kết hợp bao gồm một chu kỳ nhỏ; chúng tôi có hai kết hợp với độ dài chu kỳ $p-1$, hai kết hợp với độ dài chu kỳ $q-1$và bốn kết hợp với độ dài chu kỳ 1 (bao gồm $s_0 = 0$ và $s_0 = 1$).

Do đó, tổng số chu kỳ là $\gcd(p-1, q-1) + 8$.

Và, để trả lời câu hỏi của bạn:

Có cách nào để chuyển đổi $x_2$ vì vậy nó sẽ tạo ra chuỗi tuần hoàn giống như $x_1$ làm?

Chà, với bất kỳ số nguyên nào $\beta$, chúng ta có $s_{i+1}^\beta = (s_i^\beta)^a$. Nghĩa là, nếu chúng ta lấy mọi phần tử của một chu trình và nâng nó lên lũy thừa $\beta$, chúng ta vẫn có một chu kỳ.

Vì vậy, nếu chúng ta có giá trị $\beta$ mà $x_2^\beta = x_1$, thì điều đó cho chúng ta một cách để biến đổi chu kỳ này sang chu kỳ khác.

Hóa ra vẫn luôn tồn tại như vậy $\beta$ nếu hai chu kỳ đều lớn (nghĩa là có độ dài $\text{lcm}(p-1, q-1)$). Đối với các chu kỳ suy biến (tất cả các chu kỳ khác), sẽ không có - tuy nhiên, tôi không coi trường hợp đó là thú vị ...

Tất nhiên, việc tìm kiếm một $\beta$ được cho $x_1, x_2$ là một vấn đề không cần thiết nếu $P, Q$ lớn...