Chinese Remainder Theorem (CRT) YouTube Lecture Handout

Get top class preparation for UGC right from your home: Get detailed illustrated notes covering entire syllabus: point-by-point for high retention.

Get video tutorial on: Examrace YouTube Channel

Loading video•••

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?