Divisibility ProofDate: 02/16/2001 at 11:57:31 From: Nikhil Promise Subject: Number Theory Prove that if n is an odd positive integer, then 2269^n + 1779^n + 1730^n - 1776^n is an integer multiple of 2001. Date: 02/16/2001 at 16:50:08 From: Doctor Rob Subject: Re: Number Theory Thanks for writing to Ask Dr. Math, Nikhil. Since 2001 = 3*23*29, you should show that N is divisible by each of these prime numbers. First the easy one, 3. 2269 = 1 (mod 3), 1779 = 0 (mod 3), 1730 = -1 (mod 3), and 1776 = 0 (mod 3), so: N = 1^n + 0^n + (-1)^n + 0^n (mod 3) = 1 - 1 (mod 3) = 0 (mod 3) because n is odd. Thus 3 | N. Now for 23. 2269 = -8 (mod 23), 1779 = 8 (mod 23), 1730 = 5 (mod 23), and 1776 = 5 (mod 23), so: N = (-8)^n + 8^n + 5^n - 5^n (mod 23) = -8^n + 8^n (mod 23) = 0 (mod 23) because n is odd. Thus 23 | N. Now for 29. 2269 = 7 (mod 29), 1779 = 10 (mod 29), 1730 = 19 (mod 29), and 1776 = 7 (mod 23), so: N = 7^n + 10^n + (-10)^n - 7^n (mod 29) = 10^n - 10^n (mod 29) = 0 (mod 29) because n is odd. Thus 29 | N. You do the rest. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/