0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – rationalpi Feb 12 at 9:10
  • $\begingroup$ @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. $\endgroup$ – Michael Munta Feb 12 at 10:10
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Michael Munta Feb 12 at 22:17
  • $\begingroup$ @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? $\endgroup$ – John Omielan Feb 12 at 22:22
  • $\begingroup$ No particular reasons. Just wanted to see if something like this was possible. $\endgroup$ – Michael Munta Feb 12 at 22:27
  • 1
    $\begingroup$ @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. $\endgroup$ – John Omielan Feb 12 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.