1

I noticed that if we got a system of modular equations that all equals to $0$ we can always solve the system; for example in a system like this: $$\begin{cases}n \mod m =0 \\n \mod m' =0 \\n \mod m'' = 0 \end{cases} \tag 1$$ $$n=\text{LCM}\ (m,m',m'')$$ But this is just a particular case where all the equations equal $0$. I noticed that in this post: $$\begin{cases} n \mod m = 0 \\ n \mod m' = q \\ n \mod m'' = 0 \end{cases}$$ $$\text{if $m$, $(m' + q)$ and $m''$ don't have common divisors then} \ n=m \cdot (m' + q) \cdot m''$$ So is there a general formula or a method to solve equations that are different from $(1)$?

Community
  • 1
PunkZebra
  • 1,595
  • Note that $, {\rm mod}\ m'!:,\ m(m'!+q)m'' \equiv mqm'' \not\equiv q,$ in general, so that is not a correct solution. In general you have to resort to the Chinese Remainder Theorem or equivalent methods. – Bill Dubuque Jan 26 '15 at 18:39
  • Do you know about the chinese remainder theorem? – flawr Jan 26 '15 at 19:19

2 Answers2

1

Your suggested solution,
$\begin{align}n=m\cdot (m'+q) \cdot m''&= m\cdot m' \cdot m''+ m\cdot q \cdot m''\\&\equiv m\cdot q \cdot m'' \bmod m'\end{align}$

Looking at the second condition, if $m\cdot m'' \equiv 1 \bmod m'$, your solution will work for any $q$. Otherwise you need that $m\cdot m''\cdot q \equiv q \bmod m'$, which is possible for some additional cases. And it may not always give you the smallest solution.

So what we really need to do is find $r$ such that $ m\cdot r \cdot m'' \equiv q \bmod m'$. This means that we need the multiplicative inverse mod $m'$ of $m\cdot m''$, and then $r \equiv ((m\cdot m'')^{-1}\cdot q \bmod m'$ and $n=m\cdot(m'+r)\cdot m''$. Note however that the multiplicative inverse may not exist.

Joffan
  • 39,627
  • Does $m.m'' \equiv 1 \bmod m'$ mean $ m \cdot m'' \equiv 1 \bmod m'$? I don't understand – PunkZebra Jan 26 '15 at 19:41
  • Ok but how does this lead me to get the value of $n$? Also is there a demonstration for this? – PunkZebra Jan 26 '15 at 20:31
  • How did you get to $m\cdot (m'+q) \cdot m''\equiv m\cdot q \cdot m'' \bmod m'$ ? I showed that is true but how did you manage to write it? Also I'm sorry for all this questions but I'm kinda new to modular arithmetic. – PunkZebra Jan 28 '15 at 20:28
  • Where does $m\cdot m''\cdot q \equiv q \bmod m'$ come from and why do we need it? – PunkZebra Jan 29 '15 at 16:07
  • @Peterix We need it to fulfill the second condition. The left hand side is the calculation from the top line (as discussed) and the RHS is the second condition to be satisfied. Answer updated to clarify. – Joffan Jan 29 '15 at 16:31
1

$$n\equiv\left(+\begin{cases} m'm''\cdot 0\cdot ((m'm'')^{-1}\mod {m})\\ m\cdot m''\cdot q\cdot ((m\cdot m'')^{-1}\mod {m'})\\m\cdot m'\cdot 0\cdot ((m\cdot m')^{-1}\mod {m''})\end{cases}\right)\pmod {m\cdot m'\cdot m''}$$

$$\iff n\equiv m\cdot m''\cdot q\cdot ((m\cdot m'')^{-1}\mod {m'})\pmod {m\cdot m'\cdot m''}$$

Of course, this assumes that $m,m',m''$ are pairwise coprime, but this is not a problem if we use the following fact: $$n\equiv q\pmod {p_1^{\alpha_1}\cdots p_k^{\alpha_k}}\iff\begin{cases}n\equiv q\pmod {p_1^{\alpha_1}}\\\cdots\\n\equiv q\pmod {p_k^{\alpha_k}}\end{cases}$$

user26486
  • 11,331