Maths Olympiad Prep

Library / /7 of 27

Number theory Difficulty 5.4 AIME, harder Prove it Croatia

If nn is a positive integer, let RnR_n denote the integer that in the decimal representation consists of nn digits 1. Prove the following statement: if RnR_n is a prime number, then nn is a prime number, too.

Solution

Let RnR_n be the integer consisting of nn digits 1. That is,
Rn=1111n digits=10n19. R_n = \underbrace{111\ldots1}_{n\ \text{digits}} = \frac{10^n - 1}{9}.

Suppose RnR_n is a prime number. We want to show that nn is also a prime number.

Assume, for contradiction, that nn is composite. Then n=abn = ab for integers a,b>1a, b > 1.

Consider RaR_a:
Ra=10a19. R_a = \frac{10^a - 1}{9}.

Now, note that
10n1=10ab1=(10a)b1=(10a1)(10a(b1)+10a(b2)++10a+1). 10^n - 1 = 10^{ab} - 1 = (10^a)^b - 1 = (10^a - 1)\left(10^{a(b-1)} + 10^{a(b-2)} + \cdots + 10^a + 1\right).

Therefore,
Rn=10n19=10a19(10a(b1)+10a(b2)++10a+1). R_n = \frac{10^n - 1}{9} = \frac{10^a - 1}{9} \cdot \left(10^{a(b-1)} + 10^{a(b-2)} + \cdots + 10^a + 1\right).

Since a,b>1a, b > 1, both factors are greater than 1, so RnR_n is composite, contradicting the assumption that RnR_n is prime.

Therefore, if RnR_n is prime, nn must be prime.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.