Proving DivisibilityDate: 04/30/2002 at 06:02:08 From: Emily Wong Subject: Proving divisibility Dear Dr Maths, Prove that 1^99 + 2^99 + 3^99 + 4^99 + 5^99 is divisible by 15. I'm, not sure how to start the problem. Thank you very much for your help. Yours sincerely, Emily Wong Date: 05/02/2002 at 11:51:15 From: Doctor Douglas Subject: Re: Proving divisibility Hi, Emily, Thanks for submitting your question to the Math Forum. This is a very interesting problem in number divisibility! Let's call the number N: N = 1^99 + 2^99 + 3^99 + 4^99 + 5^99 If you could show that N is divisible by 3 AND that N is also divisible by 5, then it would be divisible by 15. Can you finish off the problem with this hint? You probably already know techniques for determining whether or not a number is divisible by 3 and by 5. You may have to break the number N into parts (i.e. 1^99, 2^99, etc., and test whether each individual part is divisible by three and/or five). Write back if you get stuck! - Doctor Douglas, The Math Forum http://mathforum.org/dr.math/ Date: 05/03/2002 at 04:55:35 From: Emily Wong Subject: Proving divisibility Dear Dr Douglas, Thank you very much for your reply. I am still quite stuck. I'm not sure how to prove that, for example 2^99 is divisible by 3 and/or 5 because 2^99 is such a large number. Thank you very much. Yours sincerely, Emily Wong Date: 05/03/2002 at 12:31:25 From: Doctor Douglas Subject: Re: Proving divisibility Hi, again, Emily. For divisibility by three, what will matter is the total digit sum of the number N. So we need to know what the remainder is (upon dividing by three) of ALL of the individual parts: 1^99, 2^99, 3^99, 4^99, and 5^99. The sum N may be divisible by three even if the individual parts are not. Let's consider 2^99: 2^1 = 2 has remainder 2 when divided by 3 2^2 = 2 x 2^1 = 2 x (3k+2) 3k+2 has remainder 2, k is some integer = 6k + 2x2 = 6k + 4 = (6k + 3) + 1 2^2 has remainder 1 when divided by 3 2^3 = 2 x 2^2 = 2 x (3k+1) here k is a different integer = 6k + 2 2^3 has remainder 2 when divided by 3 2^4 = 2 x 2^3 = 2 x (3k+2) = 6k + 4 = (6k+3) + 1 2^4 has remainder 1 when divided by 3 and so on. I think you can see the pattern. We know from this reasoning that 2^99 will have remainder 2 when divided by 3, even though we don't know all of the actual digits in 2^99. And it's okay that 2^99 divided by 3 isn't an integer, because we don't know yet what will happen with the other terms in N. If you carry out similar analyses for 1^99, 3^99, 4^99, and 5^99, you'll be able to see what the various remainders will be upon dividing by 3, and whether or not the *sum* of the remainders is a multiple of three - if it is, then N is divisible by 3. Of course 1^99 is easy - its remainder is 1, and 3^99 is obviously divisible by 3 (remainder = 0). Now the analysis for divisibility-by-five is a little easier, since we only need the final digit in each part. If the five final digits from the five terms add up to something that ends in 5 or ends in zero, then N will be divisible by 5. 2^1 = 2 ends in 2 2^2 = 4 ends in 4 2^3 = 8 ends in 8 2^4 = 16 ends in 6 2^5 = 32 ends in 2 2^6 = 64 ends in 4 2^7 = 128 ends in 8 2^8 = 256 ends in 6 2^9 = 512 ends in 2 Do you see how this pattern continues? Every factor of 2^4 doesn't change the digit: 2^(k+4) mod 10 = 2^(k) mod 10 for any positive integer k where "mod 10" means take the remainder upon dividing by 10. So the final digit in 2^99 is 2^99 mod 10 = (2^4 * 2^95) mod 10 = 2^95 mod 10 using the pattern we found = (2^4 * 2^91) mod 10 = 2^91 mod 10 = 2^87 mod 10 = ... = = 2^3 mod 10 = 8 so the final digit in 2^99 is 8. You'll have to apply similar analyses to 3^99 to find its final digit. But at least 1^99 and 4^99 and 5^99 are relatively easy. Once you have the five final digits, you can add them up to see whether or not their *sum* ends in 5 or 0 and hence, divisible by 5. And that will imply that N is divisible by 5. By combining these two facts (N is divisible by both 5 and 3), you'll be able to show that N is divisible by 15. - Doctor Douglas, The Math Forum http://mathforum.org/dr.math/ Date: 05/04/2002 at 02:29:09 From: Emily Wong Subject: Proving divisibility Dear Dr Douglas, Thank you very much for your help. I am very grateful. Yours sincerely, Emily Wong |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/