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

*print*Print*list*Cite

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=18*k* 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.