Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search