# Divisibility Rules

• Jan 28th 2007, 07:50 PM
Ideasman
Divisibility Rules
How do I determine what the highest power of 2 is that divides 89,275,744?
• Jan 28th 2007, 09:04 PM
CaptainBlack
Quote:

Originally Posted by Ideasman
How do I determine what the highest power of 2 is that divides 89,275,744?

Well its less than \$\displaystyle \log_2(89275744) \approx 18.3\$, so repeated division untill you get a odd answer is a viable option. I make it 5.

RonL
• Jan 29th 2007, 07:02 AM
ThePerfectHacker
Quote:

Originally Posted by Ideasman
How do I determine what the highest power of 2 is that divides 89,275,744?

The theorem says, and follow the pattern....

N is divisible by 2 if and only if the last digit is even.

N is divisible by 4=2^2 if and only if the last two digits are divisible by 4.

N is divisible by 8=2^3 if and only if the last three digits are divisible by 8.

And thus on.....

Thus, given 89,275,744

1)We see it is divisible by 2 because 2 divides 2.

2)We see it is divisible by 2^2 because 4 divides 44.

3)We see it is divisible by 2^3 because 8 divides 744.

And so on....
Find the point where it stops being divisible and you have an answer.
• Jan 29th 2007, 10:20 AM
Soroban
Hello, Ideasman

Quote:

How do I determine what the highest power of 2 is that divides 89,275,744?

Convert \$\displaystyle 89,275,744\$ to binary and we get:

. . \$\displaystyle 101,010,100,100,011,110,101,100,000_2\$
. . . . . . . . . . . . . . . . . . . - - - \$\displaystyle \uparrow\$
. . . and it is obvious that \$\displaystyle \overbrace{100000_2 = 32}\$ is the greatest divisor.

Just kidding!