Home > Just Math
Divisible? Yes and No. (Posted on 20110815) 

Prove that 3^105+4^105 is divisible by 13*49*181*379 but is not divisible by either 5 or 11.
Solution

Comment 3 of 3 

If a and b are odd integers with ab = 105, and if 3^{a} + 4^{a} = 0 (mod m), then:
3^{a} =  4^{a} = (4)^{a} (mod m). Therefore: 3^{ab} = (4)^{ab} =  4^{ab}
giving : 3^{105} + 4^{105} = 0 (mod m). So 3^{105} + 4^{105} is divisible by m.
Using this result in each case:
3^{3} + 4^{3} = 27 + 64 = 91 = 0 (mod 13), so 13 divides 3^{105} + 4^{105}
3^{7} + 4^{7} = 2187 + 16384 = 18571 = 0 (mod 49) so 49 divides 3^{105} + 4^{105}
3^{5} + 4^{5} = 243 + 1024 = 1267 = 0 (mod 181) so 181 divides 3^{105} + 4^{105}
3^{7} + 4^{7} = 2187 + 16384 = 18571 = 0 (mod 379) so 379 divides 3^{105} + 4^{105}
It follows that 3^{105} + 4^{105} is divisible by 13*49*181*379, since 13, 49, 181
and 379 have no common factors,
Now on a different tack: 3^{105} = (3)(3^{4})^{26} = 3*81^{26} = 3*1^{26} = 3 (mod 5)
and: 4^{105} = (4)(4^{2})^{52} = 4*16^{52} = 4*1^{52} = 4 (mod 5)
So 3^{105} + 4^{105} = 2 (mod 5) and therefore is not divisible by 5.
Also: 3^{105} = (3^{5})^{21} = 243^{21} = 1^{21} = 1 (mod 11)
and: 4^{105} = (4^{5})^{21} = 1024^{21} = 1^{21} = 1 (mod 11)
So 3^{105} + 4^{105} = 2 (mod 11) and therefore is not divisible by 11.

Posted by Harry
on 20110816 23:11:17 


Please log in:
Forums (0)
Newest Problems
Random Problem
FAQ 
About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
