# Chinese Remainder Theorem (CRT) YouTube Lecture Handout

Doorsteptutor material for ACET is prepared by world's top subject experts: get questions, notes, tests, video lectures and more- for all subjects of ACET.

Get video tutorial on: Examrace YouTube Channel

## 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*- m*a*=*y*- m*b*=*z*- m*c*= 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*- m*a*=*y*- m*b*=*z*- m*c*= 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