Maths WorkshopMaths problems with full solutions
Exercise 1122Number theory › PrimesL1Added 3 Nov 2026

Coprime integers and prime divisors

#coprime#prime divisors#intersection

Statement

Show that a,ba,b are coprime iff they have no common prime divisor.

Hint

Decompose a,ba,b into prime factorizations.

Show solutionHide solution

Solution

Forward. If gcd⁡(a,b)=1\gcd(a,b)=1 and prime p∣a,bp\mid a,b, then p∣gcd⁡(a,b)=1p\mid\gcd(a,b)=1, contradiction.

Converse. If no prime divides both, then any common divisor d>1d>1 has a prime divisor pp (previous result), which divides both. Contradiction. So d=1d=1.

Conclusion. Coprimality is equivalent to disjoint prime divisor sets.

Remark. gcd⁡(a,b)=∏p∣a,bpmin⁡(vp(a),vp(b))\gcd(a,b)=\prod_{p\mid a,b}p^{\min(v_p(a),v_p(b))}.