Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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

2 Answers 2

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$.
share|improve this answer
    
how can I aaply these theorems? –  Prasanta Jan 5 '13 at 8:43
6  
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|improve this answer
    
Why the downvote? –  Feanor Jun 25 at 10:41

Your Answer

 
discard

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.