Q.465. Remainder in a large division.

Question 465.
What is the remainder if 5^2009 + 13^2009 is divided by 18 ?

Answer 465.
Using,
For an odd positive integer n,
x^n + y^n
= (x + y) [x^(n-1) - x^(n-2)y + x^(n-2)y^2 - ... + y^(n-1)]

5^2009 + 13^2009
= (5 + 13) [5^2008 - 5^2007 * 13 + 5^2006 * 13^2 - ... + 13^2008]
= 18 * [5^2008 - 5^2007 * 13 + 5^2006 * 13^2 - ... + 13^2008]
=> 5^2009 + 13^2009 is divisible by 18 with zero remainder.

Link to YA!