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

1. ## 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?

2. 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$.

3. Fermat's lil theorem gave me a multiple of 17 that satisfies the conditions but it's not the smallest multiple of 17.

4. 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}$.

5. 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.