How to solve $a x \equiv 1 \pmod{b y}$?

76 Views Asked by At

Is there a mathematical formula (not include iteration nor recursive) which can solve $a x \equiv 1 \pmod{b y}$ ?

Note: $a$ and $b$ are certain integers, while $x$ and $y$ are arbitrary integer which are aimed to be found out.

Moreover, $ gcd (a,b) = 1$.

1

There are 1 best solutions below

2
On BEST ANSWER

If you assume $\gcd(a,b)=1$, then you can pick any $y\in\mathbb{Z}\setminus \{0\}$ such that $\gcd(a,y)=1$, thus $\gcd(a,by)=1$ and from Euler's theorem $$a^{\varphi(by)}\equiv 1 \pmod{by}$$ where $x=a^{\varphi(by)-1}$. For instance you can consider $y=k\cdot a +1$, for some $k\in \mathbb{Z}$.


If $\gcd(a,b)=d>1$ (or $a=a_1d$, $b=b_1d$) and you assume a solution $(x,y)$ exists, i.e. $ax\equiv 1\pmod{by}$, which means $ax-1=k\cdot by$ for some $k\in\mathbb{Z}$, then $$ax-k\cdot by=1 \Rightarrow d(a_1x-k\cdot b_1y)=1 \Rightarrow d \mid 1$$ which is a contradicton.