MHB Resurrecting a previous post. Coprime mod n implies coprime-ish mod n.

[caffeinemachine]

This was a question posted a long time ago by Swlabr but somehow the thread died.
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?$$.This was my response.
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$.

Ideas anyone?

The original thread is http://www.mathhelpboards.com/f15/coprime-mod-%24n%24-implies-coprime-ish-mod-%24n%24-624/#post3495

 

[melese]

Re: ressurecting a previous post. Coprime mod $n$ implies coprime-ish mod $n$.

Here's what I think,
From $ap + bq+n \gamma =1$, it's evident that $(a,b)$ is coprime to $\gamma$. Then I look for solutions in the form $p'=p+nx$,$q'=q+ny$, so if we want $ap'+bq'=1$ we are led to $ax+by=\gamma$, which has a solution.

 

[caffeinemachine]

Re: ressurecting a previous post. Coprime mod $n$ implies coprime-ish mod $n$.

Here's what I think,
From $ap + bq+n \gamma =1$, it's evident that $(a,b)$ is coprime to $\gamma$. Then I look for solutions in the form $p'=p+nx$,$q'=q+ny$, so if we want $ap'+bq'=1$ we are led to $ax+by=\gamma$, which has a solution.

Hey melese! You have helped me a lot at MHF(I used abhishekkgp as my nick there). Thanks for showing interest in this thread.

Now, from what I understand you use the fact that $ax+by=\gamma$ has a solution. Ok.. I'll assume, for the moment, that it does. Write $g=\gcd(a,b)$. This would mean that $g| \gamma$. But from $ap+bq+n\gamma=1$ we'd have $g|1$ as $g$ divides $a,b$ and $\gamma$. This would force that $\gcd(a,b)=1$ which is not a necessity in the hypothesis.