Tuesday, June 13, 2017

Chinese Remainder Theorem


I saw this example and i think i have understood how Chinese Remainder Theorem Works. First lets take three numbers which are relative prime $2,3$ and $5$. Lets try to find a number which gives the remainder $1,2$ and $3$ when divided by those 3 relative primes we chose. Lets write the original number are $x = 15x_1+10x_2+6x_3$ now the nice thing about this $x$ is when we divide by $\frac{x}{2} = \frac{15x_1}{2}=1$ and the smallest value which satisfies this equation is when $x_1 = 1$, Similarly $\frac{x}{3}=\frac{10x_2}{3}\Rightarrow x_2=2$ and $\frac{x}{5}=\frac{6x_3}{5} \Rightarrow x_3 =3$. Thus our number $x = 15x_1+10x_2+6x_3 = 15(1)+10(2)+6(3)=53$. Is this correct ? well this does satisfy the original condition of the remainders, however this is not the smallest number. If we multiply the original numbers we get $2*3*5=30$, now this divisible by all $2,3$ and $5$. So if we subtract the multiples of this number from any number the remainders will not change and hence we can obtain a smaller number which is $53-30=23$

Labels: , , ,

Site Meter