- Thread starter
- Admin
- #1

- Mar 5, 2012

- 8,684

For instance 13 has the multiple 111111.

- Thread starter Klaas van Aarsen
- Start date

- Thread starter
- Admin
- #1

- Mar 5, 2012

- 8,684

For instance 13 has the multiple 111111.

- Oct 18, 2017

- 242

For instance 13 has the multiple 111111.

Let $N$ be the number. As $\gcd(N,10)=1$, $10$ has finite order, say $k$, modulo $N$. This means that $10^k-1$ is a multiple of $N$; that number consists of $k$ digits $9$.

Let $M = \dfrac{10^k-1}{9}$ (a number consisting of $k$ digits $1$). We have $10^k-1 = 9M = aN$ for some integer $a$. If $\gcd(N,3)=1$, since $N\mid 9M$, we have $N\mid M$ and we are done.

If this is not the case, let $P$ be the number obtained by copying $M$ $9$ times; this number consists of $9k$ digits $1$. Note that $P = M(1+10^k+\cdots+10^{9k})$ is a multiple of $9M$. As $M$ is a multiple of $N/9$, $P$ is a multiple of $N$.

- Moderator
- #3

- Feb 7, 2012

- 2,677

For instance 13 has the multiple 111111.

Suppose that $N$ is an integer ending in $3$, and consider the remainders when the numbers $R_1,\,R_2,\ldots,R_{N+1}$ are divided by $N$. There are only $N$ possible remainders mod $N$, so by the pigeonhole principle two of them must coincide, say $R_m \equiv R_n \pmod{N}$. So $10^mR_{n-m} \equiv 0 \pmod{N}$. But, as in castor28 's solution, $10$ is invertible mod $N$, so it follows that $R_{n-m}\equiv0\pmod{N}$. In other words, $R_{n-m}$ is a multiple of $N$.

- Mar 31, 2013

- 1,279

For instance 13 has the multiple 111111.

I shall prove a more general case why 3 , any number that does not have a factor 2 or 5 satisfies the criteria

Proof:

The number with 10 does not have a common factor and so 10 and the number say k are coprimes

Now let us consider $10^p$ mod n for p = 1 to k-1 if k is not a multiple of 3 and upto 9k-1

they shall have k-1 remainders none of them zero and one of them shall be 1

to prove that one of them has to be 1 let us assume that none of the is one.

now there are k-1 remainders and k-2 values (as zero and 1 are not there)

so they correspond to power $10^a$ and $10^b$ with same remainder and a > b

so $10^a - 10^b \equiv 0 \pmod k$

or $10^b(10^{a-b} -1) \equiv 0 \pmod k$

or $10^{a-b} -1 \equiv 0 \pmod k$

which is not true as there is a contradiction

so there is a value n so that such that $10^n -1 equiv 0 \pmod k$

if k is not multiple of 3

$10^n -1 \equiv 0 \pmod k => \frac{10^{n-1} -1}{9} \equiv 0 \pmod k$

if k is multiple of 3

$10^n -1 \equiv 0 \pmod {9k} => \frac{10^{n-1} -1}{9} \equiv 0 \pmod k$

- Thread starter
- Admin
- #5

- Mar 5, 2012

- 8,684

Thank you all, and nice to see different solutions to the same problem.

They cover the solutions that I am aware of.