Prove that $371\cdots 1$ is not prime

Question

Prove that $371\cdots 1$ is not prime.

I tried mathematical induction in order to prove this, but I am stuck.

My partial answer:

To be proved is that $37\underbrace{111\cdots 1}_{n\text{ ones}}$ is never prime for $n\geq 1$. Let $P(n)$ be the statement that $37\underbrace{111\cdots 1}_{n\text{ enen}}$ is not prime.

For $n=1$, we can write $371=7\cdot 53$, and therefore $P(1)$ is true. Let $P(k)$ be true for $k>1$. Then we now have to prove that $P(k+1)$ is true.

I found that $37\underbrace{111\cdots 1}_{k\text{ ones}}$ can be written as $37\cdot 10^k+10^{k-1}+10^{k-2}+\cdots +10^0$ and that $37\underbrace{1111\cdots 1}_{k+1\text{ ones}}$ can be written as $37\cdot 10^{k+1}+10^{k}+10^{k-1}+\cdots+10^0$.

I think I'm pretty close to the answer know, but I don't know how to proceed.

Answer 1

Hints not to give this away completely:

Notice $111 = 37 \times 3$ so since it starts with 37, what happens if you add a number of ones divisible by $3$, like $37,111$ or $37,111,111$, etc?

Also notice if you take $3711$, the sum of digits is divisible by 3, so this should take care of $3,711$ or $3,711,111$ or $3,711,111,111$ or the like.

This leaves only one sequence class for you to deal with. Can you?

Answer 2

First note that $111111=3 \cdot 7 \cdot 11\cdot 13\cdot 37$.

If $371\cdots 1$ is divisible by any of these prime factors, so will be that number followed by six ones. It suffices to look at the factorizations of $371$, $3711$, $37111$, $371111$, $3711111$, and $37111111$.

$371 = \mathbf{7} \cdot 53$

$3711 = \mathbf{3} \cdot 1237$

$37111 = 17 \cdot \mathbf{37} \cdot 59$

$371111 = \mathbf{13} \cdot 28547$

$3711111 = \mathbf{3} \cdot 1237037$

$37111111 = \mathbf{37} \cdot 1003003$

Answer 3

If $n$, the number of ones, is a multiple of $3$, then $N=37111\cdots111$ is a multiple of $37$ (because $111=37\cdot3$).

If $n=3k+2$ then $N$ is a multiple of three, because the sum of its digits is $3k+12$, a multipe of three.

For the remainding cases, consider that $371$ is a multiple of $7$ , $371111$ is a multiple of $13$ and $111111=3\cdot 7\cdot13\cdot 11\cdot37$

Answer 4

Hint $\ $ Do a covering congruence argument mod $\color{#c00}6$ using the divisors $3,7,13,37\,$ of $\,10^{\color{#c00}6}-1$