Video 4: Divisibility Results Based on the Binomial Theorem by MIT OpenCourseWare

Summary by www.lecturesummary.com: Video 4: Divisibility Results Based on the Binomial Theorem by MIT OpenCourseWare

• Overview

  • Welcome and topic: Binomial Theorem-based results on divisibility.

    Content Breakdown

    • 0:05 - Review of the Binomial Theorem formula: x + y to the power of n is equivalent to the summation of nCr * x^(n-r) * y^r from r=0 to n.
    • 0:15 - Problem: Prove that, for natural numbers n, 3^(2n+2) - 8n - 9 is divisible by 64.
    • 0:40 - Method: To generate a binomial expansion, re-express the term.
    • 0:50 - 3^(2n+2) is rewritten as 9^(n+1).
    • 1:00 - To apply the binomial expansion, rewrite 9 as 1 + 8.
    • 1:15 - Applying the binomial theorem to expand (1 + 8)^(n+1).
    • 1:55 - The expansion's first two terms are simplified.
    • 2:00 - The subtracted terms cancel out the first two terms, which add up to 8n + 9.
    • 2:25 - The summation is rewritten with a change of indices, beginning at r=0.
    • 2:35 - The sum is factored out to get 8^2, or 64.
    • 2:45 - The expression changes to 64 * (summation of (n+1)C(r+2) * 8^r from r=0 to n-1).
    • 2:50 - The remaining summation is an integer.
    • 3:00 - Conclusion: The total term is divisible by 64.

    Example 2

    • 3:20 - Problem: Prove that, for any natural number n, 2^(4n) - 2^n * (7n + 1) is divisible by 196.
    • 3:35 - Noting that 196 is 14 squared.
    • 3:45 - 2^(4n) is rewritten as 16^n.
    • 3:55 - Divides 16 by 2 + 14.
    • 4:10 - Applying the binomial theorem to expand (2 + 14)^n.
    • 4:40 - Terms are rewritten and simplified, and 14 is factored as 2 * 7.
    • 5:00 - The subtracted term 2^n * (7n + 1) is expanded.
    • 5:10 - Termination cancellation occurs.
    • 5:20 - The sum of nCr * 2^(n-r) * 14^r from r=2 to n is the remaining term.
    • 5:30 - Rewrite the summation and factor out 14^2, or 196.
    • 5:40 - The sum is multiplied by the square of 14, yielding 196.
    • Conclusion: The term is divisible by 196 at 5:45.

    Remainder Problem/Multiple Choice Question

    • 5:50 - Issue: Determine the remainder of the division of 5^99 by 13.
    • 6:10 - Discussing how hard it is to rule out options.
    • 6:30 - Method: To find one near a multiple of 13, compute powers of 5.
    • 6:40 - 5^1 equals 5, 5^2 equals 25.
    • 6:50 - 5^99 is rewritten as 5 * 5^98.
    • 7:00 - Using 26-1 in place of 5^2.
    • 7:10 - Applying the binomial theorem to expand (26 - 1)^49.
    • 7:30 - Every term in the expansion will be divisible by 13.
    • 7:40 - The first term of the expansion multiplied by the leading 5 yields the remainder.
    • 7:50 - The expansion's first term evaluates to -1.
    • 8:10 - 5 * (-1) = -5.
    • 8:20 - The balance is 5.
    • 8:30 - Adding a multiple of 13 to make it positive.
    • -5 + 13 = 8 is the positive remainder at -8:40.

    • -8:40. This method is comparable to modular arithmetic.

      • Ignored multiples of 13
      • Used remainder arguments

      The lecture ends at 9:10.