Thursday, 14 July 2016

elementary number theory - How do you solve x24equiv0mod21



There is an example in my textbook of how you solve:
x240mod21x240mod3×7
and then 2 congruences can be formed out of this equation if:
x240mod3x240mod7
and from these 2 congruences result 2 more congruences, for each:
x20mod3x1=2x+20mod3x2=1x20mod7x3=2x+20mod7x4=5



and then 4 systems of linear congruences are formed:

{x2mod3x2mod7
{x2mod3x5mod7
{x1mod3x2mod7
{x1mod3x5mod7



What is the purpose of these systems? I already have the 4 solutions (x1,x2,x3,x4) of the congruence. Why do I need to form these systems?


Answer



Your ‘4 solutions’ are not solutions modulo 21, but pairs of solutions mod on one hand, \bmod 7 on the other hand.



From these pairs of solutions, you recover solutions modulo 3\times 7 with the Chinese remainder theorem.




Start from the Bézout's relation \;5\cdot 3-2\cdot 7=1. Then the solution corresponding to the pair (\color{red}1\bmod3,\color{red}5\bmod7), for instance, will be
x\equiv\color{red}5\cdot5\cdot 3-\color{red}1\cdot2\cdot 7=61\equiv19\mod 21.


No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...