Results 1 to 6 of 6

Thread: Prove Divisibility

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Prove Divisibility

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

    Let P: $\displaystyle n | a^2 $
    and $\displaystyle Q: n | a$.

    I have no trouble proving $\displaystyle Q \Rightarrow P$.

    I have trouble with $\displaystyle \sim Q \Rightarrow P$.

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

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

    How do you prove $\displaystyle P \Rightarrow Q$?

    For $\displaystyle P \Rightarrow Q$ is it okay to prove $\displaystyle Q \Rightarrow \sim P$ to get the contradiction?
    Last edited by novice; Mar 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
    22
    Quote Originally Posted by novice View Post
    For any integer $\displaystyle a$ and $\displaystyle n, n | a^2$ if and only if $\displaystyle n | a.$

    Let P: $\displaystyle n | a^2 $
    and $\displaystyle Q: n | a$.

    I have no trouble proving $\displaystyle Q \Rightarrow P$.

    I have trouble with $\displaystyle \sim Q \Rightarrow P$.

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

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

    How do you prove $\displaystyle P \Rightarrow Q$?

    For $\displaystyle P \Rightarrow Q$ is it okay to prove $\displaystyle Q \Rightarrow \sim P$ to get the contradiction?
    $\displaystyle 4\mid 2^2$ but $\displaystyle 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
    $\displaystyle 4\mid 2^2$ but $\displaystyle 4\nmid 2$
    How should I device the question so that $\displaystyle 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
    $\displaystyle 4\mid 2^2$ but $\displaystyle 4\nmid 2$
    Drexel,
    I just realized, you can't use a counter example because postulate is a biconditional logic. It says $\displaystyle n|a^2$ unless $\displaystyle 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
    22
    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 $\displaystyle n|a^2$ unless $\displaystyle n|a$.
    I'm no logician but $\displaystyle 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 $\displaystyle 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: Oct 29th 2009, 10:54 AM
  2. Prove divisibility by induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: Jun 2nd 2009, 12:14 PM
  3. Prove divisibility by 7 (using induction)
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 29th 2008, 11:12 AM
  4. Prove divisibility by induction
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Jul 30th 2008, 12:58 PM
  5. Prove divisibility
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Nov 17th 2007, 06:18 AM

Search Tags


/mathhelpforum @mathhelpforum