3
$\begingroup$

For any integer, $n$, show that $n^3 \equiv 0$ or $\pm 1(\mod 7)$. Use theory of congruences

So I thought about a couple of ways to go with this. I thought about showing $7|n^3$ or $7|n^3\pm1$ to be true by letting $n=7k, 7k\pm1, 7k\pm2, 7k\pm3$ and proving it that way but that seemed like a long route. Also, the problem asks to use theory of congruences and I'm not sure if this approach really uses that.

Is there a way to use the fact that $a^n \equiv b^n (\mod m)$? I tried following this logic, but I got stuck trying to imply that $n \equiv 0$ or $\pm 1(\mod 7)$ by removing the cube root.

Any help is appreciated!

$\endgroup$
  • 1
    $\begingroup$ It was quite easy to check all possibilities of mod 7 $\endgroup$ – N.S.JOHN May 17 '16 at 16:10
1
$\begingroup$

Consider the following cases:

  • $n\equiv0\pmod7 \implies n^3\equiv0^3\equiv 0\equiv 0\pmod7$
  • $n\equiv1\pmod7 \implies n^3\equiv1^3\equiv 1\equiv+1\pmod7$
  • $n\equiv2\pmod7 \implies n^3\equiv2^3\equiv 8\equiv+1\pmod7$
  • $n\equiv3\pmod7 \implies n^3\equiv3^3\equiv 27\equiv-1\pmod7$
  • $n\equiv4\pmod7 \implies n^3\equiv4^3\equiv 64\equiv+1\pmod7$
  • $n\equiv5\pmod7 \implies n^3\equiv5^3\equiv125\equiv-1\pmod7$
  • $n\equiv6\pmod7 \implies n^3\equiv6^3\equiv216\equiv-1\pmod7$
$\endgroup$
  • 1
    $\begingroup$ Though I'm not entirely sure that it uses "theory of congruences"... $\endgroup$ – barak manos May 17 '16 at 16:13
  • $\begingroup$ That's what I was worried about too, but I think it might and I was just going the wrong direction with it. $\endgroup$ – Carolyn May 17 '16 at 16:15
  • $\begingroup$ You showed the trivial method is easy. But the OP was asking for another method, like ihf's $\endgroup$ – N.S.JOHN May 17 '16 at 16:15
13
$\begingroup$

Fermat's theorem tells us that $n^7 \equiv n \bmod 7$ and so $7$ divides $n^7-n=n(n^3-1)(n^3+1)$.

Since $7$ is prime, $7$ must divide one of the factors:

  • If $7$ divides $n$, then $7$ divides $n^3$, and so $n^3 \equiv 0 \bmod 7$.
  • If $7$ divides $n^3- 1$, then $n^3 \equiv 1 \bmod 7$.
  • If $7$ divides $n^3+ 1$, then $n^3 \equiv -1 \bmod 7$.
$\endgroup$
  • $\begingroup$ Sorry how does the second equation follow? Oh got it it beomes $n^7-n $ right? $\endgroup$ – N.S.JOHN May 17 '16 at 16:13
  • 1
    $\begingroup$ @N.S.JOHN Yes. To notice that, factor out the $n$ so you have $n\,(n^6 - 1)$. $n^6 - 1$ is a difference of squares, which factors into $(n^3 - 1)\,(n^3 + 1)$. $\endgroup$ – Tavian Barnes May 17 '16 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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