# explain why $3|n$ with the following conditions..

If $ord_ma=3$ and if $a^n\equiv 1 \pmod{m}$ for some $n\ge1$, explain why $3|n$.

Attempt at solution:

We know that $ord_ma=3$ means $a^3\equiv 1 \pmod{m}$. Therefore, $n$ is a multiple of $3$, because $a^{3n}\equiv 1 \pmod{m}$.

-
Not quite... You also need to use that $a^2$ and $a$ are not congruent to 1 mod $m$. –  jp26 Nov 4 '12 at 21:04
@jp26 What would then $ord_m a$ be? ;) –  N. S. Nov 4 '12 at 21:09
@N.S. the definition of order is the smallest positive power of $a$ such which is congruent to 1. maroon.elephants wasn't using that in the proof whereas the proofs below do... –  jp26 Nov 4 '12 at 21:19
@jp26 Sorry missread your comment :) –  N. S. Nov 4 '12 at 21:23

There are three possibilities: $n = 3k$ or $n = 3k + 1$ or $n = 3k + 2$.

What happens if $n = 3k + 1$? Then $a^n = a^{3k+1} = (a^3)^k a \equiv 1^k a \equiv a \mod m$. Since we assumed $a^n \equiv 1 \mod m$, this implies $a \equiv 1 \mod n$. But this is not possible, since $ord_m a = 3$. Hence $n$ cannot be of the form $3k + 1$.

Similarly, show that $n$ cannot be of the form $3k+2$. Then the only possibility is that $n = 3k$, which proves the statement.

-
How do you know there are three possibilities? –  maroon.elephants Nov 4 '12 at 22:45
@maroon.elephants: It follows from the division algorithm. For any $n$, there exist integers $k$ and $r$ such that $n = 3k + r$ where $0 \leq r < 3$. –  Mikko Korhonen Nov 4 '12 at 23:22
Will $r$ always be $0 \leq r < 3$? Or say if $ord_ma=7$ will $r$ be $0 \leq r < 7$? thanks –  maroon.elephants Nov 6 '12 at 17:48

The reasoning is incomplete. First note that $\text{ord}_m(a)=3$ means that $a^3\equiv 1\pmod{m}$ and for any positive integer $k \lt 3$, we have $a^k\not\equiv 1\pmod{m}$.

Now we proceed to show that if $a^n\equiv 1\pmod{m}$, where $n\ge 1$, then $3$ divides $n$.

Suppose to the contrary that $3$ does not divide $n$. Then if we attempt to divide $n$ by $3$, we get a non-zero remainder. More precisely, $n=3q+k$ where $k=1$ or $k=2$. Then $$a^n=a^{3q+k}=(a^3)^qa^k.$$ But since $a^3\equiv 1\pmod{m}$, it follows that $(a^3)^q\equiv 1\pmod{m}$, and therefore $a^n\equiv a^k\pmod{m}$. Thus $a^k\equiv 1\pmod{m}$. Since $k=1$ or $k=2$, this contradicts the fact that $a$ has order $3$ modulo $m$.

-

Hint $\$ By division, $\rm\:n = 3\, q + r,\,\ 0\le r< 3,\:$ so $\rm\: 1 \equiv a^n \equiv (a^3)^q a^r \equiv 1^q a^r \equiv \color{#C00}{a^r}\:$ yields a contradiction if $\rm\:r\ne 0\:$ since then $\rm\:r<3 \:\Rightarrow\: r = 2\ (\Rightarrow\: \color{#C00}{a^2}\equiv 1)$ or $\rm\:r = 1\ (\Rightarrow \rm\:\color{#C00}{a^1}\equiv 1),\:$ contra $\rm\,a\,$ has order $3$.

Remark $\$ More conceptually, the set $\cal O$ of integers $\rm\,n\,$ with $\rm\:a^n\equiv 1\:$ is closed under subtraction, so, by a fundamental theorem, every element of $\cal O$ is a multiple of the least positive element of $\cal O$.

-