3
$\begingroup$

If I have a modulo operation like this:

$(a ( b+cd ) ) \equiv 0 \pmod{e},$

How can I derive $c$ in term of other variables present here. I.e. What function $f$ can be used such that:

$c = f (a,b,d,e) $

And what is the implication of a mod operation's result being $0$ in terms of simplifying the equation.

Thank you very much for your time.

2 Answers 2

4

You cannot express $c$ as a function of $a,b,d,e$, notably as $e$ varies there will be values for which no $c$ exists, and others for which it is not unique. However if one restricts to the cases where $a$ and $d$ are invertible modulo $e$, meaning that there exist numbers $i_a,i_d$ with $ai_a\bmod e=1=di_d\bmod e$, then $c$ exists, is unique modulo $e$, and is given by $ c\equiv d^{-1}(-b) \pmod e $ where $d^{-1}$ is the more usual notation for the number $i_d$ above. Neither $a$ nor the inverse $i_a$ of $a$ occur in the formula, but if $a$ has no inverse modulo $e$ then there are other values for $c$ than the above.

2

EDIT
My original solution to this problem was, in hindsight, radically overcomplicated. I have it below the modified post.

We have $a(b + dx) \equiv 0 \mod e$, or equivalently $ab + adx \equiv 0$, or equivalently $(ad)x \equiv -ab \mod e$. This is a very well understood subset of the problem on solving $ax \equiv b \mod m$. It turns out that there are solutions iff $(ad, e) | (-ab)$, and if there are any solutions than there are exactly $(ad,e)$ of them.

This is the Linear Congruence Theorem. In fact, my previous answer is sort of a skim of the ideas behind the proof, in a sense. And although it gives a clear record of my overcomplicating a problem, I think there is a certain amount of illustrative-ness behind it.

Original answer

So we have $a(b + cd) \equiv 0\mod e$.

If we are lucky, and in partcular that $a,b,c,d,e \neq 0$ and $(a,e) = (b,e) = (c,e) = (d,e) = 1$, i.e. that everything is coprime with $e$, then we have that $c \equiv d^{-1} (-b) \mod e$. In fact, we don't actually require $b$ or $c$ to be coprime to $e$ for this to work, as we just wanted to 'cancel' off the $a$ and be able to write down $d^{-1}$.

Otherwise, the solution may not be well-defined, or rather is a family of solutions. To vastly simplify, suppose we have something like $6(1 + c)\equiv 0 \mod 18$. Then $c \equiv 2, 5, 8, 11, 14, 17$ are all solutions.

The general idea to finding the solutions to problems like $6(1+c) \equiv 0 \mod 18$ involve noting that $(6,18) = 6$, and so by dividing out by $6$ we get $(1+c) \equiv 0 \mod 3$. This is not the same equation, but it tells us that $c \equiv 2 \mod 3$, and a quick check shows that $2,5,8,11,14,17$ are all solutions. What we really looked at were the congruences $(1+c) \equiv 0, 3, 6, 9, 12, 15 \mod 18$, as multiplying all of these by $6$ yield the original congruence. In fact, you might see that there are $6$ of them - and this is not a fluke.

So in your case, with $a(b+cd) \equiv 0 \mod e$, you might first do a 'reduction' to account for $(a,e) > 1$. Afterwards, you can effectively ignore the $a$, but remember that it incorporates $(a,e)$ distinct solutions. You are then left with $cd \equiv -b \mod e$, and this is a classic problem. I link to the Linear Congruence Theorem below for more on this.

Let's do a quick example, illustrating the method and a potential problem. $3(1 + 2c) \equiv 0 \mod 18$. We see that $(3,18) = 3$, so we look at $(1 + 2c) \equiv 0 \mod 6$ or $2c \equiv 4 \mod 6$. But what we really wanted was $1+2c \equiv 0, 1+2c \equiv 6,$ and $1+2c \equiv 12 \mod 18$. So we get that $2c \equiv 5, 11, 17 \mod 18$. We could proceed, but it's easy to see here that none of these have a solution. Working $\mod 18$, the left side is always even and the right sides are always odd.

It turns out that the congruence $ax \equiv b \mod m$ has a solution iff $(a,m)|b$. So if we define $e' := e/(a,e)$, then $a(b + xd) \equiv 0 \mod e$ will have solutions iff $(d,e') | (e'-b)$. In the (non)example abolve, we required $(2,6) = 2 | 1$, which it doesn't. But if you repeat with $3(2 + 2c) \equiv 0 \mod 18$, there will be solutions. (Answer: They are $2, 5, 8, 11, 14, 17$, with a total of $6$ coming from the $3$ from $(3,18) = 3$, each having $2 = (2, 6)$ solutions of their own. Food for thought: is it possible that there are fewer than (a,e)(d,e') due to some overlap?)

To save this answer from becoming too long, I will recommend sources of study. For further reading, I recommend looking into what wikipedia calls the Linear Congruence Theorem, which talks of the general solvability of equations like ax \equiv b \mod m$, and the Chinese Remainder Theorem. In addition, almost any introductory book on number theory will cover this sort of reasoning. I am particularly fond of recommending Rosen's Elementary Number Theory and Ireland and Rosen's Classical Introduction to Modern Number Theory, which is harder, and by a different Rosen.