Maths Olympiad Prep

Library / /742 of 860

Number theory Difficulty 5.5 AIME, harder Find the answer

Let nn be the product of the first 10 primes, and let S=xynφ(x)yS=\sum_{x y \mid n} \varphi(x) \cdot y where φ(x)\varphi(x) denotes the number of positive integers less than or equal to xx that are relatively prime to xx, and the sum is taken over ordered pairs (x,y)(x, y) of positive integers for which xyx y divides nn. Compute Sn\frac{S}{n}.

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

Solution

Solution 1: We see that, for any positive integer nn, S=xynφ(x)y=xnφ(x)(ynxy)=xnφ(x)σ(nx)S=\sum_{x y \mid n} \varphi(x) \cdot y=\sum_{x \mid n} \varphi(x)\left(\sum_{y \left\lvert\, \frac{n}{x}\right.} y\right)=\sum_{x \mid n} \varphi(x) \sigma\left(\frac{n}{x}\right) Since φ\varphi and σ\sigma are both weakly multiplicative (if xx and yy are relatively prime, then φ(xy)=φ(x)φ(y)\varphi(x y)=\varphi(x) \varphi(y) and σ(xy)=σ(x)σ(y))\sigma(x y)=\sigma(x) \sigma(y)), we may break this up as p(φ(p)+σ(p))\prod_{p}(\varphi(p)+\sigma(p)) where the product is over all primes that divide nn. This is simply 210n2^{10} n, giving an answer of 210=10242^{10}=1024. Solution 2: We recall that dnφ(d)=n\sum_{d \mid n} \varphi(d)=n So, we may break up the sum as S=xynφ(x)y=ynyxnyφ(x)=yny(ny)S=\sum_{x y \mid n} \varphi(x) \cdot y=\sum_{y \mid n} y \sum_{x \left\lvert\, \frac{n}{y}\right.} \varphi(x)=\sum_{y \mid n} y\left(\frac{n}{y}\right) so SS is simply nn times the number of divisors of nn. This number is 210=10242^{10}=1024. Solution 3: When constructing a term in the sum, for each prime pp dividing nn, we can choose to include pp in xx, or in yy, or in neither. This gives a factor of p1,pp-1, p, or 1, respectively. Thus we can factor the sum as S=pn(p1+p+1)=pn2p=210nS=\prod_{p \mid n}(p-1+p+1)=\prod_{p \mid n} 2 p=2^{10} n So the answer is 1024.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.