5

I suspect, that the prime divisors of the series of 1, 11, 111, 1111, ... 1...1 will contain every primes. But this is an intuitive hypothesis only. Somebody knows, if it is so? How could it be proven/disproven?

peterh
  • 2,683
  • 3
    $5$ will also not be a divisor. But other than those, yes, all primes (and in fact all numbers not divisible by $2$ or $5$) will be divisors. – Tobias Kildetoft Mar 31 '14 at 12:28
  • 7
    For a hint on how to prove it: Consider a fixed prime $p$ apart from $2$ or $5$. There are infinite many numbers of the form described, so at least two of them must have the same remainder mod $p$, and thus those two must have a difference divisible by $p$. What does that difference look like? – Tobias Kildetoft Mar 31 '14 at 12:30
  • @TobiasKildetoft The differences are the elements of the same series, multiplied by 10^n ! I understand, it is wonderful! I really accepted/upvoted your comment if I could! – peterh Mar 31 '14 at 12:39

3 Answers3

3

We can prove more very simply: if $\rm\:m\:$ is coprime to $10\,$ then any number with $\rm\: m\:$ digits all $\ne 0$ has a contiguous digit subsequence that forms a number divisible by $\rm\:m.\:$ Suppose the digits are $\rm\:d_{m}\ldots d_1.\:$ By $\rm\,d_i\ne 0\:$ the $\rm\:m\!+\!1\:$ numbers $\rm\:0,\,d_1,\, d_2 d_1,\, d_3 d_2 d_1,\, \ldots,d_m\!\ldots d_1$ are distinct. By Pigeonhole two are congruent $\rm\:mod\ m,\:$ so $\rm\:m\:$ divides their difference $\rm = 10^k\:$ times the number $\rm\,n\ne 0\,$ formed by the extra digits of the longest, so $\rm\:m\,|\,10^kn\:$ $\Rightarrow$ $\rm\:m\:|\:n,\:$ by $\rm\:m\:$ is coprime to $10.\:$

Let's do a simple example. Let $\rm\:m=9,\:$ and let the number be $\rm\:98765\color{green}{432}1.\:$ Modulo $9$ we have $\rm\:1 \equiv\color{#C00} 1,\ 21\equiv 3,\ 321\equiv 6,\ 4321\equiv\color{#C00} 1,\:$ so $\rm\:9\:|\:4321\!-\!1 = 432\cdot 10,\:$ so $\,9\,|\,\color{green}{432}.$

In your case, the divisor $\rm\:m=p\:$ is a prime coprime to $10$, so the number $\,111\ldots 111$ $\rm\,(m$ digits) does the trick, i.e. some subsequence $11\ldots 11$ is divisible by $\rm\:m.$

The result extends to any number having $\rm\:m\:$ nonzero digits: simply take the subsequences beginning with nonzero leading digit. This implies that the $\rm\:m+1\:$ numbers are increasing (so distinct), and the number formed by the extra digits is nonzero, since its leading digit is nonzero.

Bill Dubuque
  • 272,048
1

Tobias Kildetoft's excellent answer (posted as comment) was this:

  1. Consider any prime $p$ apart from 2 or 5.
  2. There are infinite many numbers like 1...1. So there must be two between them having the same remainder $\mod p$. Call them for example $a$ and $b$.
  3. $b-a$ will have to look like 1...10...0, and it will be divisible by $p$.

QED.

peterh
  • 2,683
1

Consider the sequence $10^k$ modulo $p$ (except for $p=2,3,5$, which we will handle separately). Since there are only $p$ equivalence classes mod $p$, for any group of $p+1$ $k$'s, we must have $k_1\gt k_2$ so that $10^{k_1}\equiv10^{k_2}\pmod{p}$. Since $(p,10)=1$, this implies $$ 10^{k_1-k_2}-1\equiv0\pmod{p} $$ and since $(p,3)=1$, we have $$ \frac{10^{k_1-k_2}-1}9\equiv0\pmod{p} $$ This is a sequence of $k_1-k_2$ ones in base-ten. $$ 111\equiv0\pmod3 $$ This is not true for $p=2$ and $p=5$ since no multiple of $2$ or $5$ can be equal to $1$ mod $10$.

robjohn
  • 345,667