AoPSWiki

Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!

Personal tools

Search

Toolbox

2004 IMO Shortlist Problems/N2

From AoPSWiki

Problem

(Russia) The function $\displaystyle \psi$ from the set $\mathbf{N}$ of positive integers to itself is defined by the equality

$\psi(n) = \sum_{k=1}^{n}(k,n), \qquad n \in \mathbf{N}$ ,

where $\displaystyle (k,n)$ denotes the greatest common divisor of $\displaystyle k$ and $\displaystyle n$ .

a) Prove that $\displaystyle \psi(mn) = \psi(m)\psi(n)$ for every two relatively prime $m,n \in \mathbf{N}$ .
b) Prove that for each $a \in \mathbf{N}$ the equation $\displaystyle \psi(x) = ax$ has a solution.
c) Find all $a \in \mathbf{N}$ such that the equation $\displaystyle \psi(x) = ax$ has a unique solution.

This was also

Solution

Let $\displaystyle d$ be a divisor of $\displaystyle n$ . We note that for $\displaystyle k \leq n/d$ , $\displaystyle (dk,n) = d$ if and only if $\displaystyle k$ is relatively prime to $\displaystyle n/d$ . It follows that each divisor $\displaystyle d$ of $\displaystyle n$ is found in the sum $\sum_{i=1}^{n}(k,n)$ exactly $\displaystyle \phi(n/d )$ times, where $\displaystyle \phi(m)$ is defined as the number of natural numbers less than or equal to $\displaystyle m$ and relatively prime to $\displaystyle m$ (the Euler Totient Function). It follows that

$\psi (n) = \sum_{i=1}^{n}(k,n) = \sum_{d \mid n} d \phi(n/d)$ .

In other words, $\displaystyle \psi$ is the convolution of the identity function $f: n \mapsto n$ and the $\displaystyle \phi$ function. Since these are both multiplicative functions, $\displaystyle \psi$ is also multiplicative, which is part (a) of the problem. For the next parts, we note that the equation $\displaystyle \psi(x) = ax$ is equivalent to the equation $\frac{\psi(x)}{x} = a$ .

We now note that for a prime $\displaystyle p$ and a non-negative integer $\displaystyle e$ , $\psi(p^k) = \sum_{i=0}^{e}p^i \cdot \phi(p^{e-i}) = p^e + \sum_{i=0}^{e-1}p^i(p^{e-i} - p^{e-i-1}) = p^e + e(p^e - p^{e-1})$ .

Since $\displaystyle \psi$ is multiplicative, if $\prod_{i=1}^k p_i^{e_i}$ is the prime factorization of $\displaystyle x$ , then

$\psi(x) = \prod_{i=1}^k [(e_i+1)p_i^{e_i} - e_i\cdot p_i^{e_i}]$ ,

and

$\frac{\psi(x)}{x} = \frac{\prod [(e_i+1)p_i^{e_i} - e_i \cdot p_i^{e_i}]}{\prod p_i^{e_i}} = \prod \left(e_i \frac{p_i-1}{p_i...$ .

From this we can see that $\displaystyle x = 2^{2(a-1)}$ is always a solution to the equation $\frac{\psi(x)}{x} = a$ , which solves part (b). Let this solution to the equation be the canonical solution. However, we also note that if $\displaystyle 2r +1$ is an odd postive integer, then $\displaystyle x = 3^{3r}$ is another solution to the equation. In particular, if $\displaystyle a$ has an odd prime factor $\displaystyle 2r+1 > 1$ , then $\displaystyle x = 2^{2[a/(2r+1) -1]} \cdot 3^{3r}$ is a solution distinct from the canonical solution. Thus if the only solution to the equation $\frac{\psi(x)}{x} = a$ is canonical, then $\displaystyle a$ cannot have any odd divisors greater than 1, i.e., $\displaystyle a$ must be a power of 2.

We now claim that for $\displaystyle a = 2^k$ , the equation has no non-canonical solutions.

Lemma. Let $p_1, \ldots, p_k$ be odd primes, $e_1, \ldots, e_k$ be positive integers. If

$\prod_{i=1}^{k}\left(e_i \frac{p-1}{p} +1\right) = \frac{p}{q}$

and $\displaystyle p, q$ are relatively prime positive integers, then $\displaystyle p$ is divisible by an odd prime.

Proof. We first note that $e_i \frac{p_i-1}{p_i} + 1 \ge \frac{p_i-1}{p_i} + 1 > 1$ , so $\frac{p}{q} = \prod \left( e_i \frac{p_i-1}{p_i} +1 \right) > 1$ , or $p>q\ge 1$ . Thus $\displaystyle p$ must be divisible by some prime. But since $\frac{p}{q} = \prod \left( e_i \frac{p_i-1}{p_i} + 1 \right) = \frac{ \prod [e_i(p_i-1) + p_i] }{\prod p_i}$ , $\displaystyle p$ divides a product of odd numbers, so it cannot be divisible by 2. Hence $\displaystyle p$ is divisible by an odd prime. ∎

Now, suppose that for $\displaystyle a = 2^k$ there exists some non-canonical solution $\displaystyle x_1$ to the equation. Since $\psi(2^j) = \frac{j}{2} + 1$ , the only value of $\displaystyle x$ which is a power of 2 and is a solution is the canonical solution. Thus $\displaystyle x_1 = 2^c \cdot n$ , for some nonnegative integer $\displaystyle c$ and some odd integer $\displaystyle n>1$ . But by our lemma, $\frac{\psi(2^c\cdot n)}{2^c\cdot n} = \left(\frac{c+2}{2} \right) \cdot \frac{p}{q}$ , for some relatively prime $\displaystyle p$ and $\displaystyle q$ such that $\displaystyle p$ is odd. But since $\frac{\psi(x_1)}{x_1}$ is an integer and there are no factors in the denominator common to the odd prime which divides $\displaystyle p$ , $\frac{\psi(x_1)}{x_1} = 2^k$ must be divisible by an odd prime, a contradiction. Thus the canonical solution to the equation $\displaystyle \psi(x) = ax$ is unique if and only if $\displaystyle a$ is a power of 2. Q.E.D.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/2004_IMO_Shortlist_Problems/N2"

Category: Olympiad Number Theory Problems

Want to learn how to tackle those tough AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us