|
1. Chinese Remainder Theorem example
( Enter your problem )
|
|
|
3. Example-3 : 2x=5 (mod 7),3x=4 (mod 8)
1. Chinese Remainder Theorem to solve `2x=5 (mod 7),3x=4 (mod 8)`
Solution:
Method-2: Successive substitution method
`2x-=5\ ("mod "7)->(1)`
`3x-=4\ ("mod "8)->(2)`
from (1)
`2x-=5\ ("mod "7)`
Here `2^(-1)-=4\ ("mod "7)`
`:. 4xx2x-=4xx5\ ("mod "7)`
`:. 8x-=20\ ("mod "7)`
`:. x-=6\ ("mod "7)`
Hence `x=6+7a`
Now from (2), `3x-=4\ ("mod "8)`
`:. 3(6+7a)-=4\ ("mod "8)`
`:. 18+21a-=4\ ("mod "8)`
`:. 2+5a-=4\ ("mod "8)`
`:. 5a-=2\ ("mod "8)`
Here `5^(-1)-=5\ ("mod "8)`
`:. 5xx5a-=5xx2\ ("mod "8)`
`:. 25a-=10\ ("mod "8)`
`:. a-=2\ ("mod "8)`
Hence `a=2+8b`
But `x=6+7a`
`:.x=6+7(2+8b)`
`:.x=6+14+56b`
`:.x=20+56b`
`:.x-=20\ ("mod "56)`
2. Chinese Remainder Theorem to solve `2x=6 (mod 14),3x=9 (mod 15),5x=20 (mod 60)`
Solution:
Method-2: Successive substitution method
`2x-=6\ ("mod "14)`
divide by 2, we get
`x-=3\ ("mod "7)->(1)`
`3x-=9\ ("mod "15)`
divide by 3, we get
`x-=3\ ("mod "5)->(2)`
`5x-=20\ ("mod "60)`
divide by 5, we get
`x-=4\ ("mod "12)->(3)`
from (1)
`x-=3\ ("mod "7)`
Hence `x=3+7a`
Now from (2), `x-=3\ ("mod "5)`
`:. (3+7a)-=3\ ("mod "5)`
`:. 3+2a-=3\ ("mod "5)`
`:. 2a-=0\ ("mod "5)`
Here `2^(-1)-=3\ ("mod "5)`
`:. 3xx2a-=3xx0\ ("mod "5)`
`:. 6a-=0\ ("mod "5)`
`:. a-=0\ ("mod "5)`
Hence `a=0+5b`
But `x=3+7a`
`:.x=3+7(0+5b)`
`:.x=3+0+35b`
`:.x=3+35b`
Now from (3), `x-=4\ ("mod "12)`
`:. (3+35b)-=4\ ("mod "12)`
`:. 3+11b-=4\ ("mod "12)`
`:. 11b-=1\ ("mod "12)`
Here `11^(-1)-=11\ ("mod "12)`
`:. 11xx11b-=11xx1\ ("mod "12)`
`:. 121b-=11\ ("mod "12)`
`:. b-=11\ ("mod "12)`
Hence `b=11+12c`
But `x=3+35b`
`:.x=3+35(11+12c)`
`:.x=3+385+420c`
`:.x=388+420c`
`:.x-=388\ ("mod "420)`
3. Chinese Remainder Theorem to solve `x=1 (mod 4),x=0 (mod 6)`
Solution:
`x-=1\ ("mod "4)->(1)`
`x-=0\ ("mod "6)->(2)`
`a_1=1,a_2=0`
`n_1=4,n_2=6`
Check if each `n_i` is pairwise coprime
`GCD(4,6)=2`
Here gcd is not 1, so the given equations has no solution.
Method-2: Successive substitution method
`x-=1\ ("mod "4)->(1)`
`x-=0\ ("mod "6)->(2)`
from (1)
`x-=1\ ("mod "4)`
Hence `x=1+4a`
Now from (2), `x-=0\ ("mod "6)`
`:. (1+4a)-=0\ ("mod "6)`
`:. 4a-=-1\ ("mod "6)`
`:. 4a-=5\ ("mod "6)`
Here, `gcd(4,6)=2` and 2 does not divide 5
So this is impossible
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
|
|
