FIND THE REMAINDER WHEN 5^2009 + 13^2009 IS DIVIDED BY 18 ?? PLZ ANYONE EXPLN IN DETAIL WITH SIMPLE METHODS....

Find the remainder if 5^2009 + 13^2009 is divided by
18.

The answer is zero. Note that for any odd power z,
(5^z+13^z)/18 has remainder zero (do the first few by hand) while even powers have
reaminders that cycle 14,8,2,14,...

To prove this we use
induction:

(1) Base case: 5^1+13^1 = 18 and 18 divides
18.

(2) Induction step: Assume that for some
n , (5^(2n+1)+13^(2n+1))/18 has remainder
zero.

(3) Show that for such an n,
(5^(2n+3)+13^(2n+3))/18 also has remainder zero.

Let
a=5^(2n+1) and b=13^(2n+1). Then 5^(2n+3)=25a and 13^(2n+3)=169b. Thus
5^(2n+3)+13^(2n+3)=25a+169b.

But by the inductive
hypothesis, 18 divides a+b or a+b=18k for some
k in the integers. If a+b=18k, then
b=18k-a.

So, 25a+169b=25a+169(18k-a)
=25a
+169(18k) - 169a
=-144a +
169(18k)
=18(-8a)+18(169k)
=18(-8a+169k)

Thus
18 divides 25a+169b, or 18 divides 25(5^(2n+1))+169(13^(2n+1)). Therefore, 18 divides
5^(2n+3)+13^(2n+3).

Since this works for n=0, by induction
it works for n=1,2,...

Therefore, by induction, 18 divides
the given sum, and the remainder is zero.