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

Question

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

Answer 1

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

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

Answer 3

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