Divisibility Proof

Printable View

February 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.

thanks in advance.
February 18th 2010, 05:41 AM
havaliza

I can solve the first one. But not the second one.
Factorization of $x^3-x$ is $(x+1)(x-1)x$ . The factors are three consecutive integers. So there is exactly one multiple of 3 among them. As a result $x^3-x$ is divisible by 3.
February 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 ?
February 18th 2010, 07:24 AM
james_bond

4 doesn't divide $3^4-3$ ...
February 18th 2010, 07:41 AM
Berge

Thanks James, this counterexample really takes the pressure off!
February 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
February 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!
February 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.
February 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.

thanks in advance.

A little more high-browed approach has you recall Fermat's little theorem, in particular that $a^{p-1}\equiv a\text{ mod }p$ if $0<a<p$ . So, in the above, if $3\mid x$ this is obvious, so assume that $3\nmid x$ then $(x,3)=1$ and so $x^3-x\equiv x-x=0\text{ mod }3$ and the conclusion follows. Also, induction works quite nicely since $(n+1)^3-(n+1)=(n+1)((n+1)^2-1)=$ $(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 $p\mid x^p-x$ for prime $p$
February 19th 2010, 01:01 AM
Berge

Thanks Fermat makes the job a lot easier !