What is the significance of the division algorithm in congruent modules?

[PsychonautQQ]

Homework Statement

≈ → 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?

Homework Equations

The Attempt at a Solution

 

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

 

[HallsofIvy]

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.

 

[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?