# Replacing coefficient of congruence

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 do it only when $p\not | b$. If it doesn't divide, then there is a $b'$ such that $bb'\equiv 1\mod{p}$. Multiplying by this $b'$ makes the coefficient of $x$ 1. – rationalpi Feb 12 at 9:10
• @rationalpi $p$ and $b$ are coprime and I know that inverse exists, I am trying to understand why replacing $b$ by what I have shown gives incorrect sign to the solution. – Michael Munta Feb 12 at 10:10

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.

• Actually now that I think about it it is possible. We want $(p - kb)x \equiv y$ to appear so we have to multiply both sides of $bx \equiv y$ by $k$ to get $kbx \equiv ky$. $kbx$ should be negative so we also multiply both sides by $(-1)$. Now we have $-kbx \equiv -ky$. Adding $px \equiv 0$ (mod $p$) on the left side of the congruence we get $px - kbx \equiv -ky$ (mod $p$), which is $(p - kb)x \equiv -ky$ (mod $p$). We can iterate like this until reaching $1$ and we will have a solution for $x$ and also if we multiply all the $k$'s we used in the algorithm we will get inverse of $b$ mod $p$. – Michael Munta Feb 12 at 22:17
• @MichaelMunta Note that the new equation of $\left(p - kb\right)x \equiv -ky \pmod p$ is not the same as the original one of $bx \equiv y \pmod p$ where $b$ is replaced by $b' = p - kb$. I provided my answer based on what you were asking in the question. Also, keep in mind your new equation comes from just multiplying both sides by $-k$ to get that $-kb \equiv -ky \pmod p$. If you are willing to iterate through all congruences, it's generally simpler & easier to just do that for all $b$ to find which one gives $bx \equiv y \pmod p$. Is there any particular reason you don't want to do that? – John Omielan Feb 12 at 22:22
• No particular reasons. Just wanted to see if something like this was possible. – Michael Munta Feb 12 at 22:27
• @MichaelMunta By changing the equation as you describe in your comment above, it is possible as we both agree. However, I don't see any advantage you will usually get by doing it. Nonetheless, I encourage you to keep trying things like this to both learn more and, you never know, you might find something new & useful some day as well. – John Omielan Feb 12 at 22:29