# 9th power of any positive integer is of the form $19 m$ or $19 m \pm 1$

Which of the following statements are true?

1. The 9th power of any positive integer is of the form $19 m$ or $19 m \pm 1$.

2. For any positive integer $n$, the number $n^{13} - n$ is divisible by 2730.

3. The number $18! + 1$ is divisible by 437.

I am stuck on this problem. Can anyone help me please...

-
Little Fermat, congruences and $(x^{18}-1)=(x^9-1)(x^9+1)$ will get you started. – Jyrki Lahtonen Jan 5 '13 at 8:38

Hints:

• Euler's theorem: for $a$ and $n$ relatively prime, $a^{\varphi(n)}\equiv 1\bmod n$.
• Wilson's theorem: for a prime number $p$, $(p-1)!\equiv -1\bmod p$.
-
how can I aaply these theorems? – user45799 Jan 5 '13 at 8:43
That is for you to think about, for more than 4 minutes at any rate. How do you expect to get better at solving problems if you are not practicing solving problems? – Zev Chonoles Jan 5 '13 at 8:45
1. From Euler, deduce that for each $a$, $a^{18} \pmod{19}$ is $0$ or $1$. Hence, if $b = a^{9}$, then $b^2$ is $0$ or $1$, and hence $b$ is $0$ or $\pm 1$.

2. Note that $2730 = 2\cdot 3\cdot 5 \cdot 7 \cdot 13$, so it's enough to show that for each $p \in \{ 2,3,5, 7, 13 \}$, $p$ divides $n^{13} - n$. But from Euler, $p$ divides $n^p - n$, and more generally $n^{k(p-1)+1} - n$. So, it's enough to check that for each of our $p$'s, it holds that $p-1$ divides $13-1$. But this is obvious.

3. Note that $437 = 19 \cdot 23$, so it's enough to see if $18! \equiv -1 \pmod{19}$ and $18! \equiv -1\pmod{23}$. The first statement is just Wilson for $p = 19$. The second, again by Wilson, is equivalent to $18! \equiv 22! \pmod{23}$, which is equivalent to $1 \equiv 22\cdot 21 \cdot 20 \cdot 19 \pmod{23}$. You can check that by computing the right side by hand, or you can notice that $$22\cdot 21 \cdot 20 \cdot 19 \equiv (-1) \cdot (-2) \cdot (-3) \cdot (-4) \equiv 4! \equiv 24 \equiv 1 \pmod{23}$$

-
Why the downvote? – Jakub Konieczny Jun 25 '14 at 10:41