I appreciate the answer to my previous question, but I still felt my larger question wasn't answered.
So, I am attempting to restate the question more clearly.
If $x,y$ are integers where $x | \varphi(y)$ and $x$ and $y$ are relatively prime, does it follow that the reduced residue class modulo $y$ divides evenly into congruence classes modulo $x$?
If $x,y$ are integers where $x | \varphi(y)$ and $x$ and $y$ are not relatively prime and the number of congruence classes relatively to prime to $y$ also divide into $\varphi(y)$, then the reduced residue class modulo $y$ divides evenly into congruence classes that are relatively prime to $y$.
Is this always the case? If not, can you provide a counterexample to either condition?
Let me give examples of both and an example where the congruence classes that are relatively prime to $y$ do not divide $\varphi(y)$:
Example 1: Where $x$, $y$ are relatively prime. If we look at $y=35$ and $x = 3$, we have $\varphi(35)=24$ and we see that there are:
- $8$ elements $\{3, 6, 9, 12, 18, 24, 27, 33\}$ that are congruent to $0$ modulo $3$
- $8$ elements $\{ 1, 4, 13, 16, 19, 22, 31, 34\}$ that are congruent to $1$ modulo $3$
- $8$ elements $\{ 2, 8, 11, 17, 23, 26, 29, 32\}$ that are congruent to $2$ modulo $3$
Example 2: Where $x$, $y$ are not relatively prime. If we look at $y=12$ and $x=4$, we see that $\varphi(12)=4$ and we see that:
- $2$ elements $\{1, 5\}$ that are congruent to $1$ modulo $4$
- $2$ elements $\{7, 11\}$ that are congruent to $3$ modulo $4$
Example 3: Where $x$, $y$ are not relatively prime and the number of congruence classes from $x$ that are relatively prime to $y$ do not divide $\varphi(y)$.
In this case, it is not possible for the congruence classes to evenly divide. An example of this is $y=9$ and $x=6$, we see that $\varphi(9)=6$.
In this case, the number of congruence classes that are relatively prime to $9$ is $4$ which are $\{1, 2, 4, 5\}$. Since $4$ does not divide $6$, it is clear that the reduced residue class modulo $9$ cannot be evenly divided across the congruence classes of $6$ which are relatively prime to $9$.
Edit: I added example 3 to the question based on the question here. Example 3 is from a comment there.
I think that I found an argument for a condition when $x$ and $y$ are relatively prime and example 1 holds true. Please post a comment if you see any mistakes in my reasoning or if you have a suggestion for improving the argument:
(1) If $y$ is a prime, then it is true since $1 \cdots y-1$ form $\frac{y-1}{x}$ distinct complete residue systems modulo $x$.
(2) Assume it is true up to $y_0$ so that the reduced residue class of $y_0$ divides equally into distinct congruence classes modulo $x$.
(3) Let $p$ be any prime that is relatively prime to $x$.
(4) The sequences $1 \cdots y_0$, $y_0+1 \cdots 2y_0, \cdots, (p-1)y_0 \cdots p{y_0}$ form $p_i$ complete residue systems modulo $y_0$.
(5) Let $R_1, R_2, \cdots, R_{p}$ be the reduced residue systems modulo $y_0$ for each of these $p$ complete residue systems.
(6) We know that if $r \in R_1$, then $r+y_0 \in R_2, r+2*y_0 \in R_3, \cdots, r+(p-1)*y_0 \in R_{p}$.
(7) We also know that since $y_0$ is relatively prime to $x$, all elements of each $R_i$ must likewise be equally divided into congruence classes modulo $x$.
[Clearly if $c_i \not\equiv c_j \pmod x$, then $c_i + y_0 \not\equiv c_j+y_0 \pmod x$]
(8) Now $1 \in R_1$. Let $r_{2,i}$ be the first element in $R_2$ such that $r_{2,i} \equiv 1 \pmod x$. Let $d = r_{2,i}-1$.
(9) If $p \nmid d$, then there is $d'$ such that $r_i, r_i+d', r_i+2d', \cdots, r_i+p*d'$ forms a complete residue system modulo $p$ where $r_i \equiv r_i+d' \equiv r_i+2d' \equiv \cdots \equiv r_i+p*d' \pmod x$
(10) If $p \mid d$, then it follows that $d \ge p*x$ and $\exists c \ge 1$ where $d=p_i*c*x$ and $1+(c*p-1)*x < y_0 < 1+c*p*x < 1+(c*p+1)*x < 1+(c*p-1)*2*x < 2y_0$
(11) It follows that $p \nmid d+p_i$ and each $r_i,r_i+d',\cdots,r_i+(p-1)*d'$ forms a complete residue system modulo $p$ where $r_i \equiv r_i+d' \equiv r_i+2d' \equiv \cdots \equiv r_i+(p-1)*d'$
It looks like this statement is not necessarily true if $x$ and $y$ are relatively prime. My argument only holds for when there is a prime $p$ such that $x \mid p-1$. But this is not always the case.
For example, let $x=4$, $y=21$ and $\varphi(21) = 12$. But in this case the reduced residue class modulo $y$ does not evenly divide into congruence classes modulo $4$ since the reduced residue class is $\{ 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20 \}$ and $4$ of them are divisible by $4$.
I'll continue to update my answer if I can clean up my analysis, someone spots a mistake, or if I can generalize my proof to cover the condition where $x$ and $y$ are not relatively prime.