<s>[INST] 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$?
 [/INST] $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$
</s>