Using Modular Arithmetic to Test Divisibility of Large NumbersDate: 08/30/2008 at 06:32:55 From: Judy Subject: Divisibility of big numbers Prove that 55^62 - 2*13^62 + 41^62 is divisible by 182. I don't know how to go about it at all. I have no idea where to start. Date: 08/30/2008 at 13:46:43 From: Doctor Greenie Subject: Re: Divisibility of big numbers Hi, Judy - Problems like this are usually solved using modular arithmetic. In modular arithmetic, we are only concerned with the remainder when a number is divided by another. The key to working with modular arithmetic is that, because we are only interested in remainders, we only need to use the remainders (instead of the actual numbers) in our calculations. For example, if I want to know the remainder when 3^175 is divided by 7, I can do the following: 3/7 = 0 remainder 3 (3^2)/7 = (3*3)/7 = 9/7 = 1 remainder 2 (3^3)/7 = (3*2)/7 = 6/7 = 0 remainder 6 In that last calculation, I didn't multiply 3^2=9 by 3, because I am only interested in remainders. Instead, I multiplied 2 by 3, because 2 is the remainder when 3^2=9 is divided by 7. (3^4)/7 = (3*6)/7 = 18/7 = 2 remainder 4 (3^5)/7 = (3*4)/7 = 12/7 = 1 remainder 5 (3^6)/7 = (3*5)/7 = 15/7 = 2 remainder 1 Now, because our remainder is 1 at this point, when we multiply by 3 again, the pattern of remainders will start repeating. So the remainders we get when dividing successive powers of 3 by 7 is 3, 2, 6, 4, 5, 1 The pattern repeats every 6 powers. The power in our problem is 175; 175/6 = 29 remainder 1. That means the remainder when 3^175 is divided by 7 is the same as the remainder when 3^1 is divided by 7; and that remainder is 3. So the remainder when 3^175 is divided by 7 is 3. How do we use modular arithmetic on your problem? First we note that the prime factorization of the divisor, 182, is 182 = 2*7*13 If the given number is divisible by 182, then it must be divisible by 2, by 7, and by 13. We can see that the number is divisible by 2 without using modular arithmetic. 55^62 is odd; 2*(13^62) is even; and 41^62 is odd. The expression is then (odd - even + odd), which is even; so the expression is divisible by 2. (In fact, we are using modular arithmetic--specifically, arithmetic "mod 2"--when we talk about even and odd numbers. But we don't need to use the formal modular arithmetic methods, because it is easy to work with "odd" and "even" numbers.) To finish showing that the expression is divisible by 182, we can use modular arithmetic to show that the expression is divisible by both 7 and 13. The work is more complicated for 13 than for 7; so I'll show you the details for 13 and let you try to fill in the details to show the expression is divisible by 7. So I need to show that 55^62 - 2*13^62 + 41^62 is divisible by 13. The middle term has multiple factors of 13, so it is clearly divisible by 13, so I only need to show that 55^62 + 41^62 is divisible by 13. To do this, I look at the remainders when successive powers of 55 and 41 are divided by 13. Note that the remainder when 55 itself is divided by 13 is 3, and the remainder when 41 itself is divided by 13 is 2--so in fact I am going to look for the patterns of remainders when 3 to successive powers and 2 to successive powers are divided by 13. Using the process demonstrated above, I find... 3^1/13 --> remainder 3 3^2/13 = 3*3/13 --> remainder 9 3^3/13 = 3*9/13 --> remainder 1 AHA! I already have a remainder of 1; the pattern of remainders repeats every 3 powers. The power I want is 62; 62/3 leaves remainder 2; so the remainder when 55^62 is divided by 13 is the same as the remainder when 3^2 is divided by 13--which is 9. And... 2^1/13 --> remainder 2 2^2/13 = 2*2/13 --> remainder 4 2^3/13 = 2*4/13 --> remainder 8 2^4/13 = 2*8/13 --> remainder 3 2^5/13 = 2*3/13 --> remainder 6 2^6/13 = 2*6/13 --> remainder 12 At this point I can use a "trick" of modular arithmetic. The remainder at this point when divided by 13 is 12; in modular arithmetic I can think of this remainder as -1. In other words, the remainder is 1 less than the divisor. For example, I can think of 19/5 as having remainder 4 (19 = 3*5 + 4) or as having remainder -1 (19 = 4*5 + (-1)). Since 2^6 leaves remainder -1, I know that (2^6)^2 = 2^12 is going to leave remainder (-1)^2 = 1. So the pattern of remainders when successive powers of 2 are divided by 13 repeats every 12 powers. Again, the power in my problem is 62; 62/12 = 5 remainder 2; so the remainder when 41^62 is divided by 13 is the same as the remainder when 2^2 is divided by 13--which is 4. So now the remainders when the three parts of the given expression are divided by 13 are 9, 0, and 4; the sum of those remainders is 13; and 13 is divisible by 13. So the entire expression is divisible by 13. Now see if you can use the same type of process to show that the expression is also divisible by 7.... I hope this helps. Please write back if you have any further questions about any of this. - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/