0
$\begingroup$

The number $2^{28} − 1$ has two factors between $120$ and $130$. The sum of these two numbers is.....

How do we solve this without using a calculator?

$\endgroup$
  • $\begingroup$ The difference of squares is often the key to class factoring problems. You should always be on the lookout for it. $\endgroup$ – Ross Millikan Jan 18 '17 at 18:51
10
$\begingroup$

The number $2^{28}-1$ is a difference of squares, so can be factored as $$2^{28}-1 = \left( 2^{14} - 1 \right) \left( 2^{14} + 1\right)$$ Now let's ignore the second factor for now. The first factor on the right-hand side is again a difference of squares, so this can be broken further down as $$2^{28}-1 = \left( 2^{7} - 1 \right) \left(2^7 + 1 \right) \left( 2^{14} + 1\right)$$ Notice that $2^7-1 = 127$ and $2^7+1 = 129$, so these are the two factors betwen $120$ and $130$ that we are interested in.

$\endgroup$
4
$\begingroup$

No, it hasn't. 227 is a prime.

$2^{28} - 1$ is an odd number, so that leaves 121, 123, 125, 127 and 129 as the only possible factors.

If we check the powers of 2 modulo 11, we get the following pattern: 2, 4, 8, 5, 10 (=-1), 9, 7, 3, 6, 1. So $2^{10} - 1$ is divisible by 11, as is $2^{20} - 1$, etc. But certainly not $2^{28} - 1$, so that number is not divisible by $11^2 = 121$.

For 123 = 41 * 3, we can check modulo 41, to get the following pattern: 2, 4, 8, 16, 32, 23, 5, 10, 20, 40 (=-1), 39, 37, 33, 25, 9, 18, 36, 31, 21, 1. So $2^{20} - 1$ is divisible by 41, but $2^{28} - 1$ isn't, and it's certainly not divisible by 123.

For 125, we check modulo 25: 2, 4, 8, 16, 7, 14, 3, 6, 12, 24(=-1), 23, 21, 17, 9, 18, 11, 22, 19, 13, 1. So $2^{20} - 1$ is divisible by 25, but but $2^{28} - 1$ isn't, and it's certainly not divisible by 125.

That leaves 127 and 129 as the only possible options, so the answer to your question is 127 + 129 = 256.

$\endgroup$
  • $\begingroup$ For more information on this number, please see Wikipedia $\endgroup$ – Simply Beautiful Art Jan 18 '17 at 18:22
  • $\begingroup$ @ChristianBlatter please check the initial version of the question. $\endgroup$ – Glorfindel Jan 18 '17 at 18:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.