Maths Olympiad Prep

Library / /43 of 520

Number theory Difficulty 5.4 AIME, harder Find the answer

Example 4 (Euler's φ\varphi function calculation formula)
Euler's φ\varphi function value at nn, φ(n)\varphi(n), is defined as the number of natural numbers that are coprime to nn in the set {1,2,,n}\{1,2, \cdots, n\}. Suppose nn has the standard factorization
n=p1z1psαs,n=p_{1}^{z_{1}} \cdots p_{s}^{\alpha_{s}},

where p1,,psp_{1}, \cdots, p_{s} are distinct prime numbers, αj1,1js,s1\alpha_{j} \geqslant 1,1 \leqslant j \leqslant s, s \geqslant 1.
Let PiP_{i} represent the property that a natural number in the set S={1,2,,n}S=\{1,2, \cdots, n\} is divisible by PiP_{i} (i=1,s)(i=1, \cdots s). The subset of SS with property PiP_{i} is denoted as AiA_{i}. Thus, we have
φ(n)=Aˉ1Aˉs=SiAi+i,jAiAj++(1)sA1As=ninpi+i<jnpipj++(1)snp1ps=n(11p1)(11ps)=npn(11p)\begin{aligned} \varphi(n)= & \left|\bar{A}_{1} \cap \cdots \cap \bar{A}_{s}\right|=|S|-\sum_{i}\left|A_{i}\right|+\sum_{i, j}\left|A_{i} \cap A_{j}\right|-+\cdots \\ & +(-1)^{s}\left|A_{1} \cap \cdots \cap A_{s}\right| \\ = & n-\sum_{i} \frac{n}{p_{i}}+\sum_{i<j} \frac{n}{p_{i} p_{j}}-+\cdots+(-1)^{s} \frac{n}{p_{1} \cdots p_{s}} \\ = & n\left(1-\frac{1}{p_{1}}\right) \cdots\left(1-\frac{1}{p_{s}}\right)=n \prod_{p \mid n}\left(1-\frac{1}{p}\right) \end{aligned}

Example: From 60=223560=2^{2} \cdot 3 \cdot 5, we get
φ(60)=60(112)(113)(115)=16.\varphi(60)=60\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)=16 .

A number or a short expression. Spacing and $ signs are ignored.

Solution

None

Translate the text above into English, please retain the original text's line breaks and format, and output the translation result directly.

Note: The provided instruction is a meta-instruction and not part of the text to be translated. Since the text to be translated is "None", the translation is also "None". Here is the formatted output as requested:

None

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.