Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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