so I have this problem and I'm running into some issues with it. Suppose we have the following system of equations -

$$-1 \equiv (x\times y)~ mod ~(z)$$ $$-1 \equiv (x\times z)~ mod ~(y)$$ $$-1 \equiv (y\times z)~ mod ~(x)$$

I'd like to find integer solutions to this equation. Are there any at all? How to tell? This system of congruences appears to conform to a Chinese remainder theorem type of question, where it would then follow that -

$$-1 \equiv [\sum(a_i~\times~b_i~\times~\frac{M}{m_i})]~ mod ~M$$

As can be found here - http://mathworld.wolfram.com/ChineseRemainderTheorem.html

The question is in the detail of the formulation of the solution. Since $x, y, z$ are arbitrary, how to find their multiplicative inverses in some modular class? I.e. How to find the multiplicative inverse of $(x\times y) ~mod ~z$? Named in wolfram's formulation $b_i$. Another point is that if you notice, in the summands, we multiply by $M$ and then take the entire sum $mod ~M$. Wouldn't the sum be congruent to $0$ in that case?

  1. One result the professor has been alluding to the entire semester, is the fact that if a statement is true in Z, then it is true in Z(p) for any prime p. This seems to make sense, since the primes generate the integers. However, could someone point me to the formal statement of that theorem?
  • $\begingroup$ If a polynomial equation with integer coefficients has a solution in integers, then it has a solution mod $m$ for every $m$, "Statement" is too general. $\endgroup$ – André Nicolas Sep 15 '15 at 4:43
  • $\begingroup$ would you write your system of equations as separate sentences with punctuation so we can make sense of it? $\endgroup$ – DanielWainfleet Sep 15 '15 at 17:41

An example, how inverses are found.

Assume, $28$ has to be inverted modulo $33$

The calculation of the gcd

$$33=1\times 28+5$$

$$28=5\times 5+3$$

$$5=1\times 3+2$$

$$3=1\times 2+1$$

can be worked backwards leading to

$$1=3-2=3-(5-3)=2\times 3-5=2\times(28-5\times5)-5=2\times 28-11\times 5$$

$$=2\times 28-11\times(33-28)=13\times 28-11\times 33$$

So, $28^{-1}\equiv 13\ (\ mod\ 33\ )$

If the equation would be $1=(-10)\times 28+4\times 33$ (which is of course not the case, but I want to explain how to deal with negative multiplicators), for instance, we would have $28^{-1}\equiv 33-10=23\ (\ mod\ 33\ )$

  • $\begingroup$ Hm, thanks. But even still, when x, y, z are arbitrary, I cannot use this algorithm. For one thing, I cannot determine the base case for when the remainder is = 1. $\endgroup$ – Joe Shmo Sep 16 '15 at 23:24

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.