0
$\begingroup$

Prove that if a $\in \mathbb{Z}$ then $a^{3} \equiv a(mod 3)$

So, the ways I have learned (or am learning, rather) to do proofs is using direct, contrapositive and contradiction.

So, I started it using direct, and got this:

$n|(a^{3}-a)$

Then there exists an integer k such that:

$nk = a^{3} - a$

$nk = a(a^{2} - 1)$

$nk = a(a+1)(a-1)$

so a must be -1, 0 or 1.

And there is where I'm stuck. I don't know where to go next and I'm not sure if it would be easier to use another method, maybe contradiction? Any help is appreciated! Thanks.

$\endgroup$
  • $\begingroup$ See my answer below. How many factors are there? What is their relationship to each other? $\endgroup$ – user4894 Oct 26 '14 at 19:21
2
$\begingroup$

Try factoring $a^3−a$. What do you notice about the relationship of the factors to each other? How many are there? What can you then conclude?

$\endgroup$
0
$\begingroup$

The other answers are great. You can also break this into cases. For any integer $a$, we must have:

$a \equiv \text{0, 1, or 2} \pmod{3}$.

Considering each case, we have:

$$0^3 \equiv 0 \pmod{3}$$ $$1^3 \equiv 1 \pmod{3}$$ $$2^3 \equiv 8 \equiv 2 \pmod{3}$$

More generally, I'd recommend reading up on Fermat's Little Theorem.

$\endgroup$

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.