1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    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


    User Avatar
    Homework Helper

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

    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


    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


    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