# Explain why 67 is prime based on the fact that order of 2 mod 67 is 66

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

-
Hint $\$ See this refinement of the Lucas Primality Test. –  Bill Dubuque Sep 25 '12 at 4:33

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

-

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.

-
See this question for this refinement of the Lucas Primality Test. –  Bill Dubuque Sep 25 '12 at 4:31

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

-
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