# Multiple consists of only 1's

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Given a number that ends in 3, prove that it has a multiple that consists of only 1's.

For instance 13 has the multiple 111111.

#### castor28

##### Well-known member
MHB Math Scholar
Given a number that ends in 3, prove that it has a multiple that consists of only 1's.

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$.

#### Opalg

##### MHB Oldtimer
Staff member
Given a number that ends in 3, prove that it has a multiple that consists of only 1's.

For instance 13 has the multiple 111111.
Let $R_n$ be the number consisting of $n$ $1$s. If $n>m$ then $R_n - R_m$ consists of $n-m$ $1$s followed by $m$ $0$s. So $R_n - R_m = 10^mR_{n-m}$.

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$.

##### Well-known member
Given a number that ends in 3, prove that it has a multiple that consists of only 1's.

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$

#### Klaas van Aarsen

##### MHB Seeker
Staff member
All correct.
Thank you all, and nice to see different solutions to the same problem.
They cover the solutions that I am aware of.