Maths Olympiad Prep

Library / /371 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Prove it

Let pp - a prime, where p>11p> 11. Prove that there exists a number kk such that the product pkp \cdot k can be written in the decimal system with only ones.

Solution

1. Understanding the Problem:
We need to prove that for any prime p>11 p > 11 , there exists an integer k k such that the product pk p \cdot k can be written in the decimal system using only the digit 1. This means we need to find k k such that pk p \cdot k is a repunit number (a number consisting only of the digit 1).

2. Properties of Repunit Numbers:
A repunit number in decimal form can be written as:
Rn=10n19 R_n = \frac{10^n - 1}{9}
where n n is the number of digits (all being 1).

3. **Finding k k :**
We need to find k k such that:
pk=Rn=10n19 p \cdot k = R_n = \frac{10^n - 1}{9}
for some integer n n .

4. Using Modular Arithmetic:
Since p p is a prime and p>11 p > 11 , we know that gcd(10,p)=1 \gcd(10, p) = 1 . By Fermat's Little Theorem, we have:
10p11(modp) 10^{p-1} \equiv 1 \pmod{p}
This implies:
10p110(modp) 10^{p-1} - 1 \equiv 0 \pmod{p}
Therefore, 10p11 10^{p-1} - 1 is divisible by p p .

5. Constructing the Repunit:
Consider the number:
Rp1=10p119 R_{p-1} = \frac{10^{p-1} - 1}{9}
Since 10p11 10^{p-1} - 1 is divisible by p p , we can write:
10p11=pm 10^{p-1} - 1 = p \cdot m
for some integer m m . Thus:
Rp1=pm9 R_{p-1} = \frac{p \cdot m}{9}

6. **Finding k k :**
We need k k such that:
pk=Rp1 p \cdot k = R_{p-1}
From the above, we have:
k=Rp1p=10p119p=10p119p k = \frac{R_{p-1}}{p} = \frac{\frac{10^{p-1} - 1}{9}}{p} = \frac{10^{p-1} - 1}{9p}

7. Conclusion:
Therefore, the number k=10p119p k = \frac{10^{p-1} - 1}{9p} satisfies the condition that pk p \cdot k is a repunit number.

k=10p119p \boxed{k = \frac{10^{p-1} - 1}{9p}}

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.