Results 1 to 4 of 4

Thread: 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 $\displaystyle 7 | x^2 + y^2$ if and only if $\displaystyle 7 | x$ and $\displaystyle 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
    12,028
    Thanks
    848
    Hello, Shinn!

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


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


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

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

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

    Therefore: .$\displaystyle 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 $\displaystyle 7 | x^2 + y^2$ then $\displaystyle 7|x$ and $\displaystyle 7 | y$" by the following:

    Given $\displaystyle 7 | x^2 + y^2$
    Then, $\displaystyle 7 | x^2 $ and $\displaystyle 7 |y^2$
    (how would I write out a reason for this line?)
    Thus, $\displaystyle 7 | x $ and $\displaystyle 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 $\displaystyle 7$ doesn't divide $\displaystyle x$ nor $\displaystyle y,$ i.e. there are integers $\displaystyle k,l\in\{1,2,3,4,5,6\}$ such that $\displaystyle x\equiv k(\text{mod}7)$ and $\displaystyle y\equiv l(\text{mod}7)$

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

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

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


    Another way to show that would be to say that $\displaystyle \mathbb{Z}[i]$ is a factorial ring, that $\displaystyle 7$ is an odd prime and $\displaystyle 7\equiv 3(\text{mod}4)$ so it is irreducible in $\displaystyle \mathbb{Z}[i],$ and as a consequence $\displaystyle 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: Mar 15th 2010, 09:31 AM
  2. Help with log Proofs
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Mar 2nd 2010, 01:38 PM
  3. More Proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 10th 2009, 07:54 AM
  4. Questions Involving Divisiblity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 20th 2009, 04:14 AM
  5. Replies: 3
    Last Post: Oct 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum