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.
Dirichlet convolution preserves multiplicativity, and multiplicative inverses stay multiplicative
Statement
If and are multiplicative arithmetic functions, then is multiplicative. If is multiplicative and is its Dirichlet inverse, then is multiplicative as well.
Facts & Assumptions
Given: Multiplicative arithmetic functions , and the Dirichlet inverse of .
Proof
Since , one has . Now let be coprime positive integers. By unique prime factorization from The fundamental theorem of arithmetic: every integer is a product of primes, and the factorisation is unique up to order — if with every and prime, then and for some , every positive divisor of is uniquely of the form with and . In particular, every such pair is coprime.
By An arithmetic function has a Dirichlet inverse exactly when its value at is nonzero, the inverse exists because , and .
Using the divisor splitting from step 1.1 and the multiplicativity of and on coprime pairs, . Thus is multiplicative.
To prove is multiplicative, fix coprime positive integers and argue by strong induction on . If or , then step 1.2 gives because .
Now assume and that for every coprime pair with . Since and , one has , where step 1.1 and multiplicativity of identify with . For each pair , step 1.1 gives and , so the induction hypothesis yields . Reindexing the remaining pairs by via step 1.1 therefore gives .
The inverse recursion from An arithmetic function has a Dirichlet inverse exactly when its value at is nonzero at gives . Comparing this with step 2.3 shows . Since the induction was on an arbitrary coprime pair, Strong (complete) induction yields multiplicativity of .
Depends on
- Coprime integers: $\gcd(a,b) = 1$
- Dirichlet convolution of arithmetic functions
- Multiplicative arithmetic functions
- Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule
- An arithmetic function has a Dirichlet inverse exactly when its value at $1$ is nonzero
- The fundamental theorem of arithmetic: every integer $n \ge 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i<r} p_i = \prod_{j<s} q_j$ with every $p_i$ and $q_j$ prime, then $r = s$ and $q_i = p_{\pi(i)}$ for some $\pi \in \operatorname{Sym}(r)$
- Strong (complete) induction
Used by
Dependency tree · two levels
47 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
- Victor Shoup, A Computational Introduction to Number Theory and Algebra, Theorem 2.37 (standard reference, not scraped)
- Karl-Dieter Crisman, Number Theory: In Context and Interactive, Propositions 23.4.10 and 23.4.11 (standard reference, not scraped)