Divisibility Proof

Date: 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/