SEARCH HOME
 Math Central Quandaries & Queries
 Question from Sahand: You are given number x that is very large (that large that it can't be divided by hand) can we find out that x is divisible by 2^n or not?

Hi,

Let's start with some small numbers. Suppose $x = 57236$ and $n=1.$ You can write $x = 57230 + 6 = 5723 \times 10 + 6.$ But 10 is divisible by 2 and 6 is divisible by 2 and hence $x = 57230 + 6 = 5723 \times 10 + 6$ is divisible by 2. But what if $x = 57235$ then $x = 5723 \times 10 + 5$ and since 5 is not divisible by 2, 57235 is not divisible by 2. Thus it looks like a positive integer is divisible by 2 if and only if its units digit is divisible by 2. Let's try to prove that.

Suppose that $x$ is a positive integer then there is a one digit integer $u$ so that $x = y \times 10 + u$ for some integer $y.$ But 10 is divisible by 2 so $x = y \times 10 + u$ is divisible by 2 if and only if $u$ is divisible by 2.

Now suppose that $n = 2$ and you want to see if $x$ is divisible by $2^n = 2^2 = {4}.$ There is a two digit integer $z$ so that $x = y \times 100 + z = y\times 10^2 + z$ for some integer $y.$ But $10^2$ is divisible by $2^2$ and hence $x$ is divisible by $2^2$ if and only if $z$ is divisible by $2^{2}.$

Can you complete your problem now?
Penny

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.