Maths Olympiad Prep

Library / Annual Harvard-MIT Mathematics Tournament /1 of 72

Annual Harvard-MIT Mathematics Tournament

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=22⋅31n=12=2^{2} \cdot 3^{1},
ϕ(12)=2(2−1)(3−1)=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=32⋅223n=2007=3^{2} \cdot 223,
ϕ(2007)=3(3−1)(223−1)=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)=22008−1,τ(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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.