Divisibility

[[email protected]]

Hi,

I wanna understand if we can solve for divisibility by 3 the below mentioned number:


2^16-1, I was thinking to solve it by identifying the pattern i.e. 2^16 will have a 5 in the end and if we subtract 1 from it it will give us a 5.

There is smthing wrong I guess I am doing, pls help me understand!

Thanks

[[email protected]]

Hi shibsriz,

This calculation has a couple of pattern shortcuts to it. Here's one way to go about figuring out the pattern:

2^1 = 2 (ends in a 2)
2^2 = 4 (ends in a 4)
2^3 = 8 (ends in an 8)
2^4 = 16 (ends in a 6)

2^5 = 32 (ends in a 2)
2^6 = 64 (ends in a 4)
2^7 = 128 (ends in an 8)
2^8 = 256 (ends in a 6)

Notice the pattern? 2, 4, 8, 6......2, 4, 8, 6.....

This pattern will repeat every 4 terms.

2^16 is 16 terms (or four sets of 4 terms)

2^16 will end in a 6, so 2^16 - 1 will end in a 5

GMAT assassins aren't born, they're made,
Rich

[[email protected]]

Hi shibsriz,

This calculation is also based on an algebra pattern: the difference of squares...and some Number Properties....

2^16 - 1 = (2^8 + 1)(2^8 - 1)

(2^8 - 1) = (2^4 + 1)(2^4 -1)

(2^4 - 1) = (2^2 + 1)(2^2 - 1)

So....

2^16 -1 = (2^8 + 1)(2^4 + 1)(2^2 + 1)(2^2 - 1)

= (257)(17)(5)(3)

Since this is the product of 4 odd numbers (and one of them is a 5), the end result will be an odd multiple of 5.

GMAT assassins aren't born, they're made,
Rich