Results 1 to 10 of 10

Math Help - Divisibility Proof

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    9

    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.

    thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2010
    Posts
    16
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    9
    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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2007
    Posts
    329
    4 doesn't divide 3^4-3...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2010
    Posts
    9
    Thanks James, this counterexample really takes the pressure off!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Feb 2010
    Posts
    9
    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!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Berge View Post
    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.

    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Feb 2010
    Posts
    9
    Thanks Fermat makes the job a lot easier !
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: June 10th 2010, 11:47 AM
  2. divisibility proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 24th 2010, 09:45 AM
  3. Divisibility Proof
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: March 16th 2009, 07:11 PM
  4. divisibility proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 20th 2009, 11:27 PM
  5. Divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 10th 2008, 08:07 AM

Search Tags


/mathhelpforum @mathhelpforum