Given $1516^{2627} \bmod 13$ I tried several things to find the solution without a calculator, such as examining some powers like $1516^{1} \bmod 13$, $1516^{2} \text{mod} 13$, $1516^{3} \bmod 13$ and so on. I realized the results recurred (in this particular case: $8$, $12$, $5$, $1$ and then $8$ again, so I just had to calculate $1516 \bmod 13^{2627 \bmod 4}=8^3\bmod 13=5$), so I wanted to know: Do the results only recur if you calculate modulo a prime number? Is there any formula to find out after how many steps it will repeat itself? Does this have any relevance in number theory?
$x^y \bmod n$ seems to repeat itself after some steps (when iterating over $n$)
-
0@ThomasA$n$drews That's what I did later (see my solution) anyway, just didn't write it elsewhere to keep things clear ;) And thanks for the answer :P – 2012-11-15
1 Answers
In general, if you start with a number which is co-prime to your modulus, then repeated multiplication will yield a sequence of different numbers until you eventually reach $1$ (in which case it will start repeating). You will always hit $1$ as long as the number is co-prime to your modulus.
What is happening is that you are in essence generating a cyclic subgroup. Suppose you have $a \pmod m$ where $a$ and $m$ are co-prime. Then $a$ is invertible and each $a^k$ is invertible. Because the set of numbers modulo $m$ is finite (there's only $m$ of them) the sequence $\{a,\ a^2,\ a^3,\ \cdots\}$ will eventually run into a repetition in the form of $a^k \equiv a^\ell$ where without loss of generality $k < \ell$. That means $a^{\ell - k}\equiv 1$ so there will eventually be a power of $a$ which is $1$. We call the smallest such exponent the order of $a$ modulo $m$.
When $a$ is not co-prime to $m$, then we can still have repetition, but we will never hit $1$ because $a$ will not be invertible.
Something particularly interesting happens when $m = p$ is prime. The numbers modulo a prime base forms a cyclic group. What this means is that there will be some element $a$ such that the powers of $a$ generates all $p-1$ non-zero elements of the group. This is a very useful fact because of the structure that it imposes onto the numbers.
There are a limited number of candidates to try for the order when calculating it. If $k$ is the order of an element modulo $m$, then $k$ must divide $\varphi(m)$ where $\varphi$ is Euler's totient function. There are probably more efficient algorithms, but this already reduces the computational effort by quite a bit.
So the bottom-line is: Yes, this has tremendous relevance to number theory (and also group theory).