Results 1 to 4 of 4

Math Help - Divisiblity Proofs

  1. #1
    Junior Member
    Joined
    Jan 2008
    Posts
    35

    Divisiblity Proofs

    Can anyone give me some hints on the following problem:

    For integers x and y, show that 7 | x^2 + y^2 if and only if 7 | x and  7 | y

    Thanks in advance

    Shinn
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,719
    Thanks
    634
    Hello, Shinn!

    For integers x and y, show that: . 7 |( x^2 + y^2)\:\text{ if and only if }\:7 | x\,\text{ and }\,7 | y
    I'll do the "only if" part . . .


    \text{Prove: }\:\text{If }\,7|x\,\text{ and }\,7|y\,\text{, then }\,7|(x^2+y^2)


    Since 7|x,\;\;x \:=\:7a\,\text{ for some integer }a
    Since 7|y,\;\;y \:=\:7b\,\text{ for some integer }b

    Then: . \begin{array}{ccccc}x^2 &=& (7a)^2 &=& 49a^2 \\ y^2 &= & (7b)^2 &=& 49b^2 \end{array}

    Hence: . x^2+y^2\:=\:49a^2 + 49b^2 \:=\:7(7a^2+7b^2) \quad\hdots\;\text{ a multiple of 7}

    Therefore: . 7|(x^2+y^2)

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2008
    Posts
    35
    Hi, thanks for the reply.
    Is it correct if i prove "If 7 | x^2 + y^2 then 7|x and 7 | y" by the following:

    Given 7 | x^2 + y^2
    Then, 7 | x^2 and 7 |y^2
    (how would I write out a reason for this line?)
    Thus, 7 | x and 7 |y
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi
    I don't see any very easy proof.

    Maybe you can do that using a contraposition proof:
    assume 7 doesn't divide x nor y, i.e. there are integers k,l\in\{1,2,3,4,5,6\} such that x\equiv k(\text{mod}7) and y\equiv l(\text{mod}7)

    Then x^2+y^2\equiv n+m(\text{mod}7) where n,m\in\{1,2,4\} \ \ \ (*)

    therefore x^2+y^2\neq 0(\text{mod}7) i.e. 7 does not divide x^2+y^2.

    To prove (*), compute all squares in \mathbb{Z}_7.


    Another way to show that would be to say that \mathbb{Z}[i] is a factorial ring, that 7 is an odd prime and 7\equiv 3(\text{mod}4) so it is irreducible in \mathbb{Z}[i], and as a consequence 7|x^2+y^2\Rightarrow 7|(x+iy)(x-iy)\Rightarrow 7|x+iy\ \text{or}\ 7|x-iy \Rightarrow 7|x\ \text{and}\ 7|y.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisiblity test for 3
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 15th 2010, 09:31 AM
  2. Help with log Proofs
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 2nd 2010, 01:38 PM
  3. More Proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 10th 2009, 07:54 AM
  4. Questions Involving Divisiblity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 20th 2009, 04:14 AM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum