Maths Olympiad Prep

Library / Ukrainian National Mathematical Olympiad /65 of 201

Ukrainian National Mathematical Olympiad

Number theory Difficulty 5.5 AIME, harder Prove it Ukraine

It is given that there exists such prime pp, for which 1017≤p≤1017+1010^{17} \le p \le 10^{17} + 10. Find pp.

Solution

We should find the last digit of this number. It cannot be even or equal to 55.

Number 1017+110^{17} + 1 is divisible by 1111.

Consider number 1017+910^{17} + 9 modulo 77. Then, 10≡3(mod7)⇒102≡2(mod7)⇒103≡−1(mod7)⇒1015≡−1(mod7)⇒1017≡−2(mod7)⇒1017+9≡0(mod7)10 \equiv 3 \pmod{7} \Rightarrow 10^2 \equiv 2 \pmod{7} \Rightarrow 10^3 \equiv -1 \pmod{7} \Rightarrow 10^{15} \equiv -1 \pmod{7} \Rightarrow 10^{17} \equiv -2 \pmod{7} \Rightarrow 10^{17} + 9 \equiv 0 \pmod{7}.

Consider number 1017+710^{17} + 7 modulo 1717. 10≡10(mod17)⇒102≡−2(mod17)⇒108≡16≡−1(mod17)⇒1016≡1(mod17)⇒1017≡10(mod17)⇒1017+7≡0(mod17)10 \equiv 10 \pmod{17} \Rightarrow 10^2 \equiv -2 \pmod{17} \Rightarrow 10^8 \equiv 16 \equiv -1 \pmod{17} \Rightarrow 10^{16} \equiv 1 \pmod{17} \Rightarrow 10^{17} \equiv 10 \pmod{17} \Rightarrow 10^{17} + 7 \equiv 0 \pmod{17}.

Thus, the only candidate for a prime number left is 1017+310^{17} + 3, and since it is given that such a number exists, this must be it.

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

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