Results 1 to 5 of 5

Math Help - Numbers that are comprised of all 1's in binary expansion

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    8

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2010
    Posts
    8
    Fermat's lil theorem gave me a multiple of 17 that satisfies the conditions but it's not the smallest multiple of 17.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    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}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by squelchy451 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binary Representation of Real Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 8th 2011, 12:47 AM
  2. Replies: 3
    Last Post: November 22nd 2010, 07:39 AM
  3. convert single numbers to 5 bit binary
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 28th 2010, 06:18 PM
  4. finite and infinite binary expansion of 3/16
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 5th 2010, 10:25 AM
  5. Binary numbers
    Posted in the Math Software Forum
    Replies: 0
    Last Post: August 8th 2008, 04:57 PM

Search Tags


/mathhelpforum @mathhelpforum