Question about congruence classes and reduced residue systems

Question

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!

Answer 1

This is a rather interesting question, which I found quite challenging to properly solve and then write this answer. Your conjecture is correct, but I have a few suggestions and there are several issues with your proof.

In your argument $(2)$, although it's supposed to be about $R_{y,i}$ for all $i$, it only discusses going from $R_{y,1}$ to $R_{y,2}$, with it implicitly assuming this is to be extended appropriately for all $i$. Also, it's not necessary to consider if $x \mid y$ because $x$ and $y$ must be relatively prime. Otherwise, if $\gcd(x, y) = d \gt 1$, then no element of the reduced residue system modulo $y$ has a factor of $d$. Thus, it wouldn't include any of the congruence classes $md \; \forall \; 0 \lt m \le \frac{x}{d}$ modulo $x$, contradicting that each of these classes are equally represented.

Your $(3)$ states you "... can find an $r_{y,2}$ with the same congruence class modulo $x$ but a difference congruence class modulo $z$". The lower-case $r$ values are apparently meant to represent elements from the corresponding $R$ sets, but you should make this explicit. Also, I assume "difference" is meant to be "different", but you don't explain how & what it's different from. Nonetheless, since your third bullet point states "... distinct pairings of $z$ elements each", it seems the term different means distinct. However, a more significant issue is your fourth bullet point which states

• This would then show that each pairing of $z$ elements forms a complete residue system modulo $z$.

You're trying to prove the congruence classes modulo $x$ are all equally represented, so it's not clear, at least to me, how having a complete residue system modulo $z$, which is relatively prime to $x$, would show the conjecture is true.

Here's how I would prove your conjecture instead. First, it's easier to deal with multiplying the value of $y$ by one prime at a time, since if the conjecture is proven true for any given prime, the steps can be repeated for each prime in turn to end up with the result for $z$. Note if $z = 1$, then there's nothing more to do. Otherwise, with $z \gt 1$, let

$$z = \prod_{i=1}^{n}p_i \tag{1}\label{eq1A}$$

where the $p_i$ are all of the $n \ge 1$ (not necessarily distinct) prime factors of $z$. Next, follow the procedure below to handle each of these primes in turn.

1. Let $C_{x}$ be the complete residue system of integers modulo $x$ in $[1, x]$. Set $y_1 = y$ and $i = 1$.
2. Set $w_i = y_i \times p_i$ and let $R_{t}$ be the set of elements in $[1, w_i]$ which are coprime to $y_{i}$. As you basically did, let $R_{y_i}$ be the reduced residue system modulo $y_i$ of the integers in $[1, y_i]$. For each $e \in R_{y_i}$, since $\gcd(e, y_i) = 1$, then $\gcd(jy_i + e, y_i) = 1$ for each $1 \le j \lt p_i$. As well, for any $1 \le f \le y_i$ where $\gcd(jy_i + f, y_i) = 1$, then $\gcd(f, y_i) = 1$ meaning $f \in R_{y_i}$. Thus, there's a one-to-one mapping between the elements of $R_{y_i}$ and the integers coprime to $y_i$ in each $[jy_i + 1, (j + 1)y_i]$ region, so each of these regions has $|R_{y_i}|$ elements. Also, each congruence class $g \in C_{x}$ is shifted by $jy_i$ in $[jy_i + 1, (j+1)y_i]$ compared to $[1, y_i]$, so since each shift is to a unique congruence class, there's no change in how many there are of each congruence class. Thus, adding all of these same number of elements together for each $j$ means the number of elements of each congruence class in $C_{x}$ in $R_{t}$ is $p_i$ times the number in $R_{y_i}$. This is basically the argument you used in your $(2)$.
3. Have $R_{w_i}$ be the reduced residue system modulo $w_i$ in $[1, w_i]$. If $p_i \mid y_i$, since there are no elements to remove, set $R_{w_i} = R_{t}$ and skip to $5$.
4. Creating $R_{w_i}$ from $R_{t}$ requires removing all $mp_i, 1 \le m \le y_i$. Since all such $mp_i$ where $m$ is not relatively prime to $y_i$ are already not in $R_{t}$, the only ones remaining to take out are those where $m \in R_{y_i}$. This means the set of $mp_i$ integers to remove is composed of each congruence class of $h \in C_{x}$ of elements in $R_{y_i}$ being mapped to $hp_{i}$. The destination mapping is unique since if congruence classes $h_1, h_2 \in C_{x}$ have $h_1p_{i} \equiv h_2p_{i} \pmod{x}$, then $(h_i - h_2)p_i \equiv 0 \pmod{x}$, but $\gcd(p_i, x) = 1$ means $h_1 = h_2$. Thus, for each $h$, the number of elements of $hp_i$ to remove in $R_{t}$ are the same. Since the number of elements of each congruence class $g \in C_{x}$ in $[1, w_i]$ were the same in $R_{t}$, they will now be fewer, but still equal to each other, after removing any multiples of $p_i$ from that set to get $R_{w_i}$.
5. Set $y_{i + 1} = w_{i}$. If $i = n$, then exit these steps. Otherwise, increment $i$ and go to $2$.

The final $y_{n + 1}$ is your $y*z$, with the reduced residue system modulo $y_{n+1}$ of $[1, y_{n+1}]$ being divided equally among each of the congruence classes modulo $x$.