Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/