LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

$φ (m) φ (n) = φ (\gcd (m, n)) φ (lcm (m, n))$

Statement

For all integers $m, n \geq 1$ ,

(The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ , Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ). At $m = n = 1$ both sides are $1$ ; at $\gcd (m, n) = 1$ the identity is the multiplicativity $φ (m) φ (n) = φ (m n)$ .

Facts & Assumptions

Given: Integers $m, n \geq 1$ ; write $g : = \gcd (m, n)$ and $ℓ : = lcm (m, n)$ , both $\geq 1$ because $m$ and $n$ are nonzero. For a prime $p$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ) and an integer $e \geq 0$ put $w (p, e) : = p^{e} - p^{e - 1}$ when $e \geq 1$ and $w (p, 0) : = 1$ . For $k \geq 1$ write $D (k)$ for the set of primes dividing $k$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ); it is finite, being contained in ${2, \dots, k}$ by If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ . Put $P : = D (m) \cup D (n)$ . Finite products over such sets are those of The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form.

[L1]

Let $k \geq 1$ and let $p_{0}, \dots, p_{r - 1}$ be an injective finite list consisting exactly of the prime divisors of $k$ ; put $e_{i} : = v_{p_{i}} (k)$ , so $e_{i} \geq 1$ . Then $φ (k) = \prod_{i < r} (p_{i}^{e_{i}} - p_{i}^{e_{i} - 1})$ (Euler's product formula $φ (n) = n \prod_{p ∣ n} (1 - 1 / p) = \prod_{p^{k} ∥ n} (p^{k} - p^{k - 1})$ for $n \geq 1$ , stated through a finite injective list of its prime divisors).

[L2]

For $a, b \geq 1$ and every prime $p$ : $v_{p} (\gcd (a, b)) = \min {v_{p} (a), v_{p} (b)}$ and $v_{p} (lcm (a, b)) = \max {v_{p} (a), v_{p} (b)}$ (For positive integers $a$ and $b$ and every prime $p$ : $v_{p} (\gcd (a, b)) = \min {v_{p} (a), v_{p} (b)}$ and $v_{p} (lcm (a, b)) = \max {v_{p} (a), v_{p} (b)}$ ; so the exponent-wise greatest common divisor is the $\gcd$ of the divisibility page and not a second notion).

[L3]

For a prime $p$ and a nonzero integer $a$ , $v_{p} (a)$ is the greatest $k \in N$ with $p^{k} ∣ a$ (The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ a$ ).

Proof

technique · direct

1.1L3

For a prime $p$ and an integer $k \geq 1$ : $p ∣ k$ if and only if $v_{p} (k) \geq 1$ . If $v_{p} (k) \geq 1$ then $p$ divides $p^{v_{p} (k)}$ , which divides $k$ by [L3]; conversely $p ∣ k$ says $p^{1} ∣ k$ , so the greatest such exponent is at least $1$ .

1.2L2given

For each $p \in P$ write $a : = v_{p} (m)$ and $b : = v_{p} (n)$ ; then $v_{p} (g) = \min {a, b}$ and $v_{p} (ℓ) = \max {a, b}$ by [L2], and the unordered pair ${\min {a, b}, \max {a, b}}$ is ${a, b}$ , so $w (p, a) w (p, b) = w (p, v_{p} (g)) w (p, v_{p} (ℓ))$ .

2.1step 1.1L2

Consequently $D (g) = D (m) \cap D (n)$ and $D (ℓ) = D (m) \cup D (n)$ : by [L2] and step 1.1, $p \in D (g)$ says $\min {v_{p} (m), v_{p} (n)} \geq 1$ , that is $p \in D (m)$ and $p \in D (n)$ ; and $p \in D (ℓ)$ says $\max {v_{p} (m), v_{p} (n)} \geq 1$ , that is $p \in D (m)$ or $p \in D (n)$ .

3.1step 1.1step 2.1L1given

The set $P$ is a finite set of primes containing $D (m)$ , $D (n)$ , $D (g)$ and $D (ℓ)$ by step 2.1. For every $k \in {m, n, g, ℓ}$ one has $φ (k) = \prod_{p \in P} w (p, v_{p} (k))$ : applying [L1] with the list $D (k)$ gives $φ (k) = \prod_{p \in D (k)} w (p, v_{p} (k))$ , and for $p \in P$ outside $D (k)$ step 1.1 gives $v_{p} (k) = 0$ , so the extra factors are $w (p, 0) = 1$ .

4.1step 3.1step 1.2∎

Multiplying the equalities of step 1.2 over the finite set $P$ and using step 3.1 four times gives $φ (m) φ (n) = \prod_{p \in P} w (p, v_{p} (m)) w (p, v_{p} (n)) = \prod_{p \in P} w (p, v_{p} (g)) w (p, v_{p} (ℓ)) = φ (g) φ (ℓ)$ .

Remarks

Why the identity is not simply multiplicativity. For coprime $m$ and $n$ it reduces to $φ (m n) = φ (m) φ (n)$ , but the general case is what the intersection theorem needs: the degrees of $Q (μ_{m})$ and $Q (μ_{n})$ multiply to the degree of the compositum times the degree of the intersection, and it is the gcd–lcm form of the identity that turns that into $φ (\gcd (m, n))$ ( $Q (μ_{m}) \cap Q (μ_{n}) = Q (μ_{\gcd (m, n)})$ ).

Depends on

Used by

ℚ(μₘ)∩ℚ(μₙ)=ℚ(μ_gcd(m,n)) Theorem

Dependency tree · two levels

68 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

K. Conrad, Cyclotomic Extensions (expository blurb), formula (4.1) in Section 4 (standard reference, not scraped)
P. L. Clark, Field Theory (course notes/monograph), Chapter 9, Section 1 (standard reference, not scraped)

φ(m)φ(n)=φ(gcd⁡(m,n)) φ(lcm⁡(m,n))φ(m)φ(n)=φ(gcd(m,n))φ(lcm(m,n))

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Used by

Dependency tree · two levels

Sources

$φ (m) φ (n) = φ (\gcd (m, n)) φ (lcm (m, n))$