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?

#NumberTheory #Mathematics

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 7 years, 4 months ago

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 - 7 years, 4 months ago

Here's a related problem:

How many numbers of the form $1010\ldots 0101$ are prime?

Calvin Lin Staff - 7 years, 4 months ago

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 - 7 years, 4 months ago

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 - 7 years, 4 months ago

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 - 7 years, 4 months ago

only $101$ is a prime

Sagnik Saha - 7 years ago

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 - 7 years, 4 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$