Powered Modulo

When we need to calculate the modulus (or remainder) of a nth powered number, we have to find out out the pattern. 

#Problem 12.1
if a^2+b^2 is a multiple of 7^2009 then prove that ab is a multiple of 7^2010.[USA Math Talent Search]
 Solution scheme and approach
a^2+b^2=7^2009*k 
As right hand side is divisible by 7 left hand should be divisible by 7.
Now we can deduce the the following table 
Number-----Square-------remainder (modulo 7)
0-------------0-------------0
1-------------1-------------1
2-------------4-------------4
3-------------9-------------2
4------------16-------------2
5------------25-------------4
6------------36-------------1
From the table it's clear that as sum of two numbers (>=1) gives 7 so both of them should be divisible by 7.
Let a=7a1,b=7b1. 
=>a^2+b^2=7^2009*k
a1^2+b1^2=7^2007*k
Likewise, let a1=7a2 and b1=7b2
a2^2+b2^2=7^2005*k
=>a=7^2*a1 and b=7^2*b1
and so on ...................
at last we get 
a1004^2 + b1004^2=7k
=>a=7^1005*a1 and b=7^1005*b1
=>ab=7^2010*(a1b1)
=>ab is a multiple of 7^2010. Q.E.D.

#Problem 12.2

A set consists of 143 natural numbers each of them is a perfect cube. If they are divided by 13, how many maximum numbers within the set are possible, such that one will get the same reminder in each case.

(a)11, (b)31, (c)33, (d)36, (e)29 [AIMCAT]

Solution scheme and approach 
When any cube(0^3,1^3,2^3,...,12^3) divides by 13 it generates 5 different numbers 0,1,5,8,12. Now at least [143/5]+1=29 numbers are possible which will generate same remainder.
Hence, option (e) is the answer