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.

I was doing a question yesterday on very elementary number theory, and I came across this pattern.

$2^1=2 \pmod {13}$

$2^2=4 \pmod {13}$

$2^3=8 \pmod {13}$

$2^4=3 \pmod {13}$

$2^5=6 \pmod {13}$

$2^6=12 \pmod {13}$

$2^7=11 \pmod {13}$

$2^8=9 \pmod {13}$

$2^9=5 \pmod {13}$

$2^{10}=10 \pmod {13}$

$2^{11}=7 \pmod {13}$

$2^{12}=1 \pmod {13}$

$2^{13}=2 \pmod {13}$

I noticed the remainder always is unique for every block multiples of powers 13. And it repeats!.

Also I tried this for base 3 and base 4 base 5. All showed similar patterns.

Why?

share|improve this question
    
Please see en.wikipedia.org/wiki/Fermat%27s_little_theorem –  wj32 Oct 20 '12 at 6:48
1  
By Fermat's Theorem, if $a$ is not divisible by the prime $p$, we have $a^{p-1}\equiv 1\pmod{p}$. So there is cycling with period at most $p-1$. –  André Nicolas Oct 20 '12 at 6:48
3  
Take any positive integers $a$ and $m$. Consider the remainders when we divide $a^0, a^1,a^2,a^3,\dots$ by $m$. There are at most $m$ possible remainders, so for some $d$, $e$ the remainders of $a^d$ and $a^e$ are the same. From then on there must be cycling. There might be an initial non-cycling part. If $a$ is relatively prime to $m$, then since $a^d\equiv a^e\pmod{m}$, we can cancel and get $a^{e-d}\equiv 1\pmod{m}$. It is not hard to show that then there is pure cycling. –  André Nicolas Oct 20 '12 at 7:00
    
(Just a nitpick @Andre): the conclusion from "there are at most m possible remainders" to "cyclicitiness" seems to be taken too immediate in my view. Consider the pattern in $1,-1,-1,1,\ldots $ indicated by the Thue-morse sequence then there is aperiodicity although we need only two residue classes. I think, the conclusion of cyclicitiness should always be founded on arguments like the second one of yours, that the remainders of $a^k$ and $a^{k+m}$ for some fixed m are the same after a finite index k. –  Gottfried Helms Oct 20 '12 at 8:30
    
@GottfriedHelms: I was writing a comment in the context of the OP's computational experience with a specific process, where the OP had recognized that there would be nothing new after the first repeat. –  André Nicolas Oct 20 '12 at 10:49

2 Answers 2

up vote 2 down vote accepted

The group of invertible classes modulo a prime $p$, i.e.:

$\Bbb F_p^\times := \{x \in \Bbb Z/ p \Bbb Z: \exists y: xy \equiv 1\}$

has cardinality $\phi(p) = p-1$, where $\phi$ is the Euler phi function. Thus, we see that the order of every element is a divisor of $p-1$ (by Little Fermat).

That $2$ has order $p-1$ in the cases you have tried is a coincidence. E.g. $p = 31$ will not work, for $2^6 \equiv 32 \equiv 1$, but $\Bbb F_{31}^\times$ has order $30$, so $2$ is not a generator.

share|improve this answer
    
Wow. That is pretty deep. Is there a way to understand this simpler? I only just learned the concept of muduolo –  Yellow Skies Oct 20 '12 at 6:53
    
We can discuss it in this chat room if you like. –  Lord_Farin Oct 20 '12 at 7:02
    
I have problems logging into the chatroom. Error message : No referer was present - this may be due to a browser setting. I guess its ok thanks for offering me help farin! Back to proper school work now. –  Yellow Skies Oct 20 '12 at 7:09

Simpler answer: For all these modulo questions, it is enough to find some exponent that gives a modulo of 1. Consider

$2^n = 1 (mod 13)$ for some n. Then $2^{n + 1} = 2 (mod 13)$ which is same as $2^{0 + 1} = 2 (mod 13)$ and $2^{n + 2} = 4 (mod 13)$ which is $2^{1 + 1} = 4 (mod 13)$, in other words, they repeat. And also, notice that, if $2^n = k (mod 13)$ and $2^m = k (mod 13)$, then $2^{n - m} = 1 (mod 13)$ also. Since there are only 13 numbers below 13 that could be modulos, it is bound to repeat after some exponent n.

Salahuddin

http://maths-on-line.blogspot.in/

share|improve this answer

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.