How to do the Chinese Remainder Theorem
Author:
Ernest Michael Nelson
Last Updated:
7 years ago
License:
Creative Commons CC BY 4.0
Abstract:
Math
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\documentclass[article]{article}
\begin{document}
%%%%%%%%%%%%%%% title %%%%%%%%%%%%%%%%%%%%%
\title{How to do the Chinese Remainder Theorem}
\author{Ernest Michael Nelson}
\date{\today}
\maketitle
%%%%%%%%%%%%%%%%%% End of title %%%%%%%%%%%
\section{Introduction}
In this article we will be doing a step by step on how to do the Chinese Reminder Theorem. An we will be given a system of three congruences.
\section{System of Congruenhces}
$$x_{1} \equiv (3 \makebox{mod}\ 8)$$
$$x_{2} \equiv(1 \makebox{mod}\ 9)$$
$$x_{3} \equiv(4 \makebox{mod}\ 11)$$
\section{Formulas}
The given formula is\\
$$\bar{x}\equiv a_{1}\cdot N_{1} \cdot x_{1}+a_{2}\cdot N_{2}\cdot x_{2}+a{3}\cdot N_{3}\cdot x_{3}(\makebox{mod}\ n_{1}\cdot n_{2} \cdot n_{3})$$
and we will also need the inverse formula
$$N_{1}x_{k}\equiv a_{1}(\makebox{mod}\ n_{k})$$
\section{Proof:}
The very first thing we want to calculate is our modules in the Chinese Remainder Theorem (CRT). An by observation we are also given $a_{1}$ from the given system of congruences.
$$\bar{x}\equiv 3\cdot N_{1}\cdot x_{1}+1\cdot N_{2}\cdot x{2}+4\cdot N_{3}\cdot x_{3}(\makebox{mod}\ 8\cdot9\cdot11)$$
$$\bar{x}\equiv 3\cdot N_{1}\cdot x_{1}+1\cdot N_{2}\cdot x_{2}+4\cdot N_{3}\cdot x_{3}(\makebox{mod}\ 792)$$
Next we will calculate the $N_{1}$,$N_{2}$ and $N_{3}$ of the (CRT).Fri st we will calculate $N_{1}$ and then repeat the process for $N_{2}$ and $N_{3}$.
$$N_{1}=\frac{8\cdot9\cdot11}{8}=99$$
$$N_{2}=\frac{8\cdot9\cdot11}{9}=88$$
$$N_{3}=\frac{8\cdot9\cdot11}{11}=72$$
Now we input $N_{1}$,$N_{2}$, and $N_{3}$ into the given formula.\
$$\bar{x}\equiv 3\cdot99\cdot x_{1}+1\cdot88 \cdot x_{2}+4\cdot72\cdot x_{3}(\makebox{mod}\ 792)$$
Then we simplify the formula.
$$\bar{x}\equiv 297\cdot x_{1}+88\cdot x_{2}+288\cdot x_{3}(\makebox{mod}\ 792)$$
On the next step we will calculate the $x_{1}$,$x_{2}$, and $x_{3}$ in the (CRT).First we will show how to solve $x_{1}$ then $x_{2}$ and $x_{3}$.
\section{Solving for $x_{1}$,$x_{2}$ and $x_{3}$}
From the formula section above we plug $N_{1}$ into our congruences.\
\ For $x_{1}$\
$$99x_{1}\equiv 1( \makebox{mod}\ 8)$$
Next step we dived 8 into 99 and remainder we put in front of $x_{1}$.
$$3x_{1}\equiv 1( \makebox{mod}\ 8)$$
Now we add 8 to our congruences.
$$3x_{1}\equiv 9( \makebox{mod}\ 8)$$
Final we dived 3 into 9 and get our answer for $x_{1}$.
$$x_{1}\equiv3( \makebox{mod}\ 8)$$
Therefore $x_{1}=3$.\
\ For $x_{2}$\
$$88x_{2}\equiv 1( \makebox{mod}\ 9)$$
We repeat the process for $x_{2}$ as the same for $x_{1}$ so we dived 9 into 88.
$$7x_{2}\equiv 1( \makebox{mod}\ 9)$$
Then we add 9 to the congruences.
$$7x_{2}\equiv 10( \makebox{mod}\ 9)$$
The next step we subtract 9 on the left hand side.
$$-2x_{2}\equiv 10( \makebox{mod}\ 9)$$
To make the congruence correct we make $x_{2}=-5$.
$$2(-5)\equiv 10( \makebox{mod}\ 9)$$
Therefor $x_{2}=-5$\
\ For $x_{3}$
$$72x_{3}\equiv 1( \makebox{mod}\ 11)$$
First we dived 72 by 11 and put the remainder in front of $x_{3}$.
$$6x_{3}\equiv 1( \makebox{mod}\ 11)$$
Now we add 11 to the congruence.
$$6x_{3}\equiv 12( \makebox{mod}\ 11)$$
Final we dived 6 on both sides.
$$x_{3}\equiv 2( \makebox{mod}\ 11)$$
Therefore $x_{3}=2$\
\ After getting $x_{1}$,$x_{2}$,and $x_{3}$ we input into our (CRT) formula and calculate.
$$\bar{x}\equiv ((297\cdot 3+ 88\cdot (-5) +288\cdot 2) \makebox{mod}\ 792)$$
$$\bar{x}\equiv ((891+(-440)+ 576 )\makebox{mod}\ 792)$$
$$\bar{x}\equiv 1027 (\makebox{mod}\ 792)$$
Lastly we reduce by subtracting 792 from 1027.
$$\bar{x}\equiv 235 (\makebox{mod}\ 792)$$
$$(q.e.d)$$
\section{Reference:}
\ Bruce M.Burton, Element of Number Theory, page 79
Joseph Cutrona,YouTube.com, Basic example of Chinese Remainder Theorem\
\end{document}