Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete Mathematics with possible Quotient Remainder Theorem

  1. Sep 12, 2007 #1
    The problem statement, all variables and given/known data

    For all integers m, m[tex]^{}2[/tex]=5k, or m[tex]^{}2[/tex]=5k+1, or m[tex]^{}2[/tex]=5k+4 for some integer k.


    Relevant equations
    I'm pretty sure we have to use the Quotient Remainder THM, which is:

    Given any integer n and positive integer d, there exists unique integers q and r such that,

    n=dq+r and 0 [tex]\leq[/tex]r<d.

    But that's as far as I got. I have no idea what to do next.
     
  2. jcsd
  3. Sep 12, 2007 #2

    StatusX

    User Avatar
    Homework Helper

    Well, it seems pretty obvious what you want d to be. Then square it.
     
  4. Sep 12, 2007 #3
    No, I have no idea what d is supposed to be. Are you saying that d should equal m and that d squared is m squared?
     
  5. Sep 12, 2007 #4

    StatusX

    User Avatar
    Homework Helper

    Compare 5k+1 to dq+r.
     
  6. Sep 13, 2007 #5
    Aaahhh...

    So d=5, k=q, and r=1. Would n=m^2? But how would that help me. I mean if you take the square root then n might not possible be an integer anymore...
     
  7. Sep 13, 2007 #6
    If you've encountered modular arithmetic, use

    Code (Text):

    n (mod 5)     0  1  2  3  4
    n^2 (mod 5)   0  1  4  4  1
     
     
  8. Sep 13, 2007 #7

    StatusX

    User Avatar
    Homework Helper

    For any number m, you can write m=5q+r. So what is m2? Combine factors of 5 to see what the remainder is for different r.
     
  9. Sep 13, 2007 #8
    Okay, I think I'm getting the general idea. I know that r can only be 0,1,2,3 or 4, but when m is squared, those numbers still have to be lower than five, so 0^2 is less than five, as is 1^2 and 2^2. Am I on the right track?
     
  10. Sep 13, 2007 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, there are five possible remainders, but squared and taken mod 5 there are only three.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook