Exercise 542Number theory › PrimesHigh schoolAdded 3 Nov 2026

Coprimality with primes

#coprime#prime#divisibility

Statement

Show that for a prime $p$ and integer $a$ : either $p\mid a$ or $\gcd(a,p)=1$ .

Hint

The only positive divisors of $p$ are $1$ and $p$ .

Show solutionHide solution

Divisors. $d=\gcd(a,p)$ divides $p$ , so $d\in\{1,p\}$ .

Case $d=1$ . $\gcd(a,p)=1$ .

Case $d=p$ . $p\mid a$ .

Conclusion. Either $p\mid a$ or $\gcd(a,p)=1$ (mutually exclusive).

Corollary. For $p$ prime and $a\not\equiv0\pmod p$ , $a$ is invertible mod $p$ .