# 'Coprime' problem related to integer rings

I am handling a problem involving the proof of whether two integers are coprime or not. Think of a positive integer $N$ and two integers $r$ and $s$ in $\mathbb{Z}_N$ such that $\gcd{(N, r)}=1$ and $\gcd{(N, s)}=1$ (so that both $r$ and $s$ have the multiplicative inverse in $\mathbb{Z}_N$.)

Then define $g=\gcd{(N, r-s)}$, $u=N/g$ and $v=(r-s)/g$. By doing that, we have $N=ug$ and $r-s=vg$ where clearly $\gcd{(u, v)}=1$.

Let $r^{-1}$ and $s^{-1}$ be multiplicative inverse of $r$ and $s$ in $\mathbb{Z}_N$, respectively. Since $r-s\equiv 0 ~mod~ g$, we know $r \equiv s ~mod~ g$ and clearly $r^{-1} \equiv s^{-1} ~mod~ g$ and $r^{-1}-s^{-1}\equiv 0 ~mod~ g$. Thus we can let $r^{-1}-s^{-1}=v'g$.

Question: Are $u$ and $v'$ coprime like $u$ and $v$ are coprime?

Anyone who is good at number theory may help me. Thank you in advance.

Yes, $u$ and $v'$ are coprime. This is equivalent to the statement: $$\gcd(N, r-s) = \gcd(N, r'-s')$$ whenever $r', s'$ satisfy $rr'\equiv ss'\equiv 1\mod{N}$.

To prove this, notice that $r'-s'\equiv -(r-s)r's' \mod{N}$. Since $\gcd(-r's',N)=1$, it follows that $$\gcd(N, r'-s')=\gcd(N, (-r's')(r-s))=\gcd(N, r-s)$$ and the result follows $\square$

Yes they are. Suppose they weren't. We would have a $h$, divisor of $N$ with $h>g$ and $h|r^{-1}-s^{-1}$.

This would imply $r^{-1}\equiv s^{-1}\pmod h$, and by doing the same thing backwards, $r-s\equiv0\pmod h$, which contradicts the fact that $g$ was the gcd.

(Here one has to notice that the inverses modulo $h$ exist because $\gcd(r,h)|\gcd(r,N)=1$, so $\gcd(r,h)=1$.)