number theory
posted by john on .
Find the least positive integer that leaves the remainder 3 when divided by 7, remainder 4 when divided by 9, and remainder 8 when divided by 11

Hint: Chinese Remainder Theorem

You can try the CRT (Chinese remainder theorem).
Master sun proceeded as follows:
Given
N≡3 mod 7
N≡4 mod 9
N≡8 mod 11
We need to find the smallest positive N.
First we find the unit remainders,
99≡1 mod 7 (99 is product of 9*11_
154≡1 mod 9 (154 is multiple of 7*11)
441≡1 mod 11 (441 is multiple of 7*9)
N mod(7*9*11) is the required number such that
N=3*99+4*154+8*441 mod 693
=4441 mod 693
=283
Check:
283≡3 mod 7
283≡4 mod 9
283≡8 mod 11 Yeah!