Congruence modulo 37 using Euler's theorem (maybe).

Question

How would one show (preferably using congruences) that $$37\not\mid n^{9^9}+4 $$ for any $n \in \mathbb Z$?

Answer 1

If $n\equiv 0 \mod 37$ then that statement isn't true of course.

If $n\not\equiv 0\mod 37... $

37 is prime. So $n^{36}\equiv 1\mod 37$. So if $9^9\equiv k \mod 36$ then ${n^9}^9\equiv n^k \mod 37$.

Hmmm... $4*9=36$ so $9*9\equiv 9+9*4+9*4\equiv 9\mod 36$ so $9^2\equiv 9\mod 36$ and inductively $9^k\equiv 9\mod 36$.

So ${n^9}^9\equiv n^9 \mod 37$.

And $(n^9)^4=n^{36}\equiv 1\mod 37$.

So if $n^9\equiv -4 \mod 37$ then it must be true that $4^4\equiv 1\mod 37$.

But $4^4=256\not \equiv 1\mod 37$.

So ... that's that then.

Answer 2

For the divisibility to hold we must have $n$ prime to $37$. Then $n^{36}\equiv 1 \bmod 37$. Now, $4×9^9$ is a multiple of $36$ so $n^{4×9^9}=(n^{9^9})^4\equiv 1$. Alas, $(-4)^4\equiv 256\equiv 34$, and $1\equiv 34$ won't work $\bmod 37$.