2
$\begingroup$

This feels like it should be elementary but it came up in my research and I was not able to solve it.

We can ask this question for any $p$ and $q$ but,let $p$ and $q$ be primes for simplicity. The sequence $$ ((a^n \text{ mod } p) \text{ mod } q)$$ is periodic. What is its period?

Can you find a characterization in terms of $a,p,q$? Clearly, it depends on the order of $a$ in $p$. If $p$ is less than $q$ the problem is trivial.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Clearly, the period divides the order of $a$ mod $p$. In most cases, they will be simply equal, but there may be some special choices of $a,p,q$ when the period is a proper divisor of the order. $\endgroup$
    – Max Alekseyev
    Commented Aug 24, 2023 at 13:19

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .