Suppose I have the following simple congruence $bx \equiv y$ (mod $p$) where $p$ is a prime.
I was wondering if I could keep replacing $b$ with any of the following until $b$ would reach $1$ and therefore solving for $x$:
$b' = p - kb$ for some integer $k$, which is really $p$ mod $b$,
$b' = b - qp$ for some integer $q$, which is really $b$ mod $p$.
Let's say we have $9x \equiv 3$ (mod $5$) and that I can replace coefficient of $x$ by any of the above:
- So first step I do $b$ mod $p$: $4x \equiv 3$ (mod $5$)
- Then $p$ mod $b$: $x \equiv 3$ (mod $5$), but this is wrong, it should be $-3$.
If I write this out with variables I should be able to do all of this:
$bx \equiv y$ (mod $p$)
$(p-kb)x \equiv y$ (mod $p$), or
$(b - qp)x \equiv y$ (mod $p$).
In the end it seems that the sign of the final result is always wrong, as in the above example I got $3$, but the correct is $-3$. Can someone tell me what am I doing wrong here?
Bill Dubuque showed a similar thing here: Euclid lemma proof