Chinese Remainder Theorem (CRT) YouTube Lecture Handout
Get top class preparation for competitive exams right from your home: get questions, notes, tests, video lectures and more- for all subjects of your exam.
Get video tutorial on: Examrace YouTube Channel
Chinese Remainder Theorem (CRT) YouTube Lecture Handout
Recap
- 4 Types of HCF Remainder Problems
- 4 Types of LCM Remainder Problems
- Smallest Number When Divided by x, y and z Leaves Remainder a, b, c?
- x - a = y - b = z - c = common difference d
- Smallest number divided by 2, 3,4, 5,6 leaves remainder 1, 2,3, 4,5
- Find the smallest number which when divided by 2,3 and 5 produces 1,2, 3 as remainders
- Note that 2,3 and 5 are (pairwise) relatively co-prime
- Find the smallest number which when divided by 7,9 and 11 produces 1,2, 3 as remainders
Simplifying CRT
Key to Reducing Complicated Calculations- Not Using Full CRT at All! !
- Find the smallest number which when divided by 2,3 and 5 produces 1,2, 2 as remainders
- Find the smallest number which when divided by 2,3 and 5 produces 1,2, 3 as remainders
- Find the smallest number which when divided by 7,9 and 11 produces 1,2, 3 as remainders
One Small Concept
- Constant Case: Smallest number when divided by x, y and z leaves remainder a, b, c
- x - a = y - b = z - c = common difference d
- LCM (a, b, c) – d
- Convert to Constant Case: Smallest number when divided by x, y and z leaves remainder a, b, c, where
- x - ma = y - mb = z - mc = common difference d
- Use all combining
- 24 produces a remainder 4 when divided by 5
- Find the smallest number which when divided by 7,9 and 11 produces 1,2, 3 as remainders
- 7 – 1 = 5 7 – 2 × 1 = 5
- 9 – 2 = 7 9 – 2 × 2 = 5
- 11 – 3 = 8 11 – 2 × 3 = 5
CRT is Last Resort! !
- Constant Case: Smallest number when divided by x, y and z leaves remainder a, b, c
- x - a = y - b = z - c = common difference d
- LCM (a, b, c) – d
- Convert to Constant Case: Smallest number when divided by x, y and z leaves remainder a, b, c, where
- x - ma = y - mb = z - mc = common difference d
- Use all combining
Next Class- Word Problems on Chinese Remainder Theorem
6 professors begin courses of lectures on Monday, Tuesday, Wednesday, Thursday, Friday and Saturday, and announce their intentions of lecturing at intervals of 2, 3, 4,1, 6,5 days respectively. The regulations of the University forbid Sunday lectures. When first will all six professors simultaneously find themselves compelled to omit a lecture?
✍ Mayank