Maths Olympiad Prep

Library / /424 of 520

Number theory Difficulty 6.8 National olympiad Prove it

Lemma 6 If aa is an integer greater than 1, and all primes a\leqslant \sqrt{a} do not divide aa, then aa is a prime.

Solution

First, prove that if aa is not divisible by any integer >1>1 and a\leqslant \sqrt{a}, then aa is a prime number. Assume aa is a composite number and a=bca=b c, where bb and cc are both integers greater than 1. Since aa is not divisible by any integer >1>1 and a\leqslant \sqrt{a}, it follows that b>ab>\sqrt{a} and c>ac>\sqrt{a}, and thus bc>aa=ab c>\sqrt{a} \cdot \sqrt{a}=a, which contradicts bc=ab c=a. Therefore, if aa is not divisible by any integer >1>1 and a\leqslant \sqrt{a}, then aa is a prime number.

From the above, if aa is a composite number, then aa must have a divisor >1>1 and a\leqslant \sqrt{a}. By Lemma 5, the smallest divisor of aa greater than 1 must be a prime number, hence the lemma is proved.

Assume n2n \geqslant 2 is an integer, define
a1a2an={a1a2, when n=2a1a2a3, when n=3a1a2a3a4, when n=4a1a2a3a4an, when n5a_{1} a_{2} \cdots a_{n}=\left\{\begin{array}{ll} a_{1} a_{2}, & \text { when } n=2 \text {; } \\ a_{1} a_{2} a_{3}, & \text { when } n=3 \text {; } \\ a_{1} a_{2} a_{3} a_{4}, & \text { when } n=4 \text {; } \\ a_{1} a_{2} a_{3} a_{4} \cdots a_{n}, & \text { when } n \geqslant 5 \text {; } \end{array}\right.

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.