Maths Olympiad Prep

Library / /2 of 71

Number theory Difficulty 4.0 AIME Find the answer United States

Problem:

Evaluate the functions ϕ(n)\phi(n), σ(n)\sigma(n), and τ(n)\tau(n) for n=12n=12, n=2007n=2007, and n=22007n=2^{2007}.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

For n=12=2231n=12=2^{2} \cdot 3^{1},
ϕ(12)=2(21)(31)=4,σ(12)=(1+2+4)(1+3)=28,τ(12)=(2+1)(1+1)=6 \phi(12)=2(2-1)(3-1)=4, \quad \sigma(12)=(1+2+4)(1+3)=28, \quad \tau(12)=(2+1)(1+1)=6

For n=2007=32223n=2007=3^{2} \cdot 223,
ϕ(2007)=3(31)(2231)=1332,σ(2007)=(1+3+9)(1+223)=2912,τ(2007)=(2+1)(1+1)=6 \phi(2007)=3(3-1)(223-1)=1332, \quad \sigma(2007)=(1+3+9)(1+223)=2912, \quad \tau(2007)=(2+1)(1+1)=6

For n=22007n=2^{2007},
ϕ(22007)=22006,σ(22007)=(1+2++22007)=220081,τ(22007)=2007+1=2008 \phi\left(2^{2007}\right)=2^{2006}, \quad \sigma\left(2^{2007}\right)=\left(1+2+\cdots+2^{2007}\right)=2^{2008}-1, \quad \tau\left(2^{2007}\right)=2007+1=2008

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.