Divisibility and Remainders

Transcript

0:00Introduction

Hello everyone! Okay, a small challenge to start. Seven to the power one hundred: if you write it out, it has eighty five digits. No calculator will show it fully. I want just one thing: the remainder when it is divided by eight. Can you find it in ten seconds? Sounds impossible, right? By the end of this video, you will do it in one line, with the binomial theorem. Remainder and divisibility questions come up often in JEE, so let's begin.

0:31The idea: write 7 as 8-1

So, here is the whole trick. Seven is just one less than eight. So seven to the power one hundred equals eight minus one, in brackets, to the power one hundred. Okay? Now expand it with the binomial theorem. Eight to the power one hundred, minus one hundred C one times eight to the power ninety nine, plus one hundred C two times eight to the power ninety eight, and so on, the three dots, down to minus one hundred C ninety nine times eight, and plus one. The small number up on the left of the capital C is n, and the one at the bottom right is r, so this is n C r. Now look carefully. Which of these terms are multiples of eight? Every term except the last one, yes, exactly! Each of them carries at least one factor of eight. So the whole thing is eight times some integer, plus the last term, which is minus one, to the power one hundred. Clear? And one hundred is even, so minus one to the power one hundred is just plus one. So the remainder is one! Eighty five digits, and we never computed a single one of them. Got it?

1:42Tools for remainders

Now let's make it general. Say we divide by m, with k an integer and N a positive integer. If the base is k times m, plus one, then every term of the expansion has a factor m, except the last. So k m plus one, to the power N, equals m times an integer, plus one. Remainder one, always. Okay? And if the base is k m minus one, only the last term changes. We get m times an integer, plus the last term, which is minus one, to the power N, clear? Now, suppose N is odd. Then the last term is minus one. So the remainder is minus one, right? No, no, careful! Remainders are never negative. So a remainder of minus c means the true remainder, m minus c: just add m once. Minus one becomes m minus one. Students forget this step all the time, so don't fall for it! With me? Now, sometimes the base itself is not next to a multiple of m. Then find a small power, a to the power k, that is a multiple of m, plus or minus one. On screen, the plus minus sign means plus one or minus one, and the sign with three lines, with mod m in brackets, is read: is congruent to, modulo m. Then divide the exponent N by k: N equals q k plus s, with quotient q and remainder s. Clear?

3:09Divisibility: (1+x)ⁿ-nx-1 and x²

Now the second kind of question: prove that something is divisible. Start with one plus x, to the power n, with n a positive integer. It equals one, plus n x, plus n C two x squared, plus n C three x cubed, and so on, up to x to the power n. Okay? Now look at the terms. Which of them have a factor of x squared? Every term from the third onwards, yes! And for integer x, what multiplies x squared is an integer too. So the expansion is one, plus n x, plus x squared times an integer. Right? Now move the first two terms across. One plus x, to the power n, minus n x, minus one, is x squared times an integer. So it is divisible by x squared. Remember the shape: a power, minus a term in n, minus a constant. When you see it, think of this tool. Got it?

4:07Example 1: remainder when 5^99 is divided by 13

Now, Example one. Find the remainder when five to the power ninety nine is divided by thirteen. Hint: look for a small power of five that sits next to a multiple of thirteen. Pause the video and try it. Done? Okay, let's check. Five itself is not next to a multiple of thirteen. So try a small power of five. Which one? Five squared, exactly! Twenty five is twenty six minus one, and twenty six is two times thirteen; the dot means times. So five squared is a multiple of thirteen, minus one. Perfect! Now the exponent. Ninety nine divided by two gives quotient forty nine and remainder one. So five to the power ninety nine is five, times five squared to the power forty nine. That is five times, twenty six minus one, to the power forty nine. With me? Forty nine is odd, so the last term of the expansion is minus one. Every other term is a multiple of twenty six, so a multiple of thirteen too. So twenty six minus one, to the power forty nine, is thirteen k minus one, with k an integer. Clear? Now multiply by five. Five times, thirteen k minus one, is sixty five k minus five. So the remainder is minus five? Or just five? Oh no, careful! Neither of them. Remainders are never negative, remember? Sixty five k is a multiple of thirteen, so add thirteen to minus five. Minus five plus thirteen is eight. So the remainder is eight. Got it?

5:48Example 2: prove 3^(2n+2) - 8n - 9 is divisible by 64

Now Example two, a harder one. Show that three to the power, two n plus two, minus eight n, minus nine, is divisible by sixty four, for every natural number n. On screen, the curved E sign means belongs to, and the double struck capital N is the set of natural numbers. Hint: look at the shape first. Pause the video and try it. Done? Okay, let's check. Look at the shape: a power, minus a term in n, minus a constant. Which tool does that remind you of? Yes, exactly, the x squared tool! But first we need one plus something. Three to the power, two n plus two, is three squared, to the power n plus one. That is nine to the power n plus one, which is one plus eight, to the power n plus one. Right? Now, the second term of this expansion. Is it just eight n? No, no, wait! The power is n plus one, not n. So the second term is eight times, n plus one. Then come n plus one C two times eight squared, n plus one C three times eight cubed, and so on. Clear? Now, every term from the third onwards has eight squared, that is sixty four, in it. And one, plus eight n plus eight, is eight n plus nine. So the whole thing is eight n, plus nine, plus sixty four k, for some integer k. With me? Move eight n and nine across. Three to the power, two n plus two, minus eight n, minus nine, equals sixty four k. Divisible by sixty four. Proved! Quick check with n equal to one. Three to the power four is eighty one, and eighty one minus eight minus nine is sixty four. Perfect!

7:43Quick revision: km ± 1, negative remainders, divisibility

So, quick revision. One: for a remainder, write the base, or a small power of it, as a multiple of m, plus or minus one, and expand. Two: if you get a negative remainder, minus c, the true remainder is m minus c. Three: one plus x, to the power n, minus n x, minus one, is divisible by x squared. Now go and try the practice problems on this page. Eighty five digits will never scare you again! All the best!