# Divisibility Proof

• Feb 18th 2010, 04:57 AM
Berge
Divisibility Proof
Hi guys !!!(Hi)

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.

• Feb 18th 2010, 05:41 AM
havaliza
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.
• Feb 18th 2010, 06:11 AM
Berge
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 ?
• Feb 18th 2010, 07:24 AM
james_bond
4 doesn't divide $\displaystyle 3^4-3$...
• Feb 18th 2010, 07:41 AM
Berge
Thanks James, this counterexample really takes the pressure off!
• Feb 18th 2010, 07:47 AM
Chris11
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
• Feb 18th 2010, 10:45 AM
Berge
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!
• Feb 18th 2010, 01:30 PM
Chris11
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.
• Feb 18th 2010, 02:08 PM
Drexel28
Quote:

Originally Posted by Berge
Hi guys !!!(Hi)

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$