Number Theory • Topic 20

p-adic Valuation

The p-adic valuation $v_{p} (n)$ counts "how many times" a prime $p$ divides an integer $n$ . It turns multiplicative problems into additive ones.

Definition

Definition (p-adic Valuation)

For a prime

p

and non-zero integer

n

v_{p} (n)

is the largest integer

k

such that

p^{k} ∣ n

v_{p} (n) = k ⟺ p^{k} ∥ n

Convention:

v_{p} (0) = \infty

Properties

$v_{p} (ab) = v_{p} (a) + v_{p} (b)$ (Logarithm-like property).
$v_{p} (a / b) = v_{p} (a) - v_{p} (b)$ .
$v_{p} (a^{n}) = n v_{p} (a)$ .
$v_{p} (a + b) \geq min (v_{p} (a), v_{p} (b))$ .

Equality holds if $v_{p} (a) \neq = v_{p} (b)$ .

If $v_{p} (a) = v_{p} (b)$ , the valuation of the sum can be strictly larger.

Legendre's Formula (Review)

v_{p} (n!) = k = 1 \sum \infty ⌊ \frac{n}{p ^{k}} ⌋

Practice Problems

Exercise (Problem 1)

Find

v_{2} (100!)

Exercise (Problem 2)

Prove that

\sum_{k = 1}^{n} \frac{1}{k}

is never an integer for

n > 1

. (Hint: Use $v_{2}$ on the sum).

Exercise (Problem 3)

Find all

n

such that

n!

is divisible by

2^{n - 1}