1. ## Divisibility Proof

Hi guys !!!

I've got a few problems regarding divisibility of equations, one of them is the following:
Show that 3|x³ - x and if possible extend the proof to n|x^n-x.

2. I can solve the first one. But not the second one.
Factorization of $\displaystyle x^3-x$ is $\displaystyle (x+1)(x-1)x$. The factors are three consecutive integers. So there is exactly one multiple of 3 among them. As a result $\displaystyle x^3-x$ is divisible by 3.

3. Thanks havaliza, I've been studing divisibility with a textbook that doesn't mention factorization. But it's easier though. So just to make sure I got it, if I can proof that the expression contains a number of consecutive integers it is divisible by this number of integers?Is that right ?

4. 4 doesn't divide $\displaystyle 3^4-3$...

5. Thanks James, this counterexample really takes the pressure off!

6. You could search for when that statement happens to be true. Ie is it true when n is prime, and so on. If you can't prove a theorem in a more general way due to counterexamples, then try doing it in more restricted cases. One way to do it is to find the set of all inputs where the theorem fails, and then use this to find the set that works

7. Thanks for the tip, really enlightening. I happened to analyse some failures but I hadn't considered to think about them as set. I feel like a real mathematician!

8. No problem. Sometimes it is actualy eaiser to find the entire set of failures than one counter example. But, if this is for a course, if your teacher asks for one counterexample be sure to give just that; if you present the set, they could doc marks... I don't think they should, but my analysis teacher did that. Having the set is a lot more useful than a single counter example I think.

9. Originally Posted by Berge
Hi guys !!!

I've got a few problems regarding divisibility of equations, one of them is the following:
Show that 3|x³ - x and if possible extend the proof to n|x^n-x.

A little more high-browed approach has you recall Fermat's little theorem, in particular that $\displaystyle a^{p-1}\equiv a\text{ mod }p$ if $\displaystyle 0<a<p$. So, in the above, if $\displaystyle 3\mid x$ this is obvious, so assume that $\displaystyle 3\nmid x$ then $\displaystyle (x,3)=1$ and so $\displaystyle x^3-x\equiv x-x=0\text{ mod }3$ and the conclusion follows. Also, induction works quite nicely since $\displaystyle (n+1)^3-(n+1)=(n+1)((n+1)^2-1)=$$\displaystyle (n+1)(n^2+2n)=n^3+3n^2+2n=n^3-n+3(n^2+n)$.
Also, using the Fermat's little theorem trick you can conclude that $\displaystyle p\mid x^p-x$ for prime $\displaystyle p$