I have 2 known positive integers, $a$ and $b$ . Is there a ' standard ' formula to find the lowest (if possible) positive integers $x$ and $y$ , so that the following is true?
$$xa = yb + 1$$
Asked
Active
Viewed 81 times
0
-
1Have you seen Bezout's Lemma? – Rushabh Mehta Jan 03 '20 at 16:37
-
Are you familiar with modular arithmetic and congruency ? – The Demonix _ Hermit Jan 03 '20 at 16:37
-
1Look up the 'Euclidean algorithm' – Empy2 Jan 03 '20 at 16:37
-
Take $a=2$ and $b=4$. Then there are no such integers $x,y$, because $xy-yb$ is even. For coprime $a$ and $b$ just use Bezout's Lemma. – Dietrich Burde Jan 03 '20 at 16:37
-
2Integers $x,y$ can be found iff $\gcd(a,b)=1$. Since in at least some cases one of $x,y$ may be negative, it is not clear what you mean by making $x,y$ the lowest. One possibility is $|xy|$ is minimized. – Keith Backman Jan 03 '20 at 16:51
-
I only know that `b` will always be prime. And it doesn't necessarily need to be the 'lowest' answer, I just need _a_ answer. Thanks for the response by the way! – DanDeg Jan 03 '20 at 18:54
-
@DanDeg So what you seek is the inverse of $\,a\,$ modulo a prime $\,p,\,$ for which there are various well known algorithms - see the linked dupes. – Bill Dubuque Jan 03 '20 at 20:43