1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...