Modulo Arithmetic Proof - FLT

Question

Show that (61! + 1) ≡ (63! + 1) ≡ 0 (mod 71)

I've tried thinking of how to use Fermat's Little Theorem with this but haven't been able to make much headway

Answer 1

$71$ is prime and by Wilson theorem you know that $70!$ has remainder $-1$ modulo $71$. You claim that also $61!$ and $63!$ have the same remainder $-1$. To this aim, it is sufficient to prove that $$ 62 \cdot 63 \equiv 1\pmod{71} $$ and that $$ 64 \cdot 65 \cdot 66 \cdot 67 \cdot 68 \cdot 69 \cdot 70 \equiv 1\pmod{71}. $$ The first one is obvious by hand. The second one is also easy because it is equivalent to $$ (-7) \cdot (-6) \cdot (-5) \cdot (-4) \cdot (-3) \cdot (-2) \cdot (-1) \equiv -7!\equiv 1\pmod{71}. $$

Answer 2

For Wilson's Theorem

$$(p-1)!\equiv -1 \pmod p \implies (70)!\equiv -1 \pmod {71}$$

then

$$(61)!+1\equiv 0 \pmod {71} \iff (61)!\equiv -1 \pmod {71}\iff 70\cdot69\cdot...\cdot62\equiv 1 \pmod {71} $$

which is true indeed

$$70\cdot69\cdot...\cdot62\equiv -9!\equiv-(9\cdot 8)\cdot(7\cdot5\cdot2)\cdot(6\cdot4\cdot3)\equiv-1\cdot-1\cdot1\equiv1 \pmod {71} $$

and also

$$(63)!+1\equiv 0 \pmod {71} \iff (63)!\equiv -1 \pmod {71}\iff 70\cdot69\cdot...\cdot64\equiv 1 \pmod {71} $$

which is true indeed

$$70\cdot69\cdot...\cdot64\equiv -7!\equiv-(7\cdot5\cdot2)\cdot(6\cdot4\cdot3)\equiv1\cdot1\equiv1 \pmod {71} $$

Answer 3

Firstly, $$\begin{align}63!+1&=(63)(62)(61!+1)-(63)(62)+1\\ &\equiv(63\times 62)(61!+1)-(-8)(-9)+1\\ &\equiv(63\times 62)(61!+1)-71\\ &\equiv 61!+1\mod{71}\end{align}$$ Then to prove this is congruent to $0$, by Wilson's theorem, $70!\equiv -1$ $$\begin{align}70!+1&=(70)(69)(68)(67)(66)(65)(64)(63!+1)-(70)(69)(68)(67)(66)(65)(64)+1\\ &=k(63!+1)-(-1)(-2)(-3)(-4)(-5)(-6)(-7)+1\\ &=k(63!+1)+(2)(5)(7)+1\\ &=k(63!+1)+71\\ &\equiv 63!+1\equiv 0\mod{71} \end{align}$$

So done.