How would I determine if there is at least 1 integer that can satisfy 5 congruences all at once? Would I prove it individually? For example A->B->C->D->E->A
How would I determine if there is at least 1 integer that can satisfy 5 congruences all at once?
-
0Please specify what type of congruences you refer to. – 2012-11-05
-
0It would depend on the congruences. You might be asking about a situation where the Chinese Remainder Theorem applies --- why not look that up, and see whether it's what you want? – 2012-11-05
-
0My thought was that the Chinese Remainder Theorem would apply but I am not sure how to apply it to 5 congruences at once, I have only seen examples dealing with 2 congruences. – 2012-11-05
-
0x≡4(mod5) x≡5(mod7) x≡3(mod8) x≡6(mod9) x≡1(mod19) – 2012-11-05
-
0If my understanding of the Chinese remainder theorem is correct it should be something like this for the example above, x≡a(mod47880) but I'm not sure where I would come up with the a – 2012-11-05
-
2The Chinese Remainder Theorem says that if the moduli are relatively prime (as they are in the example you give) then there is an integer satisfying all the congruences simultaneously, and what's more, it is unique, modulo the product of the moduli. A fuller version of the theorem says what to do if the moduli are not relatively prime. You can prove the many-congruence case by induction, starting with the 2-congruence case. – 2012-11-05
-
0@Anthony: You may want to rewrite your question, explaining what you want in it. The example $(x\equiv 4 \bmod5) \land (x \equiv 5 \bmod 7) \dots$ would do well in the problem statement above. – 2012-11-05
-
0It must be added that the congruences you wish to solve are _linear_. – 2014-08-26
2 Answers
Let's start with two congruences.
TWO CONGRUENCES
For example, let's say we have $$x \equiv 4 \bmod 5$$ $$x \equiv 5 \bmod 7$$
What does the first congruence tell us? A number $x$ is congruent to $(4 \bmod 5)$ if $x = 5k + 4$ for some integer $k$.
Now, what does the second congruence tell us? It tells us that $x$ is congrunet to $(5 \bmod 7)$ if $x = 7j + 5$ for some integer $j$.
Now, let us start with the second congruence:
$x = 7j + 5$. Try $j=0$ to start. Then $x = 7j + 5$ implies $x=5$. Now check to see if it fits into the first congruence. Does $x$, being equal to five, leave a remainder of 4 after being divided by 5? No.
So try $j=1$. Then $x=7j+5$ implies $x = 12$. Does this leave a remainder of 4 after being divided by 5? No.
So try $j=2$. Then $x=19$. Does this leave a remainder of 4 after division by 5? Yes, because $19 = (3 \cdot 5) + 4$
You can check this number for the first two congruences.
THREE CONGRUENCES
The first two congruences were modulo 5 and modulo 7. To combine these congruences, we want a number modulo $5 \cdot 7 = 35$, just like you suggest in the comments. In fact, we already know that 19 satisfies the first two congruences. So, we want a number congruent to $19 \bmod 35$.
In fact, the new congruence that we have just discovered can now be combined with one of the original congruences.
The next one on the list is $3 \bmod 8$. So we first check if 19 is equivalent to $3 \bmod 8$. $19 = (2\cdot 8) + 3$. It is! So this new congruence is satisfied. Once again, we update the new modulos to be $(37 \cdot 8) = 296$. So we now know our number is congruent to $19 \bmod 296$.
Can you do the rest? Remember, for the next number, you will add $(296\cdot \text{(the next modulus)})$ if needed to 19 until it satisfies another congruence.
In the same way that one can compute $\rm\:k$-ary products by composing binary product operations
$$\rm\: m_{\,1} * m_{\,2} * m_{\,3} * \cdots * m_{\,k}\ =\ (\cdots ((m_{\,1} * m_{\,2}) * m_{\,3}) * \cdots ) * m_{\,k}$$
one can solve $\rm\:k\:$ congruences $\rm\:x\equiv a_i\pmod{m_{\,i}}\:$ by composing solutions of two congruences. Indeed, above let $\rm\:m_{\,i} * m_{\,j}\:$ denote the CRT solution $\rm\: x\ mod\ m_{\,i} m_{\,j},\:$ composed from $\rm\:x\ mod\ m_{\,i}\:$ and $\rm\:x\ mod\ m_{\,j}.\:$ Then we can successively compute the entire product as bracketed above, since CRT applies at every step, since $\rm\:m_{\,1} m_{\,2} \cdots m_{\,j}\:$ is coprime to $\rm\:m_{\,j+1}$ by Euclid's Lemma, because $\rm\:m_{\,j}\:$ is coprime to every $\rm\:m_{\,k}\:$ with $\rm\:k\ne j,\:$ by hypothesis.
If you know some ring theory then you may view this more structurally as follows
$$\rm \Bbb Z/(m_{\,1}\,\cdots\,m_{\,k})\ \cong\ (\cdots((\Bbb Z/m_{\,1} \times \Bbb Z/m_{\,2}) \times \Bbb Z/m_{\,3})\times\,\cdots )\times \Bbb Z/m_{\,k}$$