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$?
 A: 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$. 
A: 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. 
A: $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$
