Exercise 1142Number theory › PrimesL1Added 3 Nov 2026

Prime powers and divisibility

#prime powers#divisibility#exponents

Statement

Let $p$ be prime and $a,b$ integers with $p^k\mid ab$ . Show that $p^{\lceil k/2\rceil}$ divides $a$ or $b$ (weaker version), and more precisely that the sum of exponents of $p$ in $a$ and $b$ is at least $k$ .

Hint

Use the $p$ -adic valuation: $v_p(ab)=v_p(a)+v_p(b)\ge k$ .

Show solutionHide solution

Solution

Valuation. $v_p(ab)=v_p(a)+v_p(b)\ge k$ .

Consequence. At least one of $v_p(a),v_p(b)$ is $\ge\lceil k/2\rceil$ , so $p^{\lceil k/2\rceil}\mid a$ or $p^{\lceil k/2\rceil}\mid b$ .

Conclusion. The $p$ -adic valuation gives the precise statement.

Prime powers and divisibility

Statement

Solution

More problems in Primes