- Thread starter
- #1

- Mar 10, 2012

- 834

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-$n$-implies-coprime-ish-mod-$n$-624/#post3495

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-$n$-implies-coprime-ish-mod-$n$-624/#post3495

Last edited by a moderator: