$2008$ ISL N$5$

For discussing Olympiad Level Number Theory problems
rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm
$2008$ ISL N$5$

Unread post by rah4927 » Tue Jan 31, 2017 8:50 pm

For every $ n\in\mathbb{N}$ let $ d(n)$ denote the number of (positive) divisors of $ n$. Find all functions $ f: \mathbb{N}\to\mathbb{N}$ with the following properties:
$ d\left(f(x)\right) = x$ for all $ x\in\mathbb{N}$.
$ f(xy)$ divides $ (x - 1)y^{xy - 1}f(x)$ for all $ x$, $ y\in\mathbb{N}$.

Source : $2008$ ISL N$5$

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: $2008$ ISL N$5$

Unread post by Thanic Nur Samin » Wed Feb 01, 2017 6:49 pm

Beautiful problem!!!

Lemma 1: $f(2)=2, f(3)=3^2$.

Proof: $d(f(2))=2$, so $f(2)=p$ where $p$ is a prime. Also, $d(f(3))=3$, so $f(3)=q^2$ where $q$ is a prime.

Now, $f(6)=f(2\times 3)|3^5p$

$f(6)=f(3\times 2)|2\times 2^5\times q^2$.

So, the prime divisors of $f(6)$ belong to the set $\{3,p\}$ and also to the set $\{2,q\}$. This implies $p=2$ and $q=3$, from which the lemma follows.

Lemma 2: If $p$ is a prime, then $f(p)=p^{p-1}$.

Proof: If $p=2$, then by lemma 1 we are done. So we can assume that $p$ is an odd prime.

$d(f(p))=p$, and since $d$ is a multiplicative function, we get that $f(p)=q^{p-1}$.

Now, $f(2p)|p^{2p-1}\times 2$ and $f(2p)|(p-1)2^{2p-1}q^{p-1}$

So, prime divisors of $f(2p)$ belong to the sets $\{2,p\}$ and the set of prime numbers that divide $p-1$ and $2$ and $q$. So since $p$ can't be equal to $2$ and neither can it divide $p-1$. So $p=q$ and the lemma follows.

Lemma 3: If $p$ is a prime and $k$ is a positive integer, then $f(p^k)=p^{p^k-1}$

Proof: We prove by induction on $k$. For $k=1$ this follows from lemma 2.

Now, lets assume that its true for $k-1$. Now, if a prime $q$ not equal to $p$ divides $f(p^k)$, then,

$d(f(p^k))=p^k$, so $v_q(f(p^k))\ge p-1$.

$q^{p-1}|f(p^k)=f(p\times p^{k-1})|(p-1)p^s\times p^t$ for some $s$ and $t$. So we get that $q^{p-1}|p-1$. Clearly impossible for size reasons. So $f(p^k)=p^n$, and from $d(f(p^k))=p^k$ the lemma easily follows by induction.

Lemma 4: For a prime $q$, $q|f(N)\Rightarrow q|N$.

Proof: Let the smallest prime divisor of $N$ be $p$, and $q$ is a prime factor of $f(N)$. Let $e$ be the largest number such that $q^e|f(N)$

Since $d(f(N))=N$, none of the powers of prime divisors of $f(N)$ can be less than $p-1$. So $e\ge p-1$.

Again, $f(N)|(p-1)(\dfrac{N}{p})^{N-1}f(p)$ implies that $q|N$.


Now we prove the main part, that is $\displaystyle f(\prod_{i=1}^k p_i^{a_i})=\prod_{i=1}^k (p_i^{p_i^{a_i}-1})$, Where all $p_i$'s are primes. Let $\displaystyle N=\prod_{i=1}^k p_i^{a_i}$. WLOG $p_1<p_2\ldots <p_k$.

We know that $f(N)$ has the same set of prime factors of $N$. So we can write $\displaystyle f(N)=\prod_{i=1}^k p_i^{b_i}$. However, $\displaystyle \prod_{i=1}^k (b_i+1)=\prod_{i=1}^k p_i^{a_i}$.

Also, $f(N)|(p_i^{a_i}-1)(N/p_i^{a_i})^{N-1}p_i^{p^{a_i}-1}$, and so the power of $p_i$ in the prime factorization of $f(N)$ would be at most $p_i^{a_i}-1$, and from $\displaystyle \prod_{i=1}^k (b_i+1)=\prod_{i=1}^k p_i^{a_i}$ we get that the equality case must occur. So we have proved that the function can't be anything but $\displaystyle f(\prod_{i=1}^k p_i^{a_i})=\prod_{i=1}^k (p_i^{p_i^{a_i}-1})$, and testing yields that it works, so we are done.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: $2008$ ISL N$5$

Unread post by rah4927 » Wed Feb 01, 2017 7:32 pm

A way to do lemma $4$ (perhaps the same as above).

$x|a$ and $x|b$ imply $x|(a,b)$. Now use condition $2$ by fixing $xy=n$ and letting $x$ be a prime divisor of $xy=n$. Use the gcd lemma mentioned before to see that you are left with an ugly $(p_1-1,p_2-1,\cdots)$. WLOG let $p_1$ be the smallest prime. Then if the gcd is divisible by a prime $L$, then its power must be at least $p-1$ to satisfy condition $1$, which is too large to divide any of the $p_i-1$. We are done.

Post Reply