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!
 A: 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.
A: Suppose m,n  are the largest integers such that $N=mp+r=nq+r'$ for some $0\le r\lt p,0\le r'\lt q$. Then $p, 2p,... ,(m-1)p$ divided by $N$ have remainders equal to themselves. Similarly, the remainders of $q,...,(n-1)q$ divided by $N$ are themselves.
If $r=0, mp$ divided by $N$  have remainder $0$, otherwise it has remainder $mp$, and similarly for $r'$.
Now, for any $k\in \Bbb N, (m+k)p\equiv kp-r (\mod N)$. If $kp-r\gt N$, we can find some $k'$ such that $kp-r\equiv k'p-ur(\mod N)$ and $k'p-ur\le N$ for some $u\in \Bbb N$.  When $kp-r\le N=mp+r\implies (k-m)p\le 2r\lt 2p\implies k\lt m+2\implies k\le m+1$. When $kp-r\gt N,$ we may just consider $k'p-ur\le N=mp+r\implies (k'-m)p\le (u+1)r\lt (u+1)p\implies k'\le m+u$
Notice that for any $k'$ and $u$ we have $(k'-1)p-(u-1)r\lt k'p-ur\lt k'p-(u-1)r$. Hence $$R_1=\{p,...,(m-1)p,mp\;\text{or} \;0,p-r,...,mp-r,(m+1)p-r,p-2r,...,(m+2)p-2r,...\}$$ Similarly, $$R_2=\{q,...,(n-1)q,nq\;\text{or} \;0,q-r',...,nq-r',(n+1)q-r',q-2r',...,(n+2)q-2r',...\}$$
Then our desired result is clear.
(This is due to FormulaWriter: Notice that $|R_1|=N$ regardless of $m$ if and only if $N, p$ are coprime.)
