Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
You can use \mod,\bmod,\pmod in LaTeX. –  Asaf Karagila Nov 15 '12 at 13:54
    
If $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}$. –  Thomas Andrews Nov 15 '12 at 14:14
1  
The 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.) –  Thomas Andrews Nov 15 '12 at 14:16
    
@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 –  Peter Nov 15 '12 at 14:37
add comment

1 Answer

up vote 4 down vote accepted

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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