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$)
-
0You can use `\mod,\bmod,\pmod` in LaTeX. – 2012-11-15
-
0If $x_1 \equiv x_2\pmod n$ then $x_1^y\equiv x_2^y\pmod n$. So you can first note that $1516\equiv 8\pmod {13}$. – 2012-11-15
-
1The periodicity you are seeing is correct. If $x$ is any integer, then the sequence $x^1\pmod {13},x^2\pmod {13},x^3\pmod {13},...,x^k\pmod {13},...$ always has periodicity which is a divisor of 12. (For general module any prime, $p$, the periodicity will be a divisor of $p-1$. This is called Fermat's Little Theorem.) – 2012-11-15
-
0@ThomasAndrews 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).