Find Remainders: 3^2002/26, 5^2002/26

Date: 09/21/2002 at 22:10:23
From: Mr. Hugehy
Subject: Powers

(a)
Find the remainder obtained when 3^2002 is divided by 26
(b)
Find the remainder obtained when 5^2002 is divided by 26
(c)
Show that 3^2002 + 5^2002 is divisible by 26

Kids have asked me these questions and I can't answer them.

Date: 09/22/2002 at 00:25:17
From: Doctor Greenie
Subject: Re: Powers

Hi, Mr. Hugehy -

Here is a link to a page in the Dr. Math archives where there is some 
information on how you can go about answering these questions:

   2^99 Divided by 99
   http://mathforum.org/library/drmath/view/55599.html 

If you use the technique described on that page, you will find that 
the remainders when 3^n is divided by 26 for n=1 to n=10 are the 
following:

  3, 9, 1, 3, 9, 1, 3, 9, 1, 3

As you can see, the remainders when 3^n is divided by 26 repeat for 
every 3rd power. Since the remainders of 3^n divided by 26 repeat 
every 3rd power, and since 2002/3 = 667 remainder 1, the remainder 
when 3^2002 is divided by 26 is the same as the remainder when 3^1 is 
divided by 26.

So the answer to your first question is:

  the remainder when 3^2002 is divided by 26 is 3

And the remainders when 5^n is divided by 26 for n=1 to n=10 are the 
following:

  5, 25, 21, 1, 5, 25, 21, 1, 5, 25

Here, you can see that the remainders when 5^n is divided by 26 repeat 
for every 4th power. Since the remainders of 5^n divided by 26 repeat 
every 4th power, and since 2002/4 = 500 remainder 2, the remainder 
when 5^2002 is divided by 26 is the same as the remainder when 5^2 is 
divided by 26.

So the answer to your second question is:

  the remainder when 5^2002 is divided by 26 is 25

Once we have the answers to your first two questions, showing the 
third should be easy.  If the sum

  3^2002 + 5^2002

is to be divisible by 26, then the remainder when that sum is 
divisible by 26 should be 0; this means the sum of the remainders 
when 3^2002 and 5^2002 are divisible by 26 should be 0, or a multiple 
of 26. However, we have found that the remainders when 3^2002 and 
5^2002 are divided by 26 are 3 and 25; and 3+25=28 is not a multiple 
of 26.

The problem here is that I think you have misquoted the problem.  I 
have seen this same problem here at Dr. Math several times previously 
in the last few months and every other time I have seen this problem, 
the last part was to show that

  3^2002 + 29*5^2002

is divisible by 26.

Since the remainders when 3^2002 and 5^2002 are divided by 26 are 3 
and 25, respectively, then the remainder when

  3^2002 + 29*5^2002

is divided by 26 is

  3 + 29(25) = 3 + 725 = 728 = 28(26)

This remainder is a multiple of 26, and so the number

  3^2002 + 29*5^2002

is divisible by 26.

I hope all this helps.  Write back if you have any further questions 
about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/