Results 1 to 2 of 2

Math Help - 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 p,q,r \in \mathbb{Z} with p,r \neq 0. Prove that if

    pr | qr then p|q

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

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

    My Attempt:

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

    Is this a correct proof?

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

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

    And (a^2-b^2) = (a+b)(a-b)

    (a+b)(a-b) = mk(a+b). So m|m(ka+kb), and therefore a \equiv b \pmod m implies 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
    2
    Quote Originally Posted by Roam View Post
    Can anyone check my proofs for these two questions:

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

    pr | qr then p|q

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

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

    My Attempt:

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

    Is this a correct proof?

    Yessssir.

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

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

    And (a^2-b^2) = (a+b)(a-b)

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

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

    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: June 13th 2011, 05:30 AM
  2. a few simple proofs
    Posted in the Calculus Forum
    Replies: 7
    Last Post: March 15th 2011, 06:23 PM
  3. Simple set proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 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: October 30th 2007, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum