5
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ Is it 33...3 or is it 371...1? $\endgroup$ – naslundx Apr 28 '15 at 17:20
  • $\begingroup$ 371..1, thanks for editing :) $\endgroup$ – Dr. Heinz Doofenshmirtz Apr 28 '15 at 17:25
  • $\begingroup$ Try experimenting with factoring it for different values of $n$. You'll see a pattern with the small prime factors that repeats every time $n$ is increased by $6$. $\endgroup$ – aes Apr 28 '15 at 17:29
  • $\begingroup$ After doing some experimentation, I suspect this problem is not that trivial. Call $x_k$ the number with $k$ 1s. When $k \equiv 2$ mod 3, the situation is simple: the digit sum is divisible by $3$ so the number is divisible by $3$. But the other possible moduli don't seem so simple. In particular, it appears that you have to consider mod 6, not just mod 3, because $x_1$ and $x_4$ actually have no factors in common. $\endgroup$ – Ian Apr 28 '15 at 17:39
  • $\begingroup$ @CauchytheDog You can find a rigorous proof in the answer I linked to in my answer. If something is not clear there then please ask questions on that answer and I will be happy to elaborate. $\endgroup$ – Bill Dubuque Apr 28 '15 at 19:48
14
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ I could not get it. In my opinion, it seems like a guess. It couldn't be a proof. When you want to prove "If 371⋯1 is divisible by any of these prime factors, so will be that number followed by six ones." It is not sufficient to take a look at few examples but ALL possible cases. $\endgroup$ – Hyoyoung Jung Apr 28 '15 at 17:50
  • 1
    $\begingroup$ @HyoyoungJung. That's because every number of the form $371...1$ is of the form $x * 10^k + n * 111111$ where $x$ is one of the above. $\endgroup$ – JHance Apr 28 '15 at 17:56
  • 3
    $\begingroup$ @HyoyoungJung, if $37\underbrace{1\cdots1}_{n}$ is divisible by one of the primes then so is $37\underbrace{1\cdots1}_{n}000000$, thus so is $37\underbrace{1\cdots1}_{n}111111=37\underbrace{1\cdots1}_{n+6}$, because the difference $111111$ is divisible by all of them. $\endgroup$ – Yoni Rozenshein Apr 28 '15 at 17:56
  • $\begingroup$ @YoniRozenshein, JHance Thank you. Your answers are good supporting clues for me. $\endgroup$ – Hyoyoung Jung Apr 28 '15 at 18:04
  • $\begingroup$ I understand the explanation of Yoni, but could you elaborate a bit, because I am afraid I don't seem to understand it yet.. $\endgroup$ – Dr. Heinz Doofenshmirtz Apr 28 '15 at 18:06
2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ I wonder why the downvote... $\endgroup$ – gt6989b Apr 28 '15 at 17:21
2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.