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?
0
$\begingroup$
modular-arithmetic
-
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