Waste less time on Facebook — follow Brilliant.
×

String of 1s and Prime numbers

Can you prove that if \[\frac{10^{n}-1}{9} \] is a prime number then 'n' is also a prime number?

Note by Vikram Pandya
3 years, 1 month ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Umm.. Yes, I can :)

Let's prove the contrapositive. In other words, we're going to prove that if \(n\) is not a prime number, then \(\frac{10^9-1}{9}\) will never be a prime number.

Let \(n\) be equal to \(ab\) where \(a\) and \(b\) are two positive integers greater than \(1\).

Now notice that

\[\frac{10^{ab}-1}{9}=\frac{10^a-1}{9}\times (1+10^a+10^{2a}+10^{3a}+\cdots 10^{a(b-1)})\]

which is definitely not a prime number.

A fun fact: primes in the form of \(\frac{10^n-1}{9}\) are called repunit primes. Mursalin Habib · 3 years, 1 month ago

Log in to reply

@Mursalin Habib This is true for any base.A repunit is of the form \[\dfrac{b^n-1}{b-1}\] in base \(b\).The above result holds in any base that a repunit is a prime if \(n\) is a prime. Rahul Saha · 3 years, 1 month ago

Log in to reply

Here's a related problem:

How many numbers of the form \( 1010\ldots 0101 \) are prime? Calvin Lin Staff · 3 years, 1 month ago

Log in to reply

@Calvin Lin only \(101\) is a prime Sagnik Saha · 2 years, 9 months ago

Log in to reply

@Calvin Lin Some initial thoughts:

\(101\) is prime.

\(10101\) is a multiple of \(3\). (This holds for all other cases where the number of \(1\)s are a multiple of \(3\))

\(1010101\) is the product of at least two factors, namely \(101\) and \(10001\). This holds for all greater cases where the number of \(1\)s are even.

Haven't thought of when the number of \(1\)s are odd though. Michael Tong · 3 years, 1 month ago

Log in to reply

@Michael Tong When the number of \( 1 \)s is odd, the number is divisible by the repunit you get by taking out all of the zeroes; e.g. \( 10101 \) is divisible by \( 111 \), \( 101010101 \) is divisible by \( 11111 \), and so on. This is because \( 1+10^2 + 10^4 + \cdots + 10^{2n} = (1+10+10^2+\cdots+10^n)(1-10+10^2-\cdots+10^n). \) Note that the last sign in that alternating factor is a \( + \) only if \( n \) is odd. Patrick Corn · 3 years, 1 month ago

Log in to reply

@Calvin Lin

  1. http://mathforum.org/library/drmath/view/61896.html http://askville.amazon.com/binary-numbers-form-101-10101-1010101-prime/AnswerViewer.do?requestId=30307452
Shamik Banerjee · 3 years, 1 month ago

Log in to reply

Yeah the one way of doing this. I was not sure how to put proof related questions on this forum. But this is good level 4 question otherwise :) Vikram Pandya · 3 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...