# Numbers that are comprised of all 1's in binary expansion

• July 3rd 2010, 09:01 PM
squelchy451
Numbers that are comprised of all 1's in binary expansion
I have to find a number that is made of 1's only (i.e. 111, 1111, 1111111, not 1010, 11101, 1101010, etc) that is a multiple of 17. I have to find the smallest number that meets this requirement

The forumula 2^(n+1) - 1 = 17p was set up to solve this problem since the numbers
1, 3, 7, 15, 31 put into binary expansion are all made of 1. If you didnt notice, the term n is created by multiplying the previous term by 2 and adding 1.

I found the answer using a java program and n = 7 and p = 15. Any mathematical way to solve it?
• July 3rd 2010, 09:21 PM
roninpro
You could use Fermat's Little Theorem. For any prime $p$ and $a$ not divisible by $p$, we have $a^{p-1}\equiv 1\pmod{p}$. This shows $2^{17-1}\equiv 2^{16}\equiv 1\pmod{17}$, or $2^{16}-1\equiv 0\pmod{17}$.

You can now make choices for $n$ and (your) $p$.
• July 3rd 2010, 10:09 PM
squelchy451
Fermat's lil theorem gave me a multiple of 17 that satisfies the conditions but it's not the smallest multiple of 17.
• July 3rd 2010, 10:15 PM
roninpro
Ah, I didn't see that condition.

In any case, if you want the smallest, you look at the divisors of 16: 1, 2, 4, 8, 16 and check if 2 raised to each divisor gives 1. The divisors 1, 2, 4 don't work. But, $2^8\equiv 1\pmod{17}$.
• July 3rd 2010, 10:30 PM
melese
Quote:

Originally Posted by squelchy451
I have to find a number that is made of 1's only (i.e. 111, 1111, 1111111, not 1010, 11101, 1101010, etc) that is a multiple of 17. I have to find the smallest number that meets this requirement

The forumula 2^(n+1) - 1 = 17p was set up to solve this problem since the numbers
1, 3, 7, 15, 31 put into binary expansion are all made of 1. If you didnt notice, the term n is created by multiplying the previous term by 2 and adding 1.

I found the answer using a java program and n = 7 and p = 15. Any mathematical way to solve it?

Maybe this will help? Notice that $2^4\equiv-1(mod\ 17)$, then $2^8=(2^4)^2\equiv(-1)^2=1(mod\ 17)$.

But I'm not sure whether it's a real explanation.