2
$\begingroup$

Let $k \in \mathbb{N}$. Prove that there are infinitely many prime numbers ending in $k$ 1's.

I have a couple basic ideas about how to construct a proof of this but I really can't follow any to completion. I thought about trying induction but I can't find a way prove the base case let alone to construct a prime with n + 1 1's. This proof would seem to indicate a way construct arbitrarily large primes so this suggests that induction is out of the question. I'm currently leaning towards a proof by contradiction.

Suppose for some $k \in \mathbb{N}$ we have that there are only finitely many primes ending in $k$ 1's. I want to somehow construct another prime with $k$ 1's that's not on the list. I really don't know how to do this either.

A couple small things that might help:

  • Any number consisting only of a composite number of repeated 1's is composite (the converse is not true)
  • a number ending in $k$ 1's is of the form $\frac{10^k(90a + 1) - 1}{9}$ for some natural number $a$. So equivalently we can try to prove there are infinitly many primes of this form.
  • It is equivalent show that for each $k \in \mathbb{N}$ there is at least 1 prime ending in $k$ 1's, since any prime ending in more than $k$ 1's will also end in $k$ 1's.

What would be best if I could get a hint or some suggestion as to how to attack this problem. A full solution is ok, but a hint is much more appreciated thank you!

$\endgroup$
  • 1
    $\begingroup$ Dirichlet's theorem states that there are infinitely many primes congruent to $a$ mod $m$ whenever $\gcd(a,m) = 1$. Your question is a special case of this where $m=10^k$ and a = $\sum_{i=0}^{k-1}{10^i}$ $\endgroup$ – rikhavshah Aug 14 '16 at 22:24
  • 1
    $\begingroup$ Rule of thumb. Don't ever use induction on theorems about prime numbers. There are exceptions but as one can't predict $p_{n+1} $ from $p_n $ they almost never work. $\endgroup$ – fleablood Aug 15 '16 at 0:17
5
$\begingroup$

We can just use Dirichlet's theorem, we need to show there's an infinity of primes in the progression $\frac{10^k-1}{9}+d10^k$.

$\endgroup$
  • 1
    $\begingroup$ Genius, thank you so much. We had learned Dirichlet's Theorem earlier but I've never needed it until now. $\endgroup$ – Sean Haight Aug 14 '16 at 22:23
  • 1
    $\begingroup$ @SeanHaight do not forget to check you actually can apply D.T. here. It is not hard, but it needs to be done. $\endgroup$ – quid Aug 14 '16 at 22:24
  • $\begingroup$ you are 100% completely welcome $\endgroup$ – Jorge Fernández Hidalgo Aug 14 '16 at 22:24
  • $\begingroup$ I just need to show $10^k$ and $10^k - 1$ are coprime right. $\endgroup$ – Sean Haight Aug 14 '16 at 22:26
  • $\begingroup$ yup ${}{}{}{}{}{}{}{}{}$ $\endgroup$ – Jorge Fernández Hidalgo Aug 14 '16 at 22:27

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.