Show that (103)^53+(53)^103 is divisible by 39

Asked by  | 25th Dec, 2008, 08:24: AM

Expert Answer:

We need to prove that it's divisible by 3 and by 13.
For 3, we note that if you divide 53 by 3 you get 17 with a remainder of 2 and 103 divided by 3 gives you 34 with a remainder of 1.

So 53^103 = (17x3+2) ^103

Now expand the terms,

= (17x3)^103 + A(17x3)^102 x (2)+ B(17x3)^101 x(2)^2 +……
where A and B are constant coefficients.

Here all the terms are divisible by 3 (since there's a factor of 3 in all of them) except for the last one, which gives us 2^103. That's the only term that might not be divisible by 3. Let's find out what the remainder would be:
2=2
2x2=4=(3x1)+1 = 1
2x2x2=8=3x2+2 = 2
2x2x2x2=16=5x3+1
So it looks like every time we multiply by 2, the remainder flips between 1 and 2. If there are an odd number of 2s, then the remainder is 2. If there's an even number, then it's 1, so that tells us that 2^103=kx3+2.
so 53^103=3k+2 for some number k.
Similarly:
103^53=(3x34+1)^53
Remainder=1^53=1
So 103^53=3t+1 and 53^103=3s+2, so
103^53+53^103=3t+1+3s+2
= 3(t+s+1), which tells us it is divisible by 3.

Exactly the same way for 13:
53^103=  (4x13+1)^103 so remainder=1
103^53=(7x13+12)^53 so Remainder =12
1^103=1
12^53=...oh, that's a little tougher.
12=12 Remainder =12
12x12=144 Remainder =1
12x12x12=1728 Remainder =12, so it flops between remainder of 12 and remainder of 1
So Remainder (12^53)=12
So 53^103=13k+1 and 103^53=13m+12
53^103 + 103^53
=13m+12 +13k+1
=13(m+k+1) so their sum is divisible by 13.
Since it's divisible by 3 and 13, so it is divisible by 39.

 

Answered by  | 2nd Jan, 2009, 02:28: PM

Queries asked on Sunday & after 7pm from Monday to Saturday will be answered after 12pm the next working day.