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: Mod or quotient remainder theorem (QRT)

  1. Mar 2, 2012 #1
    I have to prove this problem. For all n integers, if n mod 5 = 3, then n2 mod 5 = 4

    Proof: Let n be an integer such that n mod 5 = 3.
    n = 5k+3 for some integer k by definition of MOD or QRT?

    Which one would be correct? Am I using the definition of MOD or QRT? I'm thinking its QRT because its in the form of QRT but it could be mod since we know that 3 is the remainder by the definition of MOD. Not sure which one is correct
    Last edited: Mar 2, 2012
  2. jcsd
  3. Mar 2, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    Well, n mod 5=3 then n=5k+3 by the definition of mod. I'm not sure where you are going from there though.
  4. Mar 2, 2012 #3
    Sorry it was n2 not x, I just edited it.
  5. Mar 2, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper

    That makes more sense. But n mod 5=3 then n=5k+3 is just the definition of mod, right?
  6. Mar 2, 2012 #5
    Why woudn't it be the definition of QRT?
  7. Mar 2, 2012 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is kind of semantics. The QRT is what makes mod well-defined - if there were multiple remainders possible, then saying n=3 mod 5 doesn't make sense, because 2 might also be a remainder. Mod is (usually) defined as the remainder you get from the QRT - so n=3 mod 5 means that n=5k+3 by definition of mod, which only makes sense because of the QRT
  8. Mar 2, 2012 #7
    You mean n mod 5 = 3?

    I am only asking because my teacher is very strict about this stuff, he requires us to state all definitions used. But I think saying the definition of MOD would make more sense because QRT is kinda implied in def of MOD
  9. Mar 2, 2012 #8


    User Avatar
    Science Advisor

    i think this isn't even the right approach (you could get there from here, but it's the long way around).

    suppose we write [a]k, for the equivalence class (or residue class, i.e., the remainder upon division by k) of the integer a.

    then once can DEFINE: ([a]k)(k) = [ab]k.

    in particular, this means if: [n]5 = [3]5,

    that [n2]5 = [n]5[n]5 = [3]5[3]5 = ?
  10. Mar 2, 2012 #9

    My approach is correct, since I got the correct answer. I'm not quite sure what you are doing with the subscripts
  11. Mar 2, 2012 #10


    User Avatar
    Science Advisor
    Homework Helper

    Ack. I think everyone here knows what the correct answer is. There is some quibble about how to justify it, by the QRT or the definition of MOD. I'm having a hard time caring which.
  12. Mar 3, 2012 #11


    User Avatar
    Science Advisor

    my guess is, you are learning some number theory.

    my second guess is, you are more comfortable with writing:

    a = b + kn than:

    a = b (mod n).

    what i am "doing with the subscripts" is this:

    [a]n = b, where a = b + kn, and 0 ≤ b < n.

    the reason for the brackets is that [a]n = [a+n]n, that is: a = a+n (mod n), but surely a and a+n aren't the same integer.

    often, working with the integers mod n, the brackets are omitted (as being "understood we are working mod n").

    here's the thing:

    if a = b (mod n) and c = d (mod n), then (a+c) = (b+d) (mod n), and ab = cd (mod n).

    well there are only n "remainder classes" mod n. this reduces the (possibly infinite) number of cases about integers, to just n cases. one can consider "numbers of the form":

    0 + kn
    1 + kn
    2 + kn
    (n-1) + km

    but the arithmetic involved "carrying the terms involving n" is much more tedious to work with, and they don't affect the answer we're looking for. in other words, modular arithmetic is invoked to make things EASIER.

    you seem to be of the view, that as long as you get the correct answer correctly, that you're good. that is only half true. homework questions are not "real problems", they are usually "invented" by a professor or text author as "practice" to test your understanding of the ideas involved. later, you will use the ideas involved in situations where the "answer" may not be known. in such a situation, "checking to see if your answer is right" is useless, the only guide you have is your confidence in your methods.

    i sense a certain reluctance in you to embrace modular arithmetic. my suspicion is, this will not be a fruitful stategy for you in the long run, and may cause difficulties for you later on.


    as others have remarked in this thread, the definition of "MOD" and the "QRT" are mirrors of each other:

    a = b + kn if and only if a = b (mod n).

    if i (personally) am working thorugh an equation involving "divisibility by n":

    [a] = is much more straight-forward that a = b + kn, since i really don't care about which integer k is.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook