Use Lucas' test with $a=7$ and prove $71$ is prime

Question

My working so far:

$71-1=70$ and Prime factors of $70$ are $2 \times 5 \times 7$

Check $a=7$:

$7^{(\frac{70}{2})} \equiv 7^{35} \equiv x (mod 71)$

How do I find $x$? Usually I would use Fermat's little theorem and firstly find $\phi(71)$ except 71 is prime (giving the value as $71-1=70$ but this is a fact that we're trying to prove in the first place!!

I could of course use my calculator to calculate it, but this assumes the numbers aren't too extremely horrible.

How else do you calculate this nicely?

Answer 1

You can use repeated squaring to get to large powers quickly, then use binary to write the exponent as a sum of exponents you've already reached: $$7^1 = 7 \equiv 7\pmod{71}$$ $$7^2 = 49 \equiv 49\pmod{71}$$ $$7^4 = 49^2 \equiv 58\pmod{71}$$ $$7^8 = 58^2 \equiv 27\pmod{71}$$ $$7^{16} = 27^2 \equiv 19\pmod{71}$$ $$7^{32} = 19^2 \equiv 6\pmod{71}$$ $$7^{35}=7^{32}7^27^1\equiv 6\cdot 49\cdot 7\equiv 70\pmod{71}$$ It's still a lot of work, but it's much less than multiplying $7$ by itself $35$ times, even if you reduce mod $71$ each time.

Answer 2

Why don't we start with the minimum positive integer that is $>1$ and reach $7^{35}$ as the multiplication by $2$ is much easier.

$2^5=32,2^7=128\equiv -14{\pmod {71}}$

Now $2^8\equiv -28{\pmod {71}},2^{16}\equiv 784\equiv 3,2^{32}\equiv 9$

So, $2^{35}=2^{32}2^3\equiv 9\cdot 8 {\pmod {71}} \equiv 1$

If $m\equiv 2^n{\pmod {71}},$ where $n$ is any positive integer,

$m^{35}=(2^n)^{35}=(2^{35})^n\equiv (1)^n{\pmod {71}}=1$

$\implies (-m)^{35}=m^{35}(-1)^{35}\equiv-1{\pmod {71}}$

$\implies (-m)^5≢1{\pmod {71}}$ and $(-m)^7≢1$

We just need to show that, $(-m)^2 ≢1{\pmod {71}}$

If $n=6,m=64\implies -m=-64\equiv 7{\pmod {71}}$, which is $a$, according to the given problem.

Now $a^2=7^2=49 ≢1{\pmod {71}}$,

so by Lucas test, $71$ is prime.

This method can be employed to any prime of the form $2(2r+1)+1\equiv 3 \pmod 4$