Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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


  • 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$.
share|cite|improve this answer
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}$$

share|cite|improve this answer
Why the downvote? – Jakub Konieczny Jun 25 '14 at 10:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.