Welcome to our community

Be a part of something great, join today!

Multiple consists of only 1's

  • Thread starter
  • Admin
  • #1

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,713
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
Oct 18, 2017
245
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
Feb 7, 2012
2,681
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$.
 

kaliprasad

Well-known member
Mar 31, 2013
1,283
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$
 
  • Thread starter
  • Admin
  • #5

Klaas van Aarsen

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