Results 1 to 2 of 2

Thread: Two Simple Proofs

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    191

    Two Simple Proofs

    Can anyone check my proofs for these two questions:

    1. Let $\displaystyle p,q,r \in \mathbb{Z}$ with $\displaystyle p,r \neq 0$. Prove that if

    $\displaystyle pr | qr$ then $\displaystyle p|q$

    2. Let $\displaystyle a,b,m \in \mathbb{N}$, prove (by giving a complete proof or a counter example) that, if

    $\displaystyle a \equiv b \pmod m$ then $\displaystyle a^2 \equiv b^2 \pmod m$

    My Attempt:

    1. Since $\displaystyle pr | qr$ we know that $\displaystyle qr=mpr $for some integer m. Then if we divide both sides by r we are left with $\displaystyle q=mp$, so p|q.

    Is this a correct proof?

    2.
    $\displaystyle a \equiv b \pmod m$ $\displaystyle \iff m | (a-b)$

    a-b =mk, for some integer k.
    $\displaystyle a^2 \equiv b^2 \pmod m$ $\displaystyle \iff m | (a^2-b^2)$

    And $\displaystyle (a^2-b^2) = (a+b)(a-b)$

    $\displaystyle (a+b)(a-b) = mk(a+b)$. So $\displaystyle m|m(ka+kb)$, and therefore $\displaystyle a \equiv b \pmod m$ implies $\displaystyle a^2 \equiv b^2 \pmod m$.

    Is this right? I'm not 100% convinced if this implication always holds...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by Roam View Post
    Can anyone check my proofs for these two questions:

    1. Let $\displaystyle p,q,r \in \mathbb{Z}$ with $\displaystyle p,r \neq 0$. Prove that if

    $\displaystyle pr | qr$ then $\displaystyle p|q$

    2. Let $\displaystyle a,b,m \in \mathbb{N}$, prove (by giving a complete proof or a counter example) that, if

    $\displaystyle a \equiv b \pmod m$ then $\displaystyle a^2 \equiv b^2 \pmod m$

    My Attempt:

    1. Since $\displaystyle pr | qr$ we know that $\displaystyle qr=mpr $for some integer m. Then if we divide both sides by r we are left with $\displaystyle q=mp$, so p|q.

    Is this a correct proof?

    Yessssir.

    2.
    $\displaystyle a \equiv b \pmod m$ $\displaystyle \iff m | (a-b)$

    a-b =mk, for some integer k.
    $\displaystyle a^2 \equiv b^2 \pmod m$ $\displaystyle \iff m | (a^2-b^2)$

    And $\displaystyle (a^2-b^2) = (a+b)(a-b)$

    $\displaystyle (a+b)(a-b) = mk(a+b)$. So $\displaystyle m|m(ka+kb)$, and therefore $\displaystyle a \equiv b \pmod m$ implies $\displaystyle a^2 \equiv b^2 \pmod m$.

    I don't understand what you did in the last lines. It's simpler:

    $\displaystyle a \equiv b\bmod m\Longrightarrow a = b + km\,,\,\,k\in \mathbb{Z}\Longrightarrow a^2=b^2 +(2bk+k^2m)m\Longrightarrow a^2\equiv b^2\bmod m$

    Tonio


    Is this right? I'm not 100% convinced if this implication always holds...
    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. simple gcd proofs
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Jun 13th 2011, 05:30 AM
  2. a few simple proofs
    Posted in the Calculus Forum
    Replies: 7
    Last Post: Mar 15th 2011, 06:23 PM
  3. Simple set proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Feb 3rd 2011, 04:52 AM
  4. simple but puzzling proofs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 5th 2009, 06:21 PM
  5. 'simple' proofs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 30th 2007, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum