Competition problem — Number theory

Library / /132 of 520

Number theory Difficulty 5.7 AIME, harder Prove it

Lemma 12 If $p$ is a prime, then $p \nmid a$ implies $(p, a)=1$ , and when $(p, a)=1$ it implies $p \nmid a$ .

Solution

Since $p$ is a prime number, $p$ has only two positive divisors, which are 1 and $p$ . If $p \nmid a$ , then only $(p, a)=1$ . Conversely, if $(p, a)=1$ , then $p$ is not a common divisor of $p$ and $a$ , so $p \nmid a$ .

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.