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.

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

share|improve this question

closed as not a real question by Will Jagy, Andres Caicedo, Martin Sleziak, MJD, J. M. Nov 8 '12 at 6:17

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Please specify what type of congruences you refer to. –  Bill Dubuque Nov 5 '12 at 23:09
    
It 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? –  Gerry Myerson Nov 5 '12 at 23:09
    
My 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. –  Anthony Nov 5 '12 at 23:11
    
x≡4(mod5) x≡5(mod7) x≡3(mod8) x≡6(mod9) x≡1(mod19) –  Anthony Nov 5 '12 at 23:11
2  
The 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. –  Gerry Myerson Nov 5 '12 at 23:35
show 2 more comments

2 Answers 2

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.

share|improve this answer
add comment

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}$$

share|improve this answer
add comment

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