# Chinese Remainder Theorem (CRT) YouTube Lecture Handout

Doorsteptutor material for UGC is prepared by world's top subject experts: Get detailed illustrated notes covering entire syllabus: point-by-point for high retention.

Download PDF of This Page (Size: 183K) ↧

Get video tutorial on: Examrace YouTube Channel

Watch Video Lecture on YouTube: Chinese Remainder Theorem (CRT) YouTube Lecture Handout

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*- 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