0
$\begingroup$

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

  • 0
    It must be added that the congruences you wish to solve are _linear_.2014-08-26

2 Answers 2

3

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.

0

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