Блог пользователя snorkel

Proof about powers of 10-s
Автор snorkel, история, 4 года назад, По-английски

Recently I was solving the problem which said that I have to find the smallest number consisting of only 1-s (1, 11, 111, ...) which will be divisible by the given number $$$n$$$. This problem is easy, but I was surprised that it is possible for any $$$n$$$ not divisible $$$2$$$ and $$$5$$$. (at least for $$$<= 100 000$$$). How can I prove this?

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

I hate to be that guy, but technically it isn't possible for any $$$n$$$. $$$n=10$$$, $$$n=5$$$, and $$$n=2$$$ are all break cases.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Forgot to mention, any numbers except those divisible by $$$2$$$ and $$$5$$$.

    Thanks.

    → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

write down all numbers 1,11,111,...,11...1 (n+1 times).
now you have $$$n+1$$$ numbers,but at most $$$n$$$ different values modulo $$$n$$$,so pigeonhole says two of them have same remainder modulo $$$n$$$.
take these two,subtract smaller one from larger one,and you will have some number like 11...100...0that is divisible by $$$n$$$.now you can remove all trailing zeros(because it doesn't change divisibility by $$$n$$$) and you will have some 11...1 divisible by $$$n$$$.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    because it doesn't change divisibility by n

    But why? It's not obvious at all. When you remove the trailing zeros the number will become the sum of different powers of 10. For example 110 is divisible by 5 but 11 is not although 5 is not included in here. It's not easy to believe that.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      $$$a \mid 10^kb, gcd(10^k, a) = 1 \Rightarrow a \mid b$$$.

      → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      consider you have $$$d = 11...100...0$$$ .
      - $$$d$$$ is divisible by $$$n$$$ ,so $$$d = nk$$$ for some $$$k$$$.
      - $$$d$$$ is divisible by 10 ,but $$$gcd(n,10) = 1$$$.so $$$d = n*q*10^p$$$ for some $$$q$$$ and $$$p$$$.
      so when you divide $$$d$$$ by $$$10^p$$$, $$$d$$$ becomes equal to $$$nq$$$.
      so $$$d$$$ remains divisible by $$$n$$$.

      UPD : fixed a minor bug!

      → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hello there, I went searching for the answer, ended up with this interesting blog , I think it might help you.

Summary of the proof is: the all-1-sequence is infinte, so as you mod each all-1 number by n, (where n is not a multiple of 2 or 5, means n%10 != 0)

Either one of the remainders is 0, so boom! Divided.

Or, the sequence being infinite, at one point a number shall occur a second time in the remainders list. (From pigeonhole principle, even in worst case, within every (n+1)th iteration, as we mod by n)

Now if for 2 all-1 numbers a and b, a % n == b % n then => (a-b) % n == 0

again, as a and b are all-1 numbers and if a > b,

the number a-b will be of the form 111...10...000 (p x 10^q, where p is an all-1 number and q is a positive integer)

But as we assumed n%10!=0, n (and eventually any multiple of n) cannot have trailing zeroes,

That means, 10^q % n != 0

But (p x 10^q) % n == 0

So, from modular arithmetic, p % n == 0 and we already agreed that p itself is an all-1 number.

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

It can be shown that $$$a = \frac{10^{\phi(9n)} - 1}{9}$$$ is divisible by $$$n$$$, where $$$\phi$$$ is Euler's totient function.

Proof:

Euler's theorem states that $$$k^{\phi(n)} = 1 \space (mod \space n)$$$, given $$$gcd(k, n) = 1$$$. Now if we set $$$b = 10^{\phi(9n)}$$$, then $$$b = 1 \space (mod \space 9n)$$$. So $$$9n$$$ divides $$$c = b - 1$$$, and as $$$c$$$ is made of $$$9$$$s, we can divide $$$c$$$ by $$$9$$$ to get $$$a = 0 \space (mod \space n)$$$, consisting only of 1s.

Please note that, this number may not necessarily be the smallest such number. for example this isn't the case for 11.

→ Ответить