State the Chinese Remainder Theorem (Theorem 4.19).
Note 1: ETH::DiskMat
Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
eApiqwS~J~
Before
Front
Back
State the Chinese Remainder Theorem (Theorem 4.19).
Let \(m_1, m_2, \dots, m_r\) be pairwise relatively prime integers and let \(M = \prod_{i=1}^{r} m_i\). For every list \(a_1, \dots, a_r\) with \(0 \leq a_i < m_i\), the system
\[\begin{align} x &\equiv_{m_1} a_1 \\ x &\equiv_{m_2} a_2 \\ &\vdots \\ x &\equiv_{m_r} a_r \end{align}\]
has a unique solution \(x\) satisfying \(0 \leq x < M\).
Why unique:
If there are two solutions, then, for all \(i\):
\(x \equiv_{m_i} a_i\) and \(x' \equiv_{m_i} a_i\)
\(\implies m_i \mid( x - x_i)\)
\(\implies\)\(\sum_i m_i \mid (x-x_i)\) b/c \(m_i\) are coprime
\(\implies\)any two solutions differ by a multiple of \(M\)
Why unique:
If there are two solutions, then, for all \(i\):
\(x \equiv_{m_i} a_i\) and \(x' \equiv_{m_i} a_i\)
\(\implies m_i \mid( x - x_i)\)
\(\implies\)\(\sum_i m_i \mid (x-x_i)\) b/c \(m_i\) are coprime
\(\implies\)any two solutions differ by a multiple of \(M\)
After
Front
State the Chinese Remainder Theorem (Theorem 4.19).
Back
State the Chinese Remainder Theorem (Theorem 4.19).
Let \(m_1, m_2, \dots, m_r\) be pairwise relatively prime integers and let \(M = \prod_{i=1}^{r} m_i\). For every list \(a_1, \dots, a_r\) with \(0 \leq a_i < m_i\), the system
\[\begin{align} x &\equiv_{m_1} a_1 \\ x &\equiv_{m_2} a_2 \\ &\vdots \\ x &\equiv_{m_r} a_r \end{align}\]
has a unique solution \(x\) satisfying \(0 \leq x < M\).
Why unique:
If there are two solutions, then, for all \(i\):
\(x \equiv_{m_i} a_i\) and \(x' \equiv_{m_i} a_i\)
\(\implies m_i \mid (x - x')\) for all \(i\)
\(\implies M = \prod_{i=1}^{r} m_i \mid (x - x')\) since the \(m_i\) are pairwise coprime
\(\implies\) any two solutions differ by a multiple of \(M\) (so there is at most one solution with \(0 \le x < M\)).
Why unique:
If there are two solutions, then, for all \(i\):
\(x \equiv_{m_i} a_i\) and \(x' \equiv_{m_i} a_i\)
\(\implies m_i \mid (x - x')\) for all \(i\)
\(\implies M = \prod_{i=1}^{r} m_i \mid (x - x')\) since the \(m_i\) are pairwise coprime
\(\implies\) any two solutions differ by a multiple of \(M\) (so there is at most one solution with \(0 \le x < M\)).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Back | Let \(m_1, m_2, \dots, m_r\) be <b>pairwise relatively prime</b> integers and let \(M = \prod_{i=1}^{r} m_i\). For every list \(a_1, \dots, a_r\) with \(0 \leq a_i < m_i\), the system
\[\begin{align} x &\equiv_{m_1} a_1 \\ x &\equiv_{m_2} a_2 \\ &\vdots \\ x &\equiv_{m_r} a_r \end{align}\]
has a <b>unique solution</b> \(x\) satisfying \(0 \leq x < M\).<br><br><b>Why unique:</b> <br>If there are two solutions, then, for all \(i\):<br>\(x \equiv_{m_i} a_i\) and \(x' \equiv_{m_i} a_i\) <br>\(\implies m_i \mid |
Let \(m_1, m_2, \dots, m_r\) be <b>pairwise relatively prime</b> integers and let \(M = \prod_{i=1}^{r} m_i\). For every list \(a_1, \dots, a_r\) with \(0 \leq a_i < m_i\), the system \[\begin{align} x &\equiv_{m_1} a_1 \\ x &\equiv_{m_2} a_2 \\ &\vdots \\ x &\equiv_{m_r} a_r \end{align}\] has a <b>unique solution</b> \(x\) satisfying \(0 \leq x < M\).<br><br><b>Why unique:</b> <br>If there are two solutions, then, for all \(i\):<br>\(x \equiv_{m_i} a_i\) and \(x' \equiv_{m_i} a_i\) <br>\(\implies m_i \mid (x - x')\) for all \(i\)<br>\(\implies M = \prod_{i=1}^{r} m_i \mid (x - x')\) since the \(m_i\) are pairwise coprime<br>\(\implies\) any two solutions differ by a multiple of \(M\) (so there is at most one solution with \(0 \le x < M\)).<br> |