perplexus.info :: Just Math : Divisible? Yes and No.

Home > Just Math

Divisible? Yes and No. (Posted on 2011-08-15)

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

No Solution Yet Submitted by Ady TZIDON

No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)

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¹⁰⁵ + 4¹⁰⁵ = 0    (mod m).    So 3¹⁰⁵ + 4¹⁰⁵ is divisible by m.

Using this result in each case:

3³ + 4³ = 27 + 64 = 91 = 0 (mod 13),     so 13 divides 3¹⁰⁵ + 4¹⁰⁵

3⁷ + 4⁷ = 2187 + 16384 = 18571 = 0 (mod 49) so 49 divides 3¹⁰⁵ + 4¹⁰⁵

3⁵ + 4⁵ = 243 + 1024 = 1267 = 0 (mod 181) so 181 divides 3¹⁰⁵ + 4¹⁰⁵

3⁷ + 4⁷ = 2187 + 16384 = 18571 = 0 (mod 379) so 379 divides 3¹⁰⁵ + 4¹⁰⁵

It follows that 3¹⁰⁵ + 4¹⁰⁵ is divisible by 13*49*181*379, since 13, 49, 181

and 379 have no common factors,

Now on a different tack: 3¹⁰⁵ = (3)(3⁴)²⁶ = 3*81²⁶ = 3*1²⁶ = 3 (mod 5)

and:                              4¹⁰⁵ = (4)(4²)⁵² = 4*16⁵² = 4*1⁵² = 4 (mod 5)

So 3¹⁰⁵ + 4¹⁰⁵ = 2 (mod 5) and therefore is not divisible by 5.

Also:                             3¹⁰⁵ = (3⁵)²¹ = 243²¹ = 1²¹ = 1 (mod 11)

and:                              4¹⁰⁵ = (4⁵)²¹ = 1024²¹ = 1²¹ = 1 (mod 11)

So 3¹⁰⁵ + 4¹⁰⁵ = 2 (mod 11) and therefore is not divisible by 11.

Posted by Harry on 2011-08-16 23:11:17

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (16)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info