0
$\begingroup$

In RSA clock arithmetics is used, and as Fermat's little theorem says, $a^p \bmod p = a$. The exponentiation is cyclical, $a^x = a^{x \bmod p-1} \bmod p$, the same sequence of numbers is repeated in each cycle. Is there in a similar way a cycle for all modular exponentiation, or, only for some cases like prime modulo?

$\endgroup$

1 Answer 1

0
$\begingroup$

Yes, if $\gcd(a,n)=1$. Otherwise, we still reach a cycle, but it might not get back where it started.

For all integers $n>0$, $a$, $x$

  • when $\gcd(a,n)=1$, it holds $a^x\equiv a^{(x\bmod\lambda(n))}\pmod n$. The sequence $a_j$ defined as $a_0=1$, $a_{j+1}=a\cdot a_j\bmod n$ loops back at $1$, then $a\bmod n$.
    $\lambda$ is the Carmichael function, with $1\le\lambda(n)<n$ for all $n>1$.
    The smallest period of $a_j$ depends on $a$ and $n$. It it some divisor of $\lambda(n)$, called the order of $a$ modulo $n$. It is $1$ when $a\equiv1\pmod n$. It is $2$ for $a=n-1$ and $n>1$.
  • when $\gcd(a,n)\ne1$, the sequence $a_j$ is ultimately periodic with a period dividing $\lambda(n)$, but the head of the sequence might not be part of the period. E.g. $a=2$, $n=12$, $a_0=1$, $a_1=2$, $a_2=4$, $a_3=8$, $a_4=4$.
$\endgroup$
4
  • $\begingroup$ Thanks, very good answer. Could I ask just in the context of trying to understand cyclical nature of modular exponentiation, is 𝜆(n) the point where the cyclical group for every integer a between 1 and n has looped? $\endgroup$
    – mimesis
    May 19, 2019 at 16:23
  • 1
    $\begingroup$ "$a^x\equiv a^{(x\bmod\lambda(n))}\pmod n$ holds for all positive integers $a$, $x$, $n$"; counterexample: $a=2, x=2, n=4$ :-) $\endgroup$
    – poncho
    May 19, 2019 at 17:06
  • $\begingroup$ Ok it was in the answer already. I missed it, probably because I am learning and a lot to take in, jumping between this answer and Wikipedia. Thanks for helping me along the way. $\endgroup$
    – mimesis
    May 19, 2019 at 17:09
  • $\begingroup$ @poncho: thanks for the correction. $\endgroup$
    – fgrieu
    May 19, 2019 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.