Difference between revisions of "2004 IMO Shortlist Problems/N2"

Latest revision as of 09:10, 29 August 2011

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

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

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

We now note that for a prime $p$ and a non-negative integer $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 $\psi$ is multiplicative, if $\prod_{i=1}^k p_i^{e_i}$ is the prime factorization of $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} + 1 \right)$ .

From this we can see that $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 $2r +1$ is an odd postive integer, then $x = 3^{3r}$ is another solution to the equation. In particular, if $a$ has an odd prime factor $2r+1 > 1$ , then $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 $a$ cannot have any odd divisors greater than 1, i.e., $a$ must be a power of 2.

We now claim that for $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 $p, q$ are relatively prime positive integers, then $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 $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}$ , $p$ divides a product of odd numbers, so it cannot be divisible by 2. Hence $p$ is divisible by an odd prime. ∎

Now, suppose that for $a = 2^k$ there exists some non-canonical solution $x_1$ to the equation. Since $\psi(2^j) = \frac{j}{2} + 1$ , the only value of $x$ which is a power of 2 and is a solution is the canonical solution. Thus $x_1 = 2^c \cdot n$ , for some nonnegative integer $c$ and some odd integer $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 $p$ and $q$ such that $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 $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 $\psi(x) = ax$ is unique if and only if $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

@@ Line 16: / Line 16: @@
 == Solution ==
-Let <math> \displaystyle d </math> be a divisor of <math> \displaystyle n </math>.  We note that for <math> \displaystyle k \leq n/d </math>, <math> \displaystyle (dk,n) = d </math> if and only if <math> \displaystyle k </math> is relatively prime to <math> \displaystyle n/d </math>.  It follows that each divisor <math> \displaystyle d </math> of <math> \displaystyle n </math> is found in the sum <math> \sum_{i=1}^{n}(k,n) </math> exactly <math> \displaystyle \phi(n/d )</math> times, where <math> \displaystyle \phi(m) </math> is defined as the number of natural numbers less than or equal to <math> \displaystyle m </math> and relatively prime to <math> \displaystyle m </math> (the [[Euler Totient Function]]).  It follows that
+Let <math>d </math> be a divisor of <math>n </math>.  We note that for <math>k \leq n/d </math>, <math>(dk,n) = d </math> if and only if <math>k </math> is relatively prime to <math>n/d </math>.  It follows that each divisor <math>d </math> of <math>n </math> is found in the sum <math> \sum_{i=1}^{n}(k,n) </math> exactly <math>\phi(n/d )</math> times, where <math>\phi(m) </math> is defined as the number of natural numbers less than or equal to <math>m </math> and relatively prime to <math>m </math> (the [[Euler Totient Function]]).  It follows that
 <center>
-<math> \psi (n) = \sum_{i=1}^{n}(k,n) = \sum_{d \mid n} d \phi(n/d) </math>.
+<math> \psi (n) = \sum_{k=1}^{n}(k,n) = \sum_{d \mid n} d \phi(n/d) </math>.
 </center>
-In other words, <math> \displaystyle \psi </math> is the [[Dirichlet convolution | convolution]] of the identity function <math> f: n \mapsto n </math> and the <math> \displaystyle \phi </math> function.  Since these are both [[multiplicative function]]s, <math> \displaystyle \psi </math> is also multiplicative, which is part (a) of the problem.  For the next parts, we note that the equation <math> \displaystyle \psi(x) = ax </math> is equivalent to the equation <math> \frac{\psi(x)}{x} = a </math>.
+In other words, <math>\psi </math> is the [[Dirichlet convolution | convolution]] of the identity function <math> f: n \mapsto n </math> and the <math>\phi </math> function.  Since these are both [[multiplicative function]]s, <math>\psi </math> is also multiplicative, which is part (a) of the problem.  For the next parts, we note that the equation <math>\psi(x) = ax </math> is equivalent to the equation <math> \frac{\psi(x)}{x} = a </math>.
-We now note that for a prime <math> \displaystyle p </math> and a non-negative integer <math> \displaystyle e </math>, <center><math> \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}) </math>. </center>
+We now note that for a prime <math>p </math> and a non-negative integer <math>e </math>, <center><math> \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}) </math>. </center>
-Since <math> \displaystyle \psi </math> is multiplicative, if <math> \prod_{i=1}^k p_i^{e_i} </math> is the prime factorization of <math> \displaystyle x </math>, then
+Since <math>\psi </math> is multiplicative, if <math> \prod_{i=1}^k p_i^{e_i} </math> is the prime factorization of <math>x </math>, then
 <center>
 <math> \psi(x) = \prod_{i=1}^k [(e_i+1)p_i^{e_i} - e_i\cdot p_i^{e_i}] </math>,
@@ Line 33: / Line 33: @@
 </center>
