Congruent Module n Theorm

1. Jun 20, 2014

PsychonautQQ

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. Jun 20, 2014

bloby

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$.

3. Jun 20, 2014

HallsofIvy

Staff Emeritus
If a is any integer then, for any positive integer, n, we can write a= qn+ r for a and r integers and$0\le r< n$. 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 $x= q_1n+ r_1$ and $y= q_2n+ r_2$ for some integers $q_1$, $q_2$, $r_1$, and $r_2$. Then $x- y]= q_1n+ r_1- (q_2n+ r_2)= (q_1- q_2)n+ (r_1- r_2)$. Since $r_1$ and $r_2$ 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 $r_1- r_2= 0$ or $r_1= r_2$. 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.

4. Jun 21, 2014

PsychonautQQ

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?