Bunuel wrote:
Every digit of a number written in binary is either 0 or 1. To translate a number from binary, multiply the nth digit (reading from right to left) by 2^(n-1)
What is the largest prime number (written in binary) that is a factor of both 100010000 and 1000100000 ?
(A) 10
(B) 11
(C) 101
(D) 1011
(E) 10001
Kudos for a correct solution.
MANHATTAN GMAT OFFICIAL SOLUTION:To begin this problem, translate the numbers written in binary.
\(100010000 = 1*2^8 + 0*2^7 + 0*2^6 + 0*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 0*2^0\)
This simplifies to \(2^8 + 2^4\).
Similarly, 1000100000 simplifies to \(2^9 + 2^5\).
We could then translate these further.
\(2^8 + 2^4 = 256 + 16 = 272\)
\(2^9 + 2^5 = 512 + 32 = 544\)
We need to find the greatest common factor of both of these numbers. At this point, we could do a prime factorization of both numbers. They are large, however, and this process could be tedious. It will actually be easier to find common factors of these numbers from their previous forms.
When an expression like 2^8 + 2^4 appears on the GMAT, it is usually helpful to factor out the largest common factor of both terms of the expression. In this case, factor out 2^4.
\(2^8 + 2^4\) → \(2^4(2^4+1)\) → \(2^4(16+1)\) → \(2^4(17)\)
From this we can see that 272 has only two prime factors: 2 and 17.
Now do the same for 544.
\(2^9 + 2^5\) → \(2^5(2^4 + 1)\) → \(2^5(16 + 1)\) → \(2^5(17)\)
544 has the same two prime factors: 2 and 17. So the greatest common prime factor of the two numbers is 17. Now we need to translate 17 back into binary. Notice from the manipulations above that
\(17 = 2^4 + 1, or 2^4 + 2^0\)
Thus, 17 written in binary is 10001.
The correct answer is E.Thanks for the explanation Bunuel. But do we really need to go through this process. I just looked at the two numbers in the question. The second number ( 1000100000) is the first number (100010000) multiplied by 10. Then I took a look at E which is the highest value given among the questions. I just realized that you would need to multiply that by 10 several times to divide both the first number and the second number so I chose E. I didn't bother with the binary calculations. Is my reasoning flawed?