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.

Without using the fact that 67 is prime, show that the order of 2 mod 67 is 66. Explain why this result proves that 67 is prime

What I understand:

  • The order of 2 in $\mathbb{Z}_{67}$(or mod $67$) $ = 66$ means that $66$ is the smallest power $2^x$ such that $2^x \equiv 1$ mod 67

  • Lucas primality test states if we can find $a$ such that $a$ has order $n-1$ mod $n$ then $n$ is prime. Here the question states that $a = 2$ has order $67-1=66$

  • This result proves $67$ is prime by Lucas test

Now the part I don't get is how can you show the order of $2$ mod $67$ is indeed $66$?

share|improve this question
    
Hint $\ $ See this refinement of the Lucas Primality Test. –  Bill Dubuque Sep 25 '12 at 4:33
add comment

3 Answers 3

up vote 5 down vote accepted

Compute, using the binary method for exponentiation, and reducing modulo $67$ often. It can be done with a simple calculator.

First verify that $2^{66}\equiv 1\pmod{67}$.

Thus the order of $2$ must divide $66$. That leaves not many numbers to rule out as the order of $2$.

share|improve this answer
add comment

The brute force way is to calculate $2,2^2,2^3,\dots$, all modulo 67, until you get 1, and notice that this doesn't happen until you reach $2^{66}$.

You can save some work by first calculating $2^{66}$ modulo 67 in a clever way (one that doesn't require calculating all the lower powers first), and then showing for all primes $p$ dividing 66 (namely, 2, 3, and 11) that $2^{66/p}$ is not 1 modulo 67.

share|improve this answer
    
See this question for this refinement of the Lucas Primality Test. –  Bill Dubuque Sep 25 '12 at 4:31
add comment

$2^6\equiv64\pmod {67} \implies 2^6\equiv -3 \pmod {67}\implies {(2^6)}^{11}\equiv -3^{11}\pmod {67}$

Now, $3^4\equiv 14\pmod {67}\implies 3^8\equiv 196\pmod {67}\equiv{-5}\pmod {67}$

$\implies 3^{11}=3^8.3^3\equiv -135\pmod {67}$

Therefore, $2^{66}\pmod {67}\equiv-3^{11}\pmod {67}\equiv 135\pmod {67}\equiv 1\pmod {67}$

order of $2$ must divide $66=2*3*11$

Factors of $66$ are: $2,3,6,11,22,33,66$

Since, $2^2=4\not\equiv1\pmod {67}$, $2^3=8\not\equiv 1 \pmod {67}$,$2^6=64\equiv{-3}\pmod {67}$, $2^{11}=38\not\equiv 1\pmod {67}$, $2^{22}={(2^6)}^3.2^4\equiv{-30}\pmod {67}$ and $2^{33}=2^{22}.2^{11}\equiv{-1}\pmod {67}$

Hence, order of $2\pmod {67}$ is $66$

share|improve this answer
1  
Yes, $2^{66}\!\equiv 1$ but that does not imply that $2$ has order $66,\,$ which is what is needed. –  Bill Dubuque Sep 25 '12 at 4:23
    
i have edited my answer. –  Aang Sep 25 '12 at 6:04
    
That's still incorrect, since $66$ has proper divisors other than $2,3,11$. See Gerry's answer and/or the link I mentioned there for one correct approach. –  Bill Dubuque Sep 25 '12 at 6:13
    
Is this okay now?? –  Aang Sep 25 '12 at 6:24
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.