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$?

Please include examples of your own thoughts, context, where you are struggling and/or an attempt to resolve the problem on your own. — gen-ℤ ready to perish, Oct 18 '17 at 02:09

score 3 · Answer 1 · answered Oct 18 '17 at 01:57

3

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$.

answered Oct 18 '17 at 01:57

Oscar Lanzi

39,403

score 1 · Accepted Answer · edited Oct 18 '17 at 16:35

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.

edited Oct 18 '17 at 16:35

Oscar Lanzi

39,403

answered Oct 18 '17 at 02:21

fleablood

124,253

Thanks for the news about $4^4$. I always thought it was $256\equiv 34 \bmod 37$. – Oscar Lanzi Oct 18 '17 at 13:42
1

Ooops..... But it's still not $\equiv 1 \mod 37$. – fleablood Oct 18 '17 at 15:51

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

2 Answers2