Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fun Divisibility Problem

  1. Jun 27, 2007 #1
    Show that for any n>1 we can construct a positive integer consisting of only 1's and 0's such that this integer is a multiple of n.
     
  2. jcsd
  3. Jun 27, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Interesting variation: show that if n is no divisbible by 2 or 5, then there you can choose this multiple to have precisely two 1s and the rest of the digits 0.
     
  4. Jun 27, 2007 #3

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Can you show example answers for, say, n=3 or n=9?

    I do wonder how interesting a 'minimal' condition would make this though.
     
  5. Jun 27, 2007 #4
    A Big Hint

    Given (n+1) integers show that there exists two whose difference is a divisible by n.
     
  6. Jun 28, 2007 #5

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    The problem is fairily easy...

    [tex]k=\sum_{i=1}^{n} 10^{i\phi(n)}[/tex]
    where [itex]\phi(n)[/itex] is the Euler Totient function.

    Is divisible by [itex]n[/itex].

    Alternatively, if we take [itex]n^2-n+1[/itex] integers then at least [itex]n[/itex] of them must have the same residue mod [itex]n[/itex], so their sum is equal to zero mod [itex]n[/itex], so if we take the first [itex]n^2-n+1[/itex] powers of 10, some sum will be equal to zero mod n, and that sum will clearly be zeros and ones.
     
  7. Jun 28, 2007 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    My special case was: if 10 and n are coprime, let r be the order of 10 in the units mod n, then 10^r-1 is divisble by n.
     
  8. Jun 28, 2007 #7

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    But that's all 9's. Of course, this leads to a marginally more challenging version:

    Show that every number has a (non-trivial) multiple which is some number of ones, followed by some number of zeros.
     
  9. Jun 28, 2007 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Duh. Some times I even surprise myself with my idiocy - we need -1 =some power of n. So if n=p is prime, then we need that 10 has even order mod p - for then 1 has two square roots, 1 and -1
     
  10. Jun 28, 2007 #9
    My version is the easiest if you used my hint.

    Theorem: If there are (n+1) distinct integers then there exists two who difference is divisible by n.

    Proof: Each of these integers leaves a remainder between 0 and n-1 inclusive upon division by n. Since there are n possible remainders and (n+1) integers that means there exist two which have the same remainder by the PigeonHole Principle. So their difference is divisible by n.

    Theorem: Given any positive integer n we can find a positive number consisting of only 1's and 0's which is divisible by n.

    Proof: Construct the sequence of (n+1) integers:
    1,11,111,....,111...1
    By the first theorem two of these when subtracted are divisible by n. But when we subtract them we end up with a number consisting of only 1's and 0's. In fact, the 1's and 0's are groupped together which answers the more difficult question stated by NateTG
     
  11. Jun 28, 2007 #10

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Kummer: How about showing that any number not divisible by 2 or 5 has a multiple that is all 1s?
     
  12. Jun 28, 2007 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Kummer, I think you're under the mistake apprehension that we found your question hard....
     
  13. Jun 28, 2007 #12
    The question is not hard. It is fun and I wanted to show it to you.
     
  14. Jun 29, 2007 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Here's another (but very similar) way of showing it:

    consider the sequence 10^m mod n. This is periodic, by the pigeon hole principle. There for there are s,r integers with 10^s=10^{s+kr} mod n for k natural numbers k. Just add up any n different such powers of 10.
     
  15. Jun 29, 2007 #14

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Hmm, I wonder if there's some way to find the minimum such multiple, or the average minimum multiple.
     
  16. Jun 30, 2007 #15

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I should have been more pedantic: the sequence is eventually periodic. It need not be periodic. The idea being that at some point you must have a repeated residue, and then it becomes periodic - if 10 were invertible, then you could guarantee to run it backwards too. Eg. say n=100, the sequence goes 10,0,0,0,0,0,....
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Fun Divisibility Problem
  1. Divisibility problem (Replies: 1)

  2. Just for fun (Replies: 5)

Loading...