Difference between revisions of "2004 IMO Shortlist Problems/N2"
m (→Solution) |
|||
Line 16: | Line 16: | ||
== Solution == | == Solution == | ||
− | Let <math> | + | 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> | <center> | ||
− | <math> \psi (n) = \sum_{ | + | <math> \psi (n) = \sum_{k=1}^{n}(k,n) = \sum_{d \mid n} d \phi(n/d) </math>. |
</center> | </center> | ||
− | In other words, <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> | + | 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> | + | 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> | <center> | ||
<math> \psi(x) = \prod_{i=1}^k [(e_i+1)p_i^{e_i} - e_i\cdot p_i^{e_i}] </math>, | <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> | </center> | ||
− | From this we can see that <math> | + | 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> | + | 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 | '''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> | <center> <math> \prod_{i=1}^{k}\left(e_i \frac{p-1}{p} +1\right) = \frac{p}{q} </math> </center> | ||
− | and <math> | + | 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> | + | ''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> | + | 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}} | {{alternate solutions}} | ||
− | |||
== Resources == | == Resources == |
Latest revision as of 08:10, 29 August 2011
Problem
(Russia)
The function from the set
of positive integers to itself is defined by the equality
,
where denotes the greatest common divisor of
and
.
a) Prove that for every two relatively prime
.
b) Prove that for each the equation
has a solution.
c) Find all such that the equation
has a unique solution.
This was also
Solution
Let be a divisor of
. We note that for
,
if and only if
is relatively prime to
. It follows that each divisor
of
is found in the sum
exactly
times, where
is defined as the number of natural numbers less than or equal to
and relatively prime to
(the Euler Totient Function). It follows that
.
In other words, is the convolution of the identity function
and the
function. Since these are both multiplicative functions,
is also multiplicative, which is part (a) of the problem. For the next parts, we note that the equation
is equivalent to the equation
.
We now note that for a prime and a non-negative integer
,

Since is multiplicative, if
is the prime factorization of
, then
,
and
.
From this we can see that is always a solution to the equation
, which solves part (b). Let this solution to the equation be the canonical solution. However, we also note that if
is an odd postive integer, then
is another solution to the equation. In particular, if
has an odd prime factor
, then
is a solution distinct from the canonical solution. Thus if the only solution to the equation
is canonical, then
cannot have any odd divisors greater than 1, i.e.,
must be a power of 2.
We now claim that for , the equation has no non-canonical solutions.
Lemma. Let be odd primes,
be positive integers. If

and are relatively prime positive integers, then
is divisible by an odd prime.
Proof. We first note that , so
, or
. Thus
must be divisible by some prime. But since
,
divides a product of odd numbers, so it cannot be divisible by 2. Hence
is divisible by an odd prime. ∎
Now, suppose that for there exists some non-canonical solution
to the equation. Since
, the only value of
which is a power of 2 and is a solution is the canonical solution. Thus
, for some nonnegative integer
and some odd integer
. But by our lemma,
, for some relatively prime
and
such that
is odd. But since
is an integer and there are no factors in the denominator common to the odd prime which divides
,
must be divisible by an odd prime, a contradiction. Thus the canonical solution to the equation
is unique if and only if
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.