1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

  • If $r_i$ is between $1$ and $2y_0-d-1$, then $d' = d$
  • If $r_i$ is between $2y_0 -d$ and $2y_0-1$, then $d' = d-y_0+1$

(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'$

  • If $r_i$ is between $1$ and $2y_0-(d+p)-1$, then $d' = d+p$
  • If $r_i$ is between $2y_0-(d+p)$ and $2y_0-1$, then $d' = d+p-y_0+1$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.