-From this we can see that <math> \displaystyle x = 2^{2(a-1)} </math> is always a solution to the equation <math> \frac{\psi(x)}{x} = a </math>, which solves part (b).  Let this solution to the equation be the ''canonical solution''.  However, we also note that if <math> \displaystyle 2r +1 </math> is an odd postive integer, then <math> \displaystyle x = 3^{3r} </math> is another solution to the equation.  In particular, if <math> \displaystyle a </math> has an odd prime factor <math> \displaystyle 2r+1 > 1 </math>, then <math> \displaystyle x = 2^{2[a/(2r+1) -1]} \cdot 3^{3r} </math> is a solution distinct from the canonical solution.  Thus if the only solution to the equation <math> \frac{\psi(x)}{x} = a </math> is canonical, then <math> \displaystyle a </math> cannot have any odd divisors greater than 1, i.e., <math> \displaystyle a </math> must be a power of 2.
+From this we can see that <math>x = 2^{2(a-1)} </math> is always a solution to the equation <math> \frac{\psi(x)}{x} = a </math>, which solves part (b).  Let this solution to the equation be the ''canonical solution''.  However, we also note that if <math>2r +1 </math> is an odd postive integer, then <math>x = 3^{3r} </math> is another solution to the equation.  In particular, if <math>a </math> has an odd prime factor <math>2r+1 > 1 </math>, then <math>x = 2^{2[a/(2r+1) -1]} \cdot 3^{3r} </math> is a solution distinct from the canonical solution.  Thus if the only solution to the equation <math> \frac{\psi(x)}{x} = a </math> is canonical, then <math>a </math> cannot have any odd divisors greater than 1, i.e., <math>a </math> must be a power of 2.
-We now claim that for <math> \displaystyle a = 2^k </math>, the equation has no non-canonical solutions.
+We now claim that for <math>a = 2^k </math>, the equation has no non-canonical solutions.
 '''Lemma.'''  Let <math> p_1, \ldots, p_k </math> be odd primes, <math> e_1, \ldots, e_k </math> be positive integers.  If
 <center> <math> \prod_{i=1}^{k}\left(e_i \frac{p-1}{p} +1\right) = \frac{p}{q} </math> </center>
-and <math> \displaystyle p, q </math> are relatively prime positive integers, then <math> \displaystyle p </math> is divisible by an odd prime.
+and <math>p, q </math> are relatively prime positive integers, then <math>p </math> is divisible by an odd prime.
-''Proof.''  We first note that <math> e_i \frac{p_i-1}{p_i} + 1 \ge \frac{p_i-1}{p_i} + 1 > 1 </math>, so <math> \frac{p}{q} = \prod \left( e_i \frac{p_i-1}{p_i} +1 \right) > 1 </math>, or <math> p>q\ge 1 </math>.  Thus <math> \displaystyle p </math> must be divisible by some prime.  But since <math> \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} </math>, <math> \displaystyle p </math> divides a product of odd numbers, so it cannot be divisible by 2.  Hence <math> \displaystyle p </math> is divisible by an odd prime.  {{Halmos}}
+''Proof.''  We first note that <math> e_i \frac{p_i-1}{p_i} + 1 \ge \frac{p_i-1}{p_i} + 1 > 1 </math>, so <math> \frac{p}{q} = \prod \left( e_i \frac{p_i-1}{p_i} +1 \right) > 1 </math>, or <math> p>q\ge 1 </math>.  Thus <math>p </math> must be divisible by some prime.  But since <math> \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} </math>, <math>p </math> divides a product of odd numbers, so it cannot be divisible by 2.  Hence <math>p </math> is divisible by an odd prime.  {{Halmos}}
-Now, suppose that for <math> \displaystyle a = 2^k </math> there exists some non-canonical solution <math> \displaystyle x_1 </math> to the equation.  Since <math> \psi(2^j) = \frac{j}{2} + 1 </math>, the only value of <math> \displaystyle x </math> which is a power of 2 and is a solution is the canonical solution. Thus <math> \displaystyle x_1 = 2^c \cdot n </math>, for some nonnegative integer <math> \displaystyle c </math> and some odd integer <math> \displaystyle n>1 </math>.  But by our lemma, <math> \frac{\psi(2^c\cdot n)}{2^c\cdot n} = \left(\frac{c+2}{2} \right) \cdot \frac{p}{q} </math>, for some relatively prime <math> \displaystyle p </math> and <math> \displaystyle q </math> such that <math> \displaystyle p </math> is odd.  But since <math> \frac{\psi(x_1)}{x_1} </math> is an integer and there are no factors in the denominator common to the odd prime which divides <math> \displaystyle p </math>, <math> \frac{\psi(x_1)}{x_1} = 2^k </math> must be divisible by an odd prime, a contradiction.  Thus the canonical solution to the equation <math> \displaystyle \psi(x) = ax </math> is unique if and only if <math> \displaystyle a </math> is a power of 2.  Q.E.D.
+Now, suppose that for <math>a = 2^k </math> there exists some non-canonical solution <math>x_1 </math> to the equation.  Since <math> \psi(2^j) = \frac{j}{2} + 1 </math>, the only value of <math>x </math> which is a power of 2 and is a solution is the canonical solution. Thus <math>x_1 = 2^c \cdot n </math>, for some nonnegative integer <math>c </math> and some odd integer <math>n>1 </math>.  But by our lemma, <math> \frac{\psi(2^c\cdot n)}{2^c\cdot n} = \left(\frac{c+2}{2} \right) \cdot \frac{p}{q} </math>, for some relatively prime <math>p </math> and <math>q </math> such that <math>p </math> is odd.  But since <math> \frac{\psi(x_1)}{x_1} </math> is an integer and there are no factors in the denominator common to the odd prime which divides <math>p </math>, <math> \frac{\psi(x_1)}{x_1} = 2^k </math> must be divisible by an odd prime, a contradiction.  Thus the canonical solution to the equation <math>\psi(x) = ax </math> is unique if and only if <math>a </math> is a power of 2.  Q.E.D.
 {{alternate solutions}}
 == Resources ==

Page

Toolbox

Search

Difference between revisions of "2004 IMO Shortlist Problems/N2"

Latest revision as of 09:10, 29 August 2011

Problem

Solution

Resources