Chinese Remainder Theorem (CRT) YouTube Lecture Handout

Get unlimited access to the best preparation resource for IAS : Get detailed illustrated notes covering entire syllabus: point-by-point for high retention.

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?

Developed by: