# Question about congruence classes and reduced residue systems

Let $x$,$y$ be integers such that the reduced residue system modulo $y$ divides equally into congruence classes modulo $x$.

An example of this is $x=4$, $y=5$.

• The reduced residue system modulo $5$ is $\{1,2,3,4\}$
• These divide evenly into congruence classes of $4$ (one element to a congruence class).

Another example of this is $x=4$, $y=13$

• The reduced residue system modulo $13$ is $\{1,2,3,4,5,6,7,8,9,10,11,12\}$
• These equally divide into the congruence classes of $4$ since each class consist of the same number of elements (3 elements to a class each):
• $\{1,5,9\}$ congruent to $1 \pmod 4$
• $\{2,6,10\}$ congruent to $2 \pmod 4$
• $\{3,7,11\}$ congruent to $3 \pmod 4$
• $\{4,8,12\}$ congruent to $0 \pmod 4$

Is it always true that for any integer $z$ that is relatively prime to $x$, the reduced residue system modulo $y*z$ will also equally divide into congruence classes modulo $x$?

Here's an example of what I am talking about.

Let $z$ be $3$ which is relatively prime to $4$ with $x=4, y=5$

• The reduced residue system modulo $15$ is $\{1,2,4,7,8,11,13,14\}$
• These divide evenly into congruence classes of $4$ (two elements to a congruence class)
• $\{1,13\}$ congruent to $1\pmod 4$
• $\{2,14\}$ congruent to $2\pmod 4$
• $\{4,8\}$ congruent to $0\pmod 4$
• $\{7,11\}$ congruent to $3\pmod 4$

In this case, there $8$ elements in the reduced residue class and all congruence classes of $4$ are included an equal number of times.

Does it always follow that if $x,y$ have the relationship described, that for any integer $z$ that is relatively prime to $x$, that $y*z$ will also have this relationship? I believe that the answer is yes. I am trying to work on the argument that establishes this.

Here's the approach that I came up with:

(1) $y*z$ consists of $z$ complete residue systems modulo $y$:

• $C_{y,1}: 1 \cdots y$
• $C_{y,2}: y+1 \cdots 2y$
• $\cdots$
• $C_{y,z}: (z-1)*y+1 \cdots yz$

(2) For each complete residue system, $R_{y,i}$, the elements will equally divide into the congruence classes modulo $x$.

Argument: If $r \in R_{y,1}$, then $r+y \in R_{y,2}$. So, it follows if $x \mid y$, then $r + y \equiv r \pmod x$. If $x \nmid y$, then each element has a one-to-one mapping with a different congruence class. Since each class of element maps to the same distinct class in $R_{y,2}$, the result follows.

(3) To complete the argument, I want to show that I can take $z$ elements from $R_{y,1}, R_{y,2}, \cdots, R_{y,z}$ such that:

• For each $r_{y,1}$ I take, I can find an $r_{y,2}$ with the same congruence class modulo $x$ but a difference congruence class modulo $z$.
• I can repeat this process for $r_{y,3}$ and so on up until $r_{y,z}$.
• I can do this to the point that I have $\varphi(y)$ distinct pairings of $z$ elements each.
• This would then show that each pairing of $z$ elements forms a complete residue system modulo $z$.

Is there an easier way to prove this? Is my reasoning sound? Is there a more elegant way to complete the argument than my proposed step #3? How would you state the argument for step #3?

Thanks very much!

• Please give a precise definition and/or an example of what you mean by "reduced residue system modulo y divides equally into congruence classes modulo x." $\ \$ – Bill Dubuque Jan 18 '14 at 19:29
• Thanks for comment! I've updated the question to add more examples. I mean that if you divide up the reduced residue system modulo y into congruence classes modulo x, you will get the same number of elements in each congruence class. – Larry Freeman Jan 18 '14 at 19:41
• Both examples are lacking the $\;0\;$ (zero) residue... – DonAntonio Jan 18 '14 at 20:18
• @Don, I am not clear on your point. Isn't $4 \equiv 0 \pmod 4$? – Larry Freeman Jan 18 '14 at 20:55
• Once again, @LarryFreeman: the list you gave of the residues modulo $\;13\;$ is not complete: there's lacking the residue $\;0=-13=13=26=-39\;$ , etc. Of course, it may be that you're interested in the non-zero residues modulo a prime...? About your question: your two examples $\;(5,13)\;$ are primes equal to $\;1\pmod 4\;$ so what you want will always work. But now try a prime $\;=3\pmod 4\;$ , say $\;7\;$ : the non-zero residues are $\;\{1,2,3,4,5,6\}\;$ and there's only one thate equals zero or three modulo $\;4\;$ , but two that equal $\;1\;or\;2\pmod 4\;$ ... – DonAntonio Jan 19 '14 at 4:02