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