How to Recreate CRT

Mathematics

Congruent Numbers

Given $a \in N$,and $p$ be a prime,we have a family numbers $x$ s.t $x \equiv a\pmod{p}$
Let $n$ be a integer where $gcd(n,p)==1$,$n$ has inverse modulus $p$
$n*a*n^{-1} \equiv a\pmod{p}$
So $x = n*a*n^{-1}$ where $gcd(n,p)==1$

Two Congruence Equations

Given two equations,$p$ and $q$ are distinct primes:
$x \equiv a\pmod{p}$
$x \equiv b\pmod{q}$

Solution 1:
We need find a $x$ which satisfies $x=a+kp=b+rq$,so we can find this particular $x$ by finding $k$ and $r$
$\therefore kp-rq=a-b$

Since $gcd(p,q)==1$,by XGCD,we can solve $k\prime p-r\prime q=1$

$\therefore k=(a-b)k\prime ,r=(a-b)r\prime$

Then we can substitute back to find $x$.

Solution 2:
Since $p,q$ relatively primes.
$p$ has inverse modulus $q$,let say $p^{-1}$,and $q$ has inverse modulus $p$,let say $q^{-1}$
That is,we can find a $x=qaq^{-1}+pbp^{-1}$
$x \equiv a+0\pmod{p}$
$x \equiv b+0\pmod{q}$
So,$x=qaq^{-1}+pbp^{-1}$ is the solution

$x$ is unique up to mod $pq$

Task one
Let $y$ be another solution of the equations above.
we have:
$y \equiv x\pmod{p}$
$y \equiv x\pmod{q}$

So $p|y-x, q|y-x$
Since $q,p$ are primes,$y-x$ must be divided by $pq$
$\rightarrow y=x+kqp$
$\rightarrow y \equiv x\pmod{pq}$

In conclusion,$x$ is unique up to $pq$

Task two
We've proved that:$y \equiv x\pmod{pq}$
$\rightarrow y-k_1pq==x-k_2qp$
$\rightarrow x==y+(k_2-k_1)pq$

$x \equiv a\pmod{p} \rightarrow y+(k_2-k_1)pq \equiv a\pmod{p}$
$\rightarrow y \equiv a\pmod{p}$
Similarly,$y \equiv b\pmod{q}$

Gerneralization

Given $n$ equations,and $n$ distinct positive integers $m_i$,and for all $i \not= j$,$gcd(m_i,m_j)==1$.
Solve the following equations:
$x \equiv a_1\pmod{m_1}$
$x \equiv a_2\pmod{m_2}$
...
$x \equiv a_n\pmod{m_n}$

Solution:
let $M_i=\prod\limits_{i \not=j}m_j$
$x=\sum\limits_{i=1}^nM_i{M}_i^{-1}a_i$

Exercises

Question:$2000^{2019} \mod 221(221=13*17)$

Answer:
$2000^{2019} \equiv 11^{2019}\pmod{13}$
$2000^{2019} \equiv 11^{2019}\pmod{17}$

From Euler's theorem,we have:
$11^{2019} \equiv 11^3\ \equiv 5\pmod{13}$
$11^{2019} \equiv 11^3\ \equiv 5\pmod{17}$

$\therefore 2000^{2019} \equiv 5*17*10+5*13*4\pmod{221}$
$\therefore 2000^{2019} \mod 221 ==5$

Programming

Here

Little Thought

If
$x \equiv a\pmod{p}$
$x \equiv a\pmod{q}$
where $p,q$ are distinct primes and $a>0$
then $x=(a \mod pq)$

Reason:
$\because$$x \equiv a\pmod{p}$
$x \equiv a\pmod{q}$
So $a$ is one of the solutions
From CRT,we know that the solution of these equations is unique up to $pq$

$\therefore x\equiv a\pmod{pq}$

Bigger Than Little Thought

Question:
Let $p,q,r$ be distinct primes

If
$x \equiv a\pmod{p}$
$x \equiv a\pmod{q}$
$x \equiv 0\pmod{r}$
and $a$ is a multiple of $r$,
then what is $x \mod pqr$? why?

Answer:
Since $r |a$:
$x \equiv 0\ \equiv a\pmod{r}$
So $a$ is one of the solutions
From CRT,we know that the solution of these equations is unique up to $pq$

$\therefore x \equiv a\pmod{pqr}$