Count divisors and units through prime powers

Try

Positive divisors of twelve are 1, 2, 3, 4, 6, 12. Their count is six and their sum is twenty-eight. Factorization 12=2²·3 makes both quantities systematic: a divisor chooses a power of two from 0, 1, 2 and a power of three from 0, 1. Each choice produces exactly one divisor. This turns a list into a reusable product rule.

Predict

Predict whether the divisor count of ab always equals the product of the two divisor counts. It does for coprime a, b, because their prime choices do not overlap. It fails for a=b=2: four has three divisors, not four. Multiplicative means the product rule under coprimality; completely multiplicative means the rule without that restriction. The difference matters throughout arithmetic-function identities.

Experiment

Organize the divisors of twelve as exponent choices.

Power of three	2⁰	2¹	2²
3⁰	1	2	4
3¹	3	6	12

Summing the grid factors as (1+2+4)(1+3)=28. Counting it factors as 3·2=6. Repeat with 18 and identify which exponent range changes.

Understand

An arithmetic function maps positive integers to numbers. For n=∏pᵢ^aᵢ, unique factorization gives τ(n)=∏(aᵢ+1) and σ(n)=∏(1+pᵢ+⋯+pᵢ^aᵢ). The geometric sum can be written (pᵢ^(aᵢ+1)−1)/(pᵢ−1). The totient counts units: φ(p^k)=p^k−p^(k−1), since the nonunits are precisely multiples of p. CRT makes φ multiplicative, giving φ(n)=n∏_(p|n)(1−1/p). Empty products at n=1 give τ(1)=σ(1)=φ(1)=1. State this convention so later divisor sums include the endpoint correctly.

Why CRT also pairs the units

A unit modulo m is a residue x with a multiplicative inverse: some integer y satisfies xy≡1 modulo m. For coprime positive moduli m,n, the Chinese remainder theorem (CRT) makes the map x modulo mn ↦ (x modulo m, x modulo n) a bijection on all residue classes. A bijection on all objects does not by itself prove a bijection on a selected subset: we must check units in both directions.

If x has an inverse modulo mn, reducing the identity modulo m and modulo n gives both component inverses. Conversely, suppose the two component residues are units. Choose an inverse in each component and use CRT to assemble an integer y with those two inverse residues. Then xy−1 is divisible by m and by n. Since the moduli are coprime, mn divides xy−1, so y is an inverse modulo mn. This proves that the CRT bijection restricts exactly to the units. Counting its target pairs gives φ(mn)=φ(m)φ(n).

Try m=4,n=3. The units modulo 4 are 1,3 and those modulo 3 are 1,2. Predict the four units modulo 12 from their pairs before opening the table.

Check the unit pairs and a failed hypothesis

Residue modulo 12	Residue modulo 4	Residue modulo 3
1	1	1
5	1	2
7	3	1
11	3	2

There are 2·2=4 unit pairs. For a changed case, m=n=2 is not coprime: φ(4)=2 but φ(2)φ(2)=1. Both units 1 and 3 modulo 4 reduce to the same pair (1,1), so the proposed map is not injective. The missing hypothesis changes the counting argument.

Finally, distinct prime-power factors of N are pairwise coprime. Repeatedly apply the proved product rule, substituting φ(pᵏ)=pᵏ(1−1/p) at each factor. This derives the prime-product formula above rather than assuming it in the proof of multiplicativity.

Why almost every totient is even

Modulo 12 the units pair as (1, 11) and (5, 7): pair a with 12 − a. For any n greater than two, this map preserves coprimality and applying it twice returns a. A fixed point would give n dividing 2a. Since a is a unit, cancellation would imply n divides 2, impossible. Thus the units split into disjoint pairs and φ(n) is even. The exceptions are φ(1)=φ(2)=1. In particular, no positive integer has totient 9; a long unsuccessful search is unnecessary.

Reverse the question with a completeness proof

Computing φ(36)=12 verifies one answer. How do we find every positive n with φ(n)=12, including answers larger than twelve?

Which integers have this many units?

Predict the allowed primes and all answers before revealing the enumeration. Each row chooses one exponent for each allowed prime; exponent zero omits that prime.

Target φ(n) 1246891012 Reset

Allowed primes: 2, 3, 5, 7, 13. For each, p − 1 divides 12.

• p = 2: exponents 0, 1, 2, 3; local totients 1, 1, 2, 4.
• p = 3: exponents 0, 1, 2; local totients 1, 2, 6.
• p = 5: exponents 0, 1; local totients 1, 4.
• p = 7: exponents 0, 1; local totients 1, 6.
• p = 13: exponents 0, 1; local totients 1, 12.

The necessary local conditions leave 96 combinations, with maximum candidate 32760. Predict which products of local totients equal the target. Local divisibility alone is insufficient.

Reveal enumeration

Temporary exploration, at most 96 combinations. The completeness proof below is essential: matching examples alone do not exclude a larger solution. No learning achievement is awarded by revealing the ledger.

Let the desired totient be a positive integer m. If the exact prime power pᵃ divides n, with a at least one, its local contribution pᵃ⁻¹(p − 1) is a factor of the product φ(n)=m. Therefore p − 1 divides m, so p is at most m + 1. For each such prime retain only positive exponents whose local contribution divides m; also allow exponent zero, whose contribution and power are both one. There are finitely many exponents because pᵃ⁻¹(p − 1) grows without bound.

Now choose one exponent for every allowed prime, multiply the prime powers to obtain n, and multiply their local contributions. Keep precisely the choices whose contribution product is m. Every solution appears by the necessary conditions just proved. Conversely, multiplicativity proves every retained choice is a solution. Unique factorization prevents duplicate integers. This is a complete finite argument, not a scan stopped at a convenient number.

Work the target 12, including rejected combinations

The allowed primes are 2, 3, 5, 7, 13. The exponent lists are respectively (0, 1, 2, 3), (0, 1, 2), (0, 1), (0, 1), (0, 1). There are 4·3·2·2·2=96 choices. The maximum candidate allowed by these necessary local conditions is 2³·3²·5·7·13=32760. This is a derived bound, although most candidates fail the final product test.

For example n=15 passes the local divisibility checks because 2 and 4 both divide 12, but their product 8 is not 12. The complete accepted list is 13, 21, 26, 28, 36, 42. Their prime-power products give 12, 2·6, 1·12, 2·6, 2·6, 1·2·6 respectively. The factor 2 to exponent one contributes one, so omitting it from candidate primes would incorrectly lose 26 and 42. At target one the empty product gives n=1 and the factor 2 gives n=2; these endpoints must both remain.

For an unfamiliar case, solve φ(n)=8 without first revealing the checker. Supply the prime list, exponent bounds, accepted products and a reason no larger integer was missed. Compare a complete proof with the weaker claim “these five examples work.”

Apply

A useful identity is Σ_(d|n)φ(d)=n. Partition k=1,…, n by gcd(k, n)=g. Set d=n/g and k=gu; then u ranges over units among 1,…, d. Thus the class has φ(d) elements, and summing over all gcd classes counts every k exactly once. This is a combinatorial proof, not an unexplained algebraic coincidence. More generally, divisor convolution is (f∗g)(n)=Σ_(d|n)f(d)g(n/d). If f and g are multiplicative, unique splitting of a divisor of coprime ab into a divisor of a and one of b proves their convolution is multiplicative too.

For a concrete divisor classification, take n=12. The integers k from one to twelve with gcd(k, 12)=4 are four and eight. Dividing these k values and the modulus by four gives the two units modulo three. More generally, the class with gcd(k, n)=g corresponds bijectively to units modulo n/g. Summing these disjoint classes proves the divisor-sum identity without assuming a formula for φ in advance. Check that the class g=n contributes the single integer n, corresponding to φ(1)=1. This endpoint convention is necessary for the total to equal n.

Continue

Prime-power formulas reduce many problems, but only after proving the required multiplicativity. Do not assume every function defined using divisors has that property. A written implementation should factor a small integer, generate divisors independently and compare the count and sum with the formulas. For large inputs, factorization cost remains part of the computation. Next, the Möbius function will invert divisor summation, turning cumulative arithmetic information back into its original terms.

Return to the number theory unit to choose a targeted retry. Continue with undo a divisor sum by controlled cancellation.