If $R_1$ and $R_2$ have the same cardinality, then $R_1 = R_2$ In proving one direction (the part at most) of this statement from Wikipedia



I re-phrase it as below theorem. Could you please leave me some hints (not involved modular arithmetic) to prove it.

Let

*

*$0<p<q < N$ be natural numbers.


*$R_1$ be the set of remainders when all multiples of $p$ is divided by $N$.


*$R_2$ be the set of remainders when all multiples of $q$ is divided by $N$.

If $R_1$ and $R_2$ have the same cardinality, then $R_1 = R_2$.

Thank you so much for your help!

HINT.
Let $a=\gcd (p,N).$ Let $p=p'a$ and $N=N'a.$ Then $\gcd(p',N')=1.$
Now $p'ax=px=Ny+r=N'ay+r$ with $r\in R_1$ iff $r=r'a$ for some  $ r'\in R'_1$, where $R'_1$ is the set of remainders when multiples of $p'$ are divided by $N'.$
So $R_1=\{ar': r'\in R'_1\}.$
Use $\gcd(p',N')=1$ to obtain $R'_1=\{0,..., N'-1\},$ which has $N'=N/a=N/\gcd(p,N)$ members.
