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.

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}$.

share|improve this question
    
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

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer

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

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.