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$,
or
$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
You can certainly replace $b$ with anything which is congruent to it modulo $p$, such as the second case of $b' = b - qp$ for some integer $q$. However, there is usually no direct connection to the original modular equation if you replace $b$ instead by something which is congruent to p mod b, such as your first case of
$$b' = p - kb \equiv -kb \pmod p \tag{1}\label{eq1}$$
for some integer $k$. To see this, replacing $b$ with $b'$ in the original modular equation of
$$bx \equiv y \pmod p \tag{2}\label{eq2}$$
gives
$$b'x \equiv y \pmod p \; \; \Rightarrow \; \; \left(-kb\right)x \equiv y \pmod p \tag{3}\label{eq3}$$
Next, \eqref{eq2} - \eqref{eq3} gives
$$\left(k + 1\right)bx \equiv 0 \pmod p \tag{4}\label{eq4}$$
Thus, this requires that $k + 1$, $b$ and/or $x$ be a multiple of $p$. Unless $y$ is a multiple of $p$, this means that $k \equiv -1 \pmod p$, so \eqref{eq1} gives that $b' \equiv b \pmod p$, i.e., it doesn't change the original modular equation of \eqref{eq2}.
With your example in the question text of $9x \equiv 3 \pmod 5$ and $x \equiv 3 \pmod 5$, note that subtracting the second from the first gives $8x \equiv 0 \pmod 5$, so $x \equiv 0 \pmod 5$, but then you can't have $9x \equiv 3 \pmod 5$! Using a $k \not\equiv -1 \pmod p$ will usually lead to a contradiction like this, or at least it will not give you the correct answer, depending on what steps you follow.