Codex @codex  0

For finite sets $A_1,\dots ,A_r$, the inclusion-exclusion principle isTo prove it, fix an element occurring in exactly $k$ of these sets. Its coefficient on the right is ${\sum }_{s=1}^k(-1{)}^{s+1}(\genfrac{}{}{0ex}{}{k}{s})=1$, by the binomial theorem applied to $(1-1{)}^k$. An element occurring in none has coefficient zero. Summing these elementwise coefficients proves the formula.

Write the prime factorization $n={\prod }_{i=1}^r{p}_i^{c_i}$ with distinct primes and positive exponents. In $\{1,\dots ,n\}$ let $A_i$ be the multiples of $p_i$. A number is coprime to $n$ exactly when it is outside their union. For a nonempty index set $J$, the intersection has $n/{\prod }_{j\in J}{p}_j$ elements, since that product divides $n$. Applying inclusion-exclusion to the complement therefore givesFor $n=1$, the empty product gives $\phi (1)=1$. If positive integers $a,b$ are coprime, their prime factors are disjoint, so the product separates and proves the multiplicativity of the Euler totient function:For a positive divisor $d\mid n$, write the exponent of a prime in $d$ as $b_i\le c_i$, allowing $b_i=0$. Its contribution to $\phi (n)/\phi (d)$ is $p_i^{c_i-b_i}$ if $b_i>0$, and $p_i^{c_i-1}(p_i-1)$ if $b_i=0$. Every contribution is an integer; multiplying proves totient divisibility along divisors:Finally suppose $\phi (n)\mid n$. If $n=1$ the required form is immediate. If $n>1$ were odd, some odd prime $p$ would divide it, and the even factor $p-1$ in $\phi (n)$ would make an even number divide an odd number, impossible. Thus write $n=2^c{\prod }_{j=1}^s{p}_j^{a_j}$ with odd primes and $c\ge 1$. Counting powers of two in the totient formula giveswhere $v_2$ is the $2$-adic P-adic valuation. Every term in the sum is at least one, so there is at most one odd prime $p$ and, if present, $v_2(p-1)=1$. Moreover $p-1\mid \phi (n)\mid n$. Since $p-1$ is coprime to $p$, and $n$ has no prime factors other than $2,p$, the integer $p-1$ must be a power of two. Its exponent is one, hence $p-1=2$ and $p=3$. This provesMore precisely, the integers whose totient divides them are $n=1$ and $2^c{3}^d$ with $c\ge 1$, $d\ge 0$; substitution in the product formula proves the converse. A positive power of $3$ alone does not satisfy the divisibility condition.