1
$\begingroup$

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?

  • 0
    Please see http://en.wikipedia.org/wiki/Fermat%27s_little_theorem2012-10-20
  • 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$.2012-10-20
  • 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.2012-10-20
  • 0
    (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*.2012-10-20
  • 0
    @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.2012-10-20
  • 0
    @GottfriedHelms All you need is that $a≡c$ and $b≡d \mod m$ implies $ab≡cd$. $c=a+me,d=b+mf,cd=ab+(be+af+mef)m$ [corrected for careless typo]2012-10-20

2 Answers 2

2

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.

  • 0
    Wow. That is pretty deep. Is there a way to understand this simpler? I only just learned the concept of muduolo2012-10-20
  • 0
    We can discuss it in [this chat room](http://chat.stackexchange.com/rooms/info/6184/) if you like.2012-10-20
  • 0
    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.2012-10-20
1

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/