MHB Coprime mod n implies coprime-ish mod n

[Swlabr1]

Let $a$ and $b$ be two integers such that there exists integers $p$, $q$ with $ap+bq=1\text{ mod }n$. Do there exist integers $a^{\prime}$ $b^{\prime}$, $p^{\prime}$ and $q^{\prime}$ such that, $x^{\prime}=x\text{ mod }n$ for $x\in\{a, b, p, q\}$ and, $$a^{\prime}p^{\prime}+b^{\prime}q^{\prime}=1?$$

 

[caffeinemachine]

Re: Coprime mod $n$ implies coprime-ish mod $n$

Let $a$ and $b$ be two integers such that there exists integers $p$, $q$ with $ap+bq=1\text{ mod }n$. Do there exist integers $a^{\prime}$ $b^{\prime}$, $p^{\prime}$ and $q^{\prime}$ such that, $x^{\prime}=x\text{ mod }n$ for $x\in\{a, b, p, q\}$ and, $$a^{\prime}p^{\prime}+b^{\prime}q^{\prime}=1?$$

If $\gcd (a,b)=1$ then yes.

$ap+bq \equiv 1 \mod n$ means there exist integer $\gamma$ such that $ap + bq+n \gamma =1$ . If $\gcd (a, b)=1$ then $\exists k_1, k_2$ such that

$ak_1+bk_2=\gamma$.

Take $a{'} =a, b{'}=b, p{'}=p+nk_1, q{'}=q+nk_2$

Then $a{'}b{'} +b{'}q{'}=1$

I am not sure what happens when $\gcd (a,b) \neq 1$.

Hope this helps.