Results 1 to 6 of 6

Math Help - Prove Divisibility

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Prove Divisibility

    For any integer a and n, n | a^2 if and only if n | a.

    Let P: n | a^2
    and Q: n | a.

    I have no trouble proving Q \Rightarrow P.

    I have trouble with \sim Q \Rightarrow P.

    I am doing it by showing that if n \not | a, then a \not = ny or equivalently,

    a = n y + c, where y, c \in \mathbb{Z} and 1  \leq c < n. It doesn't look too good.

    How do you prove P \Rightarrow Q?

    For P \Rightarrow Q is it okay to prove Q \Rightarrow \sim P to get the contradiction?
    Last edited by novice; March 1st 2010 at 02:00 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by novice View Post
    For any integer a and n, n | a^2 if and only if n | a.

    Let P: n | a^2
    and Q: n | a.

    I have no trouble proving Q \Rightarrow P.

    I have trouble with \sim Q \Rightarrow P.

    I am doing it by showing that if n \not | a, then a \not = ny or equivalently,

    a = n y + c, where y, c \in \mathbb{Z} and 1  \leq c < n. It doesn't look too good.

    How do you prove P \Rightarrow Q?

    For P \Rightarrow Q is it okay to prove Q \Rightarrow \sim P to get the contradiction?
    4\mid 2^2 but 4\nmid 2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    4\mid 2^2 but 4\nmid 2
    How should I device the question so that n | a? Never mind. Thanks anyway.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    4\mid 2^2 but 4\nmid 2
    Drexel,
    I just realized, you can't use a counter example because postulate is a biconditional logic. It says n|a^2 unless n|a.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by novice View Post
    Drexel,
    I just realized, you can't use a counter example because postulate is a biconditional logic. It says n|a^2 unless n|a.
    I'm no logician but n\mid a^2\Longleftrightarrow n\mid a is countered by my example.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    I'm no logician but n\mid a^2\Longleftrightarrow n\mid a is countered by my example.
    You are right; it's logically inconsistent.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 29th 2009, 10:54 AM
  2. Prove divisibility by induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: June 2nd 2009, 12:14 PM
  3. Prove divisibility by 7 (using induction)
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 29th 2008, 11:12 AM
  4. Prove divisibility by induction
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: July 30th 2008, 12:58 PM
  5. Prove divisibility
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 17th 2007, 06:18 AM

Search Tags


/mathhelpforum @mathhelpforum