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: Congruent Module n Theorm

  1. Jun 20, 2014 #1
    1. The problem statement, all variables and given/known data
    ≈ → equivalence
    "In general, if a is an integer, the division algorithm gives a = qn + r, where 0 ≤ r ≤ n-1 so a≈r (mod n). Thus every residue class module n appears in the list [0], [1].....,[n-1]. In fact, it appears exactly once.

    I'm having trouble connecting the dots here, can anyone help me explain what this is saying exactly?

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Jun 20, 2014 #2
    Every class appears for if is any class ##b\approx r_b## for an ##r_b## given by the algorithm, that is =[##r_b##].
    It appears exactly once then means ##[r_i]\neq[r_j]## if ##i\neq j##.
  4. Jun 20, 2014 #3


    User Avatar
    Science Advisor

    If a is any integer then, for any positive integer, n, we can write a= qn+ r for a and r integers and[itex]0\le r< n[/itex]. That is the "Euclidean division algorithm" which basically says that if you divide a by n you get some quotient, q, and remainder r.

    "x is congruent to y modulo (not "module") n" if and only if x- y is divisible by n. By the Euclidean division algorithm, we can write [itex]x= q_1n+ r_1[/itex] and [itex]y= q_2n+ r_2[/itex] for some integers [itex]q_1[/itex], [itex]q_2[/itex], [itex]r_1[/itex], and [itex]r_2[/itex]. Then [itex]x- y]= q_1n+ r_1- (q_2n+ r_2)= (q_1- q_2)n+ (r_1- r_2)[/itex]. Since [itex]r_1[/itex] and [itex]r_2[/itex] are both non-negative and less than n, there difference is between -n and n. Since x- y is divisible by n, we must have [itex]r_1- r_2= 0[/itex] or [itex]r_1= r_2[/itex]. If x and y are equivalent modulo n (if x- y is divisible by n) then they have the same remainder when divided by n.

    That is, we can label the equivalence classes (set of numbers that are all equivalent to one another modulo n) by the remainders when the numbers in that equivalence class are divided by n. Given any number, x, its remainder, when divided by n, is an integer from 0 to n-1. Every integer is in exactly one of those classes because it has exactly one such remainder.
  5. Jun 21, 2014 #4
    If you divide x by n wouldn't you get x/n = q + r/n? isn't the remainder technically r/n and not just r? like say n = 5 and x = 17. 17/5 = 3 + r/5 so it seems that the real "remainder" here is going to be 2/5?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted