Mg Problem 34

PRELIMINARY
a. Thm: For any finite set of congruencies of the form:
$x\equiv a_{1} \mod m_{1}$
$x\equiv a_{2} \mod m_{2}$

$x\equiv a_{n} \mod m_{n}$

where all $x,a_{i},m_{i}$ are integers and $m_{1},m_{2}, ... m_{n}$ are coprime, there exists a unique solution for x modulo the product $m_{1} \cdot m_{2} \cdot ... \cdot m_{n}$.

Pf: First, we must prove the theorem works for a set of two congruences satisfying all of the properties described. Consider a generic pair of congruencies of this form. By definition, $x\equiv a_{1} \mod m_{1}$ and $x\equiv a_{2} \mod m_{2}$ imply that $x=m_{1}b_{1}+a_{1}=m_{2}b_{2}+a_{2}$. From this result, we may simplify to get $m_{1}b_{1}-m_{2}b_{2} = a_{2}-a_{1}$. Since $m_{1},m_{2}$ are coprime, there exists a unique linear combination of the two equaling 1. And since $a_{2} - a_{1}$ is an integer and therefore a multiple of 1, we know there exist unique solutions for $b_{1}$ and $b_{2}$. Now, having solved for $b_{1},b_{2}$, we can derive some $x$ that fits congruencies 1 and 2. Since all $m_{i}$ are coprime, this solution will be equivalent to any solution in the coset of $m_{1}m_{2}$.

Next, since we have proven the theorem for two congruencies, we can prove it for any finite number, as the two-congruence process can be repeated sequentially through all the remaining congruences, since the numbers all remain integers and all $m_{i}$ remain coprime, as the product of two integers coprime with a third remains coprime with that third integer.

b. Bandit solution

c. Generic solution: In this case, we would need to prove that there is a bijective homomorphism between the two quotient rings

FINALS:

a. Prove that for any finite set of congruences of the form

$x\equiv a_{1} \mod m_{1}$
$x\equiv a_{2} \mod m_{2}$

$x\equiv a_{n} \mod m_{n}$

where all $a_i, m_i, x \in \mathbb{Z}$ and $GCD(m_{1}, m_{2}, ... , m_{n}) = 1$, there exists a unique solution for $x$, modulo the product $m_{1} \cdot m_{2} \cdot ... \cdot m_{n}$.

Pf: We may consider a single pair of congruences, generically $x\equiv a_{1} \mod m_{1}$ and $x\equiv a_{2} \mod m_{2}$. From these facts, we may determine that $x=b_{1}m_{1}+a_{1} = b_{2}m_{2}+a_{2}$. From this, we may derive $b_{1}m_{1} - b_{2}m_{2} = a_{2} - a_{1}$. Since $a_{1},a_{2} \in \mathbb{Z}$, $a_2 - a_1 = c\cdot 1$ for some integer $c$. Since $m_1, m_2$ are relatively prime, there exists some linear combination equal to 1, and therefore, the linear combination $b_{1}m_{1} - b_{2}m_{2} = c \cdot 1$ also exists, as it is in proportion to the linear combination equal to 1. Therefore, we can be certain that some $x$ exists satisfying both congruences.

Next, we must show that this solution is unique modulo $m_{1}m_{2}$. Let $a'$ be a generic solution satisfying both congruences. This implies that $a' \in \underline{a_1}_{m_1}$ and $a' \in \underline{a_2}_{m_2}$, that is $a'$ is contained within the coset of $a_1$ in quotient ring $\mathbb{Z}/m_{1}\mathbb{Z}$ and the coset of $a_2$ in quotient ring $\mathbb{Z}/m_{2}\mathbb{Z}$. Since all members of a coset are equivalent modulo the ideal dividing the quotient ring, all $x$ satisfy $x \in a' + m_{1}\mathbb{Z}$ and $x \in a' + m_{2}\mathbb{Z}$. The intersection of these two sets is all integers equal to $a'$ plus a multiple of of both $m_1$ and $m_2$. Since $GCD(m_{1},m_{2}) = 1$, the only integers that are multiples of both $m_1$ and $m_2$ are the multiples of their product. Therefore, the set of all satisfactory solutions in precisely defined by $a' + m_{1}m_{2}\mathbb{Z}$. Equivalently, $x \equiv a' \mod m_{1}m_{2}$.

Since we have proven that $x\equiv a_{1} \mod m_{1}$ and $x\equiv a_{2} \mod m_{2}$ yield a unique result modulo $m_{1}\cdot m_{2}$, and the greatest common divisor of all $m_i$ is 1 by definition, we may simply repeat the process with the new congruence $x \equiv a' \mod m_{1}m_{2}$ and the next congruence from the original set. This may be repeated all the way through to the final congruence.

QED

b. Bandit problem. Boils down to solve for $x$ modulo $17\cdot 16 \cdot 11 \cdot 7$ for $x$ satisfying the following congruences:

1. $x \equiv 3 \mod 17$
2. $x \equiv 10 \mod 16$
3. $x \equiv 4 \mod 11$
4. $x \equiv 0 \mod 7$

First, let's solve for 1 and 4. We'll do this by finding the intersection of the sets defined by 7n and 17m + 3 up to the product of 7 and 17, or 119. These sets are: $\{0,7,14,21,28,35,42,49,56,63,70,77,84,91,98,105,112\}$ and $\{3,20,37,54,71,88,105\}$. The common element is 105. Therefore, we have $x \equiv 105 \mod 119$. Let us simplify some of our calculations by using the equivalent $x \equiv -14 \mod 119$.

Now, let's perform the same for 2 and 3. The sets we must compare are those generated by 16n + 10 and 11m + 4, up to the product 16x11=176. Here are those sets: $\{10,26,42,58,74,90,106,122,138,154,170\}$ and $\{4,15,26,37,48,59,70,81,92,103,114,125,136,147,158,169\}$. This solution is 26, giving us the equivalence $x \equiv 26 \mod 176$.

Finally, let's compare in the same manner the two new congruences. We will use the sets generated by 119n - 14 and 176m + 26, up to the product 119x176 = 20944. For the sake of space, that solution is 2842.

Therefore, all possible x satisfy $x \equiv 2842 \mod 20944$. The least number of coins the bandits could have stolen is 2842.

c. Prove the more generic statement that for $R$, a commutative ring with identity, and $I,J$, two coprime ideals of $R$ such that $I+J = R$, $R/IJ \cong R/I \times R/J$.

To prove this theorem, we may start by defining a map $\phi: R/IJ \rightarrow R/I \times R/J$ by $\phi(a) = (a+I,a+J)$. This map can be proven to be a homomorphism:
Multiplication: $\phi(ab) = (ab+I, ab+J)$. $\phi(a)\phi(b) = (a+I,a+J)\cdot(b+I,b+J)$. Multiply pairwise modulo $I$ and $J$ respectively. $(a+I,a+J)\cdot(b+I,b+J) = (ab+I, ab+J)$
Addition: $\phi(a+b) = (a+b+I, a+b+J)$. $\phi(a) + \phi(b) = (a+I,a+J)+(b+I,b+J)$. Add pairwise: $(a+I,a+J)+(b+I,b+J) = (a+b+I,a+b+J)$.

Suffice it to show that the homomorphic map $\phi$ is bijective. This can be done by proving injectivity in both directions. For $R/IJ \rightarrow R/I \times R/J$, since we know that $I$ and $J$ are coprime, we know that elements of $R$ that are equivalent under $R/I$ and $R/J$ must also be equivalent under $R/IJ$ and therefore are the same element of $R/IJ$. Thus, every element of $R/IJ$ has a unique image. For the reverse direction, we may see simply that $(x+I,y+J) \rightarrow (xy + IJ)$, a unique image.

QED

page revision: 20, last edited: 25 Apr 2018 22:41