function
number theory
IMO Shortlist
modular arithmetic
divisor
functional equation

Everyone who has spent a few hours(minutes) thinking about the problem would have figured out that $ f(1) \equal{} 1, f(p^a) \equal{} p^{p^a \minus{} 1}$ where $ p$ is a prime number. In any case I'll prove these two facts at the end. Using the above two facts and the conditions given in the problem, we will prove that
$ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) \equal{} f(p_1^{a_1})f(p_2^{a_2})...f(p_k^{a_k})$ where $ p_i$ is prime for $ 1 \leq i \leq k$

We write $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) \equal{} f(p_1\cdot p_1^{a_1 \minus{} 1}p_2^{a_2}...p_k^{a_k})$
Using the second condition given in the problem,(i.e)  $ f(xy)$ divides $ (x \minus{} 1)y^{xy \minus{} 1}f(x) \;\; \forall x, y\in\mathbb{N}$, we get the following
$ f(p_1\cdot p_1^{a_1 \minus{} 1}p_2^{a_2}...p_k^{a_k})\;|\; (p_1 \minus{} 1)(p_1^{a_1 \minus{} 1}p_2^{a_2}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} \minus{} 1}f(p_1)$
$ \Rightarrow f(p_1\cdot p_1^{a_1 \minus{} 1}p_2^{a_2}...p_k^{a_k})\;|\; (p_1 \minus{} 1)(p_1^{a_1 \minus{} 1}p_2^{a_2}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} \minus{} 1}p_1^{p_1 \minus{} 1}$ (using $ f(p_1) \equal{} p_1^{p_1 \minus{} 1}$).

We repeat this for every $ p_i$ and we get that $ \forall i\in \mathbb{N}$ such that  $ 1\leq i \leq k$,

$ f(p_i\cdot p_1^{a_1}p_2^{a_2}...p_i^{a_i \minus{} 1}...p_k^{a_k})\;|\; (p_i \minus{} 1)(p_1^{a_1}p_2^{a_2}...p_i^{a_i \minus{} 1}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} \minus{} 1}p_i^{p_i \minus{} 1}$

The above observations imply that

$ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) \equal{} q_1^{c_1}q_2^{c_2}...q_m^{c_m}\cdot p_1^{x_1}p_2^{x_2}...p_k^{x_k}$
where $ q_i$ is prime for $ 1 \leq i \leq m$ and $ q_1^{c_1}q_2^{c_2}...q_m^{c_m} \;|\; (p_i \minus{} 1) \;\;\forall i \in \mathbb{N}$, such that  $ 1\leq i \leq k$.

We note that the number of divisors of $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k})$ is $ (c_1 \plus{} 1)(c_2 \plus{} 1)...(c_m \plus{} 1)(x_1 \plus{} 1)(x_2 \plus{} 1)...(x_k \plus{} 1)$.

The number of divisors of $ f(x)$, $ d\left(f(x)\right) \equal{} x \;\;\forall x\in\mathbb{N}$. This when applied to  $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k})$, gives us the following equation

$ p_1^{a_1}p_2^{a_2}...p_k^{a_k} \equal{} (c_1 \plus{} 1)(c_2 \plus{} 1)...(c_m \plus{} 1)(x_1 \plus{} 1)(x_2 \plus{} 1)...(x_k \plus{} 1)$

Since $ (c_1 \plus{} 1)\;|\;p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, there exists an $ i$ such that $ c_1 \equiv \minus{} 1 (mod \;p_i) \Rightarrow c_1 \geq p_i \minus{} 1 \Rightarrow q_1^{c_1} \geq q_1^{p_i \minus{} 1} \geq 2^{p_i \minus{} 1} > p_i \minus{} 1$.
We know that
$ q_1^{c_1}q_2^{c_2}...q_m^{c_m} \;|\; (p_i \minus{} 1) \Rightarrow q_1^{c_1}q_2^{c_2}...q_m^{c_m} \leq p_i \minus{} 1 \Rightarrow q_1^{c_1} \leq p_i \minus{} 1$. But we established above that $ q_1^{c_1} > p_i \minus{} 1$.

Hence, our assumption that $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) \equal{} q_1^{c_1}q_2^{c_2}...q_m^{c_m}\cdot p_1^{x_1}p_2^{x_2}...p_k^{x_k}$ is incorrect.

Therefore, $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) \equal{} p_1^{x_1}p_2^{x_2}...p_k^{x_k}$

We would again have to use condition (ii) from the problem.

This time we write $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) \equal{} f(p_1^{a_1}\cdot p_2^{a_2}...p_k^{a_k})$
Using condition (ii), we get the following
$ f(p_1^{a_1}\cdot p_2^{a_2}...p_k^{a_k})\;|\; (p_1^{a_1 \minus{} 1} \minus{} 1)(p_2^{a_2}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} \minus{} 1}f(p_1^{a_1})$

$ \Rightarrow f(p_1^{a_1}\cdot p_2^{a_2}...p_k^{a_k})\;|\; (p_1^{a_1} \minus{} 1)(p_2^{a_2}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} \minus{} 1}p_1^{p_1^{a_1} \minus{} 1}$ (using $ f(p_1^{a_1}) \equal{} p_1^{p_1^{a_1} \minus{} 1}$).

$ \Rightarrow$ the power of $ p_1$ in $ f(p_1^{a_1}\cdot p_2^{a_2}...p_k^{a_k})$ is $ x_1 \leq p_1^{a_1} \minus{} 1$

We repeat this for every $ p_i$ and we get that $ \forall i\in \mathbb{N}$ such that  $ 1\leq i \leq k$,

$ f(p_i^{a_i}\cdot p_1^{a_1}...p_{i \minus{} 1}^{a_{i \minus{} 1}}p_{i \plus{} 1}^{a_{i \plus{} 1}}...p_k^{a_k})\;|\; (p_i^{a_i} \minus{} 1)(p_1^{a_1}...p_{i \minus{} 1}^{a_{i \minus{} 1}}p_{i \plus{} 1}^{a_{i \plus{} 1}}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} \minus{} 1}p_i^{p_i^{a_i} \minus{} 1}$

$ \Rightarrow$ the power of $ p_i$ in $ f(p_1^{a_1}\cdot p_2^{a_2}...p_k^{a_k})$ is $ x_i \leq p_i^{a_i} \minus{} 1$

The above observations imply that

$ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) \equal{} p_1^{x_1}p_2^{x_2}...p_k^{x_k}$ where $ x_i \leq p_i^{a_i} \minus{} 1$ for $ 1 \leq i \leq k$.

From condition(i) in the problem, we have that $ p_1^{a_1}p_2^{a_2}...p_k^{a_k} \equal{} (x_1 \plus{} 1)(x_2 \plus{} 1)...(x_k \plus{} 1) \leq p_1^{a_1}p_2^{a_2}...p_k^{a_k}\;\; (\because x_i \leq p_i^{a_i} \minus{} 1)$.

Hence, $ x_i \equal{} p_i^{a_i} \minus{} 1\;\; \forall i \in \mathbb{N}$ such that $ 1\leq i \leq k$.

Therefore, $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) \equal{} f(p_1^{a_1})f(p_2^{a_2})...f(p_k^{a_k})$ where $ p_i$ is prime for $ 1 \leq i \leq k$

Now it remains to show that
(i) $ f(1) \equal{} 1$ and
(ii) $ f(p^a) \equal{} p^{p^a \minus{} 1}$.

Since $ d(f(1)) \equal{} 1$, we have $ f(1) \equal{} 1$.
We establish $ f(p^a) \equal{} p^{p^a \minus{} 1}$, by proving the following
(a) $ f(2) \equal{} 2$
(b) $ f(p) \equal{} p^{p \minus{} 1}$ for all odd prime $ p$
(c) for $ a \geq 2$, $ f(p^a)$ has to be a power of $ p$ (i.e.) $ f(p^a) \equal{} p^{x}$.
Statement (c) along with $ d(f(p^a)) \equal{} p^a \Rightarrow x \plus{} 1 \equal{} p^{a} \Rightarrow x \equal{} p^{a} \minus{} 1 \Rightarrow f(p^a) \equal{} p^{p^{a} \minus{} 1}$.

Hence, it is enough to establish (a),(b) and (c).

Proof of (a):

As $ d(f(2)) \equal{} 2$, $ f(2) \equal{} p$ where $ p$ is a prime.

Suppose $ p$ is an odd prime.
$ f(2\cdot p)\; |\; p^{2p \minus{} 1}f(2) \equal{} p^{2p} \Rightarrow f(2p) \equal{} p^{y}$
Since $ d(f(2p)) \equal{} 2p$, we have $ f(2p) \equal{} p^{2p \minus{} 1}$.
$ f(p\cdot 2)\; |\; (p \minus{} 1) 2^{2p \minus{} 1}f(p) \Rightarrow p^{2p \minus{} 1}\;|\; (p \minus{} 1) 2^{2p \minus{} 1}f(p) \Rightarrow p^{2p \minus{} 1}\;|\; f(p) \Rightarrow f(p) \equal{} p^{z}$ where $ z \geq 2p \minus{} 1$. This implies $ d(f(p)) \geq 2p$. But $ d(f(p)) \equal{} p$ This is a contradiction.

Hence, $ f(2)$ cannot be an odd prime. Therefore, $ f(2) \equal{} 2$.

Proof of (b):
Suppose $ p$  is an odd prime. Since $ d(f(p)) \equal{} p$, $ f(p) \equal{} q^{p \minus{} 1}$ for some prime $ q$. In other words, $ f(p)$ has exactly one prime factor. Now if we could show that $ p \;|\; f(p)$, then it would follow that $ f(p) \equal{} p^{p \minus{} 1}$.
$ f(2\cdot p)\; |\; p^{2p \minus{} 1}f(2) \equal{} 2p^{2p \minus{} 1} \Rightarrow f(2p) \equal{} 2^{x}p^{y}$ where $ x \leq 1, y \geq 0$.
Since $ d(f(2p)) \equal{} 2p$, we have $ (x \plus{} 1)(y \plus{} 1) \equal{} 2p \Rightarrow y \geq p \minus{} 1$.
$ f(p\cdot 2)\; |\; (p \minus{} 1) 2^{2p \minus{} 1}f(p) \Rightarrow 2^{x}p^{y}\;|\; (p \minus{} 1) 2^{2p \minus{} 1}f(p) \Rightarrow p^{y}\;|\; f(p) \Rightarrow f(p) \equal{} p^{p \minus{} 1}$.

Proof of (c):

Let $ k \geq 1$
We write $ f(p^{k \plus{} 1}) \equal{} f(p\cdot p^{k}) \; |\; (p \minus{} 1)(p^k)^{(p^{k \plus{} 1} \minus{} 1)}f(p) \equal{} (p \minus{} 1)(p^k)^{(p^{k \plus{} 1} \minus{} 1)}p^{p \minus{} 1}$
$ \Rightarrow f(p^{k \plus{} 1}) \equal{} q_1^{c_1}q_2^{c_2}..q_m^{c_m}p^{x}$ where $ q_i$ is prime for $ 1 \leq i \leq m$ and $ q_1^{c_1}q_2^{c_2}...q_m^{c_m} \;|\; (p \minus{} 1)$.

We note that the number of divisors of $ f(p^{k \plus{} 1})$ is $ (c_1 \plus{} 1)(c_2 \plus{} 1)...(c_m \plus{} 1)(x \plus{} 1)$.

The number of divisors of $ f(x)$, $ d\left(f(x)\right) \equal{} x \;\;\forall x\in\mathbb{N}$. This when applied to  $ f(p^{k \plus{} 1})$, gives us the following equation

$ p^{k \plus{} 1} \equal{} (c_1 \plus{} 1)(c_2 \plus{} 1)...(c_m \plus{} 1)(x \plus{} 1)$

Since $ (c_1 \plus{} 1)\;|\;p^{k \plus{} 1}$, $ c_1 \equiv \minus{} 1 (mod \;p) \Rightarrow c_1 \geq p \minus{} 1 \Rightarrow q_1^{c_1} \geq q_1^{p \minus{} 1} \geq 2^{p \minus{} 1} > p \minus{} 1$.
We know that
$ q_1^{c_1}q_2^{c_2}...q_m^{c_m} \;|\; (p \minus{} 1) \Rightarrow q_1^{c_1}q_2^{c_2}...q_m^{c_m} \leq p \minus{} 1 \Rightarrow q_1^{c_1} \leq p \minus{} 1$. But we established above that $ q_1^{c_1} > p \minus{} 1$.

Hence, our assumption that $ f(p^{k \plus{} 1}) \equal{} q_1^{c_1}q_2^{c_2}...q_m^{c_m} p^{x}$ is incorrect.

Therefore, $ f(p^{k \plus{} 1}) \equal{} p^{x}$.

We have proven (a),(b) and (c). Hence, $ f(p^a) \equal{} p^{p^a \minus{} 1}$.

Therefore, the function that satisfies the conditions in the problem is the following:
(i)$ f(1) \equal{} 1$,(ii) $ f(p^{a}) \equal{} p^{p^a \minus{} 1 }$ and (iii)  $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) \equal{} f(p_1^{a_1})f(p_2^{a_2})...f(p_k^{a_k})$ where $ p_i$ is prime for $ 1 \leq i \leq k$.

Step 1:$ f(1)\equal{}1,f(2^a)\equal{}2^{2^a\minus{}1}$
Step 2:$ f(2p^a)\equal{}2p^{p^a\minus{}1},f(p^a)\equal{}p^{p^a\minus{}1}$
Step 3:the set of prime divisors of $ f(x)$ are containted in the set of prime divisors in $ x$
Step 4:$ f(p_1^{a_1}...p_k^{a_k})\equal{}p_1^{p^{a_1}\minus{}1}...p_k^{p^{a_k}\minus{}1}$
And I will post the full solution below(very sorry for being written in Chinese,I am glad to explain if anyone has questions) :)

I am grateful if anyone can point out my mistakes or flaws :)

Hi Hxy09,

I was reading through your solution and realized that our solutions are very similar.  On page 2 of your solution after the proof of $ f(p^{\alpha}) \equal{} p^{p^{\alpha}\minus{}1}$, I couldn't follow the arguments as you had written something in Chinese. Could you translate your solution into english from that point onwards till "....$ \exists \alpha \in \mathbb{N}_0 s.t. f(x) | x^{\alpha} \therefore (f(x),x\minus{}1) \equal{} 1$".

[quote="nicetry007"]Hi Hxy09,

I was reading through your solution and realized that our solutions are very similar.  On page 2 of your solution after the proof of $ f(p^{\alpha}) \equal{} p^{p^{\alpha} \minus{} 1}$, I couldn't follow the arguments as you had written something in Chinese. Could you translate your solution into english from that point onwards till "....$ \exists \alpha \in \mathbb{N}_0 s.t. f(x) | x^{\alpha} \therefore (f(x),x \minus{} 1) \equal{} 1$".[/quote]

Ok,here we go:

In page 2,we proved the set of prime divisors of $ f(x)$ are containted in the set of prime divisors of $ x$     ...(*)

Firstly we pick out the smallest prime divisor of $ x$.and replaced $ x$ with $ py$(it doesn't matter whether $ y$ is coprime with $ p$)

Noticed that $ f(p)\equal{}p^{p\minus{}1}$    $ f(py)|(p\minus{}1)y^{py\minus{}1}p^{p\minus{}1}$

If (*) is not true,denote by $ q$   $ q^ \beta \parallel{}f(py)$ and $ gcd(q,py)\equal{}1$   $ \beta \ge 1$

implies that $ q^{\beta}|p\minus{}1$,but $ d(f(py))\equal{}py$,$ \beta \plus{}1|py$

$ p$ is the [b]smallest[/b] prime divisor of $ x$

So $ \beta \plus{}1 \ge p$

Then $ p\minus{}1 \ge q^{\beta} \ge q^{p\minus{}1} \ge 2^{p\minus{}1}$ This is absurd!

Then the conclusion is true :)

Very sorry for some typoes in the picture(directly from my notebook) :blush:

Hi Hxy09

Thanks for clarifying it. I sort of guessed that you had assumed $ p$ to be the smallest prime or something of that sort. It turns out my guess was right!!

First of all $d(f(1))=1 \implies f(1)=1$

[b]Claim 1:[/b]$f(p)=p^{p-1}$ for all primes $p$.

[i]Proof[/i]:Let $p \ge 5$.Note that the condition $d(f(p))=p$ forces us to conclude that $f(p)$ has only one prime with power $p-1$,say $f(p)=q^{p-1}$.Let $f(3)=y^2$.Then taking $x=3,y=p$ we get

$f(3p)|2p^{3p-1}f(3)=2p^{3p-1}y^2$

Also note that $f(3p)$ can have two forms:$r^2s^{p-1}$ or $r^{3p-1}$ where $r$ and $s$ are primes.In the former case $r=y,s=p$ and in the later case $r=p$ (This can be determined by checking the size of the exponents)..Taking $x=p,y=3$ we have

$f(3p)|(p-1)3^{3p-1}f(p)=(p-1)3^{3p-1}q^{p-1}$.In the later case we have $f(3p)=p^{3p-1}$.Note that $p$ cannot be $3$ and cannot divide $p-1$ and the exponent $3p-1$ of $p$ is also greater than the exponent $p-1$ of $q$.So the later case cannot hold.
Now consider the former case.In this case $f(3p)=y^2p^{p-1}$.Now $p$ cannot divide $p-1$ and $3$ so $p=q$.That is $f(p)=p^{p-1}$.Also we get $y^2|(p-1)3^{3p-1}$.This holds for arbitrary $p$ so choose $p$ such that $\text{gcd}(y^2,p-1)=1$.Then we get $y=3$ so $f(3)=3^2$

Now taking $x=2,y=3$ we get
$f(6)|3^5f(2)$

Now using property (a) we get that $f(6)$ can have two forms namely,$lm^2$ or $l^5$ where $l,m$ are primes.In the first case we are forced to conclude that $m=3,l=f(2)$.In the second case we get $l=3$.Now taking $x=3,y=2$ and using $f(3)=3^2$ we get
$f(6)|2^63^2$.So the second case cannot hold.The first case has to hold,hence $f(2)$ has to be $2$(in combination with property(a)).Now we are done with our claim.

[b]Claim 2[/b]:$f(p^{\alpha})=p^{{p^{\alpha}}-1} \forall \alpha \ge 1$

[b]Proof[/b]:Taking $x=p,y=p^{n-1}$ we get
$f(p^n)|(p-1)p^{(n-1)(p^n-1)+p-1}$.Now let the prime factorization of $f(p^n)$ be $\prod_{i=1}^{s}{{r_i}^{m_i}}$.Now $s \ge 2$ implies that ${r_k}^{m_k}|p-1$ for some $k$.Let $p-1={r_k}^{m_k}j$.Note that property (a) shows that

$\prod_{i=1}^{s}{(m_i+1)}=p^n$ so $m_k$ must be of form $p^c-1$.In other words $p-1|m_k$.Taking modulo $p$ we get
$-1 \equiv j \pmod{p}$ so $j$ must be atleast $p-1$,i.e., $r_k$ can atmost be $1$,a contradiction.Hence $s=1$ and combining this with property (a),we get $f(p^n)=p^{p^n-1}$.Claim 2 is established.

Take $x=p_i,y={p_i}^{a_i-1}\prod_{j \neq i}{{p_j}^{a_j}}$.Then we get
 $f(\prod_{i=1}^{k}{{p_i}^{a_i}}|({p_i}-1)({p_i}^{a_i-1}\prod_{j \neq i}{{p_j}^{a_j}})^{\prod_{i=1}^{k}{{p_i}^{a_i}}-1}{p_i}^{p_i-1}$
where we have used $f(p_i)={p_i}^{p_i-1}$

Considering this for all $i$ we get that
$f({\prod_{i=1}^{k}{{p_i}^{{\alpha}_i}})=\prod_{i=1}^{k}{{p_i}^{a_i}\prod_{j=1}^{s}{{c_j}^{d_j}}}}$

Here $\prod_{j=1}^{s}{{c_j}^{d_j}}$ divides $p_i-1$ for all $i$.

Then by property (a) we have $\prod_{i=1}^{k}{(a_i+1)} \prod_{j=1}^{s}{(d_j+1)}={\prod_{i=1}^{k}{{p_i}^{a_i}}}$.
So $\prod_{j=1}^{s}{(d_j+1)}$ divides ${\prod_{i=1}^{k}{{p_i}^{a_i}}}$ which means that there exists an $i$ such that $d_1 \equiv -1\pmod{p_i}$ so $d_1 \ge p_i-1$.This means that ${c_1}^{d_1}\ge {c_i}^{p_i-1}>p_i-1$.
But note that $\prod_{j=1}^{s}{{c_i}^{d_i}}|(p_i-1)$ so ${c_1}^{d_1} \le \prod_{j=1}^{s}{{c_i}^{d_i}} \le p_i-1$.This contradicts our previous result.

Thus $f({\prod_{i=1}^{k}{{p_i}^{{\alpha}_i}})=\prod_{i=1}^{k}{{p_i}^{a_i}}}$.

Now take $x={p_i}^{\alpha_i}$ and $y=\prod_{j \neq i}{p_j^{\alpha_j}}$.We will get
$f({\prod_{i=1}^{k}{{p_i}^{{\alpha}_i}})|({p_i}^{\alpha_i}-1)(\prod_{j \neq i}{{p_j}^{\alpha_j}})^{\prod_{i=1}^{k}{{p_i}^{\alpha_i}}-1}{p_i}^{{p_i}^{\alpha_i}-1}}$

So the $a_i$ never exceeds ${p_i}^{{\alpha}_i}-1$ for all $i$ so

${\prod_{i=1}^{k}{{p_i}^{{\alpha}_i}}=\prod_{i=1}^{k}{(a_i+1)} \le {\prod_{i=1}^{k}{{p_i}^{{\alpha}_i}}}}$ and hence $a_i={p_i}^{{\alpha}_i}-1$.So multiplicativity is established.

Finally the function is defined as $f(1)=1,f({p}^{{\alpha}})={p}^{{p}^{\alpha}-1}$ and $f$ is multiplicative.

This is a very standard problem. I will use repeatedly that $x^{y-1}$ can't divide $y-1$ (because it's bigger), and also that if $p|f(n)$ then the exponent of $p$ must be of the form $d-1$ where $d|n$. By condition 1. Note that, in particular, if $x$ is the smallest prime divisor of $n$, then $p^{x-1} | f(n)$.

Firstly notice that for $r$ prime, $f(r)=s^{r-1}$ for some $s$ prime. Assume $s \neq r$. Now take $p>r,s$ a prime such that $p-1$ isn't divisible by $r$ nor $s$ (which can be done by CRT and Dirichlet). If $r$ or $s$=2, then make sure $p-1$ isn't divisible by $4$: Now, assume $f(p)=q^{p-1}$ for a prime $q$. Take any prime $a|f(pr)$. By first condition, $a^{r-1}|f(pr)$. If $a \neq q,s$ then $a^{r-1} | f(pr) | (r-1)s^{r-1}p^{big}$. But $a^{r-1}>r-1$, and therefore $a=p$. Then $a^{r-1}=p^{r-1} | (p-1)q^{p-1}r^{big}$, and since $a \neq q$, we get that $p=a=r$, contradiction to the definition of $p$. Therefore only $q,s$ divide $f(pr)$. Assume $s=q$, then $s^{pr-1}=f(pr) | s^{r-1}(r-1)p^{big}$ and so $s^{pr-r} | (r-1)p^{big}$ and since $s^{pr-r}>r-1$, we get $s=p$. Therefore, $p^{pr-1} = f(pr) | q^{p-1}(p-1)r^{big}$, so $p^{pr-1} | q^{p-1}$, contradiction. Therefore $s \neq q$. Now, if $s | f(pr)$ then $s^{r-1} | f(pr) | q^{p-1}(p-1)r^{big}$ and so $s^{r-1} | p-1$ and so, since we had said that $s$ didn't divide $p-1$ if $s$ was odd and $4$ didn't divide $p-1$, we get that $s=r=2$, contradiction since $s \neq r$. Therefore $s$ doesn't divide $f(pr)$ and so $f(pr)=q^{pr-1} | s^{r-1}(r-1)p^{big}$ and so $q=p$ and so $p^{pr-1} | q^{p-1}(p-1)r^{big}$, impossible. Finally we have a contradiction! So $\boxed{f(r)=r^{r-1}}$ for all $r$ prime.

Now let $r | f(p^k)$ for $r,p$ primes. Then $r^{p-1} | (p-1)p^{p-1}(p^{k-1})^{p^k-1}$ and since $r^{p-1}>p-1$, we get $r=p$. Therefore $f(p^k)=p^{p^k-1}$ for all $p$ prime.

Now let $p | f(m)$ be a prime that divides some $f(m)$. Let $x$ be the smallest prime divisor of $m$. If $p$ doesn't divide $m$, then $p^{x-1} | f(m) | (m/x)^{big}x^{x-1}(x-1)$ and so $p^{x-1} | (x-1)$, contradiction. So $p|m$, and let $x=p^a||m,y=m/x$. Then if $p^b || f(m)$, we get $p^b | (p^a-1)(f(p^a))$ and so $p^b | p^{p^a-1}$ and so $b \le p^a-1$. However, since this happens for all $p|f(m)$, and by condition 1 we get that $b=p^a-1$ for all $p|f(m)$. Therefore $f(m) = \prod_{p^a||m} f(p^a)$.

So we are done and the answer is $\boxed{f(\prod p_i^{a_i}) = \prod p_i^{p_i^{a_i}-1}}$. Oh, and $f(1)=1$ clearly.

The important step in this problem is showing that $f(p^k) = p^{p^k-1}$, for the problem is not so hard after that. Here's a very straightforward, "just do it" style solution. There is only one clever step in here, and it is not too hard to notice once you see the condition. It should remind you of how we count the number of divisors of a number.

Observe that the condition rearranges to
 \[ v_p(f(xy)) \le v_p(x-1) + (xy-1)v_p(y) + v_p(f(x)) \]
This condition is trivial for all primes dividing $y$, so we will consider $v_p(f(xy)) \le v_p(x-1) + v_p(f(x))$  for all primes not dividing $y$.Observe that, for any prime $q$,
\[ (q^n + 1)(q^n) = d(f((q^n+1)(q^n))) \]

  Taking $p = q$, $y = q^n + 1$, and $x = q^n$ gives that the latter is
 \[ \prod_{p}(1+v_p(f(q^n(q^n+1)))) \]

\[  =(1+v_q(f(q^n)(q^n+1))) \times  \prod_{p \neq q} (1+v_p(f(q^n)(q^n+1))) \]

Since $v_p(x-1) = 0$, Now, observe that $p \nmid q^n$, so \[ (1+v_p(f((q^n)(q^n+1))) \le (1 + v_p(q^n) + v_p(f(q^n+1)) = 1 + v_p(f(q^n+1))  \] . Hence, the previous product is
  \[\le (1 + v_q(f(q^n)(q^n+1))) \times \prod_{p \neq q} (1 + v_p(f(q^n+1))) \]
 \[ \le (1 + v_q(f(q^n)(q^n+1))) \times d(f(q^n+1))  \]

 \[ = (q^n+1)(1 + v_q(f(q^n)(q^n+1)) \]

 Hence, we obtain the result \[ v_q(f((q^n)(q^n+1)) \ge q^n-1 \]
Now, observe that
 \[ q^n - 1 \le v_q(f((q^n)(q^n+1)) \le v_q(q^n-1) + v_q(f(q^n)) = v_q(f(q^n))\]

, but in fact equality must hold, since $d(f(q^n)) = q^n$! Hence, we obtain $f(q^n) = q^{q^n-1}$.

As $d(f(1))=1$, we have $f(1)=1$. As $d(f(2))=2$, we get that $f(2)$ is a prime. Let $p\ge 3$ be a prime. As $f(2p)|p^{2p-1}f(2)$, from $d(f(2p))=2p$ we get that either $f(2p)=p^{2p-1}$ or $f(2p)=p^{p-1}f(2)$, so $p^{p-1}|f(2p)$. So $p^{p-1}|f(2p)|(p-1)2^{2p-1}f(p)$ which, combined with $d(f(p))=p$, yields $f(p)=p^{p-1}$. This forces $f(2p)=p^{p-1}f(2)$; we have that $f(2)|(p-1)2^{2p-1}$. If $f(2)\ne 2$, as $f(2)$ is a prime, we get that $f(2)|p-1$ for any prime $p\ge 3$. It is enough to choose $p\equiv 2(\mathrm{mod}\ f(2))$ to obtain a contradiction, so $f(2)=2$.

We have that $f(p^k)|(p-1)p^{p-1}\left (p^{k-1} \right )^{p^k-1}$. Let $q$ be a prime divisor of $f(p^k)$. As $d(f(p^k))=p^k$, we get that $v_q(f(p^k))=p^\alpha-1\ge p-1$. If $q|p-1$, then $q\ne p$, so $q^{v_q(f(p^k))}|p-1$. But $q^{v_q(f(p^k))}\ge q^{p-1}\ge 2^{p-1}>p-1$, a contradiction, so $q=p$. We thus get that $f(p^k)$ is a power of $p$; from $d(f(p^k))=p^k$ we get that $f(p^k)=p^{p^k-1}$.

Let $n\in \mathbb{N}$ be a number with at least two prime divisors, $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k}$ with $p_1<p_2<...<p_k$. We have that $f(n)|(p_1-1)p_1^{p_1-1}\left ( p_1^{\alpha-1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k} \right )^{n-1}$. Let $q$ be a prime dividing $f(n)$. As $d(f(n))=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k}$ we have that $v_q(f(n))=p_{i_1}^{\beta_1}\cdot p_{i_2}^{\beta_2}\cdot... \cdot p_{i_t}^{\beta_t}-1\ge p_1-1$. If $q|p_1-1$, then $q<p_1<p_2<...<p_k$, so $q^{v_q(f(n))}|p_1-1$, which is a contradiction because $q^{v_q(f(n))}\ge q^{p_1-1}\ge 2^{p_1-1}>p_1-1$. Therefore $(q,p_1-1)=1$, hence $q\in \{ p_1,..,p_k\}$. Thereby, any prime divisor of $f(p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k})$ can be found in the set $\{p_1,p_2,..., p_k\}$.

So $f(n)=f(p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k})=p_1^{x_1}p_2^{x_2}...p_k^{x_k}$ with $x_1,x_2,...,x_k\in \mathbb{N}$ (some of them are possibly $0$). Write $n=p_i^{\alpha_i}y$. Obviously, $p_i$ does not divide $y$. As $f(n)=f(p_i^{\alpha_i}y) | (p_i^{\alpha_i}-1)p_i ^{p_i^{\alpha_i}-1}y^{n-1}$, we have that $$x_i=v_{p_i}(f(n))\le v_{p_i} \left ( (p_i^{\alpha_i}-1)p_i ^{p_i^{\alpha_i}-1}y^{n-1} \right ) =p_i^{\alpha_i}-1$$ Therefore, $d(f(n))\le (x_1+1)(x_2+1)...(x_k+1)\le p_1^{\alpha_1}p_2^{\alpha_2}\cdot ... p_k^{\alpha_k}=n$. But $d(f(n))=n$, so we actually have equality in every inequality, i.e. $x_i=p_i^{\alpha_i}-1$. We conclude that $$f(p_1^{\alpha_1}p_2^{\alpha_2} ... p_k^{\alpha_k})=p_1^{p_1^{\alpha_1}-1}p_2^{p_2^{\alpha_2}-1} ... p_k^{p_k^{\alpha_k}-1}$$
[hide="tl;dr"]The first paragraph shows that $f(p)=p^{p-1}$ for all primes and the second gives $f(p^k)=p^{p^k-1}$. We see that every prime divisor of $f(n)$ must be a prime divisor of $n$ and we finish our proof with the aid of inequalities. [/hide]

We claim that $f(n)$ is a multiplicative function with $f(p^k)=p^{p^k -1 }$. Clearly $f(1)=1$.

[b]Lemma 1[/b]: For primes $p$, $f(p)=p^{p-1}$.

[b]Proof:[/b] Note that $f(p)$ is the $p-1$th power of some prime. WLOG $p> q$. Now, note that $f(pq)\mid (p-1)\cdot q^{pq-1}\cdot f(p)$ and $f(pq)\mid (q-1)\cdot p^{pq-1}\cdot f(q)$. Note that $f(pq)$ is either of form $a^{pq-1}$ or $b^{p-1}\cdot c^{p-1}$; i.e., $f(pq)$ has at most two prime divisors. Suppose $f(pq)$ had only one prime divisor; i.e. it was the $pq-1$th power of a prime. Then that $pq-1$th power must divide both $(p-1)\cdot q^{pq-1}\cdot f(p)$ and $(q-1)\cdot p^{pq-1}\cdot f(q)$. Note that $p-1$ and $q-1$ are both too small to have their own $pq-1$th power, and similarly with $f(p)$ and $f(q)$ (because they are $p-1$ and $q-1$th powers, respectively). But this means that $f(pq)\mid q^{pq-1}$ and $f(pq)\mid p^{pq-1}$, which is a contradiction! Thus $f(pq)$ has two prime divisors. By the second divisibility relation, these primes must be $p$ and the prime dividing $f(q)$. Indeed, $q-1$ is not large enough to have a prime factor, distinct from that dividing $p$ or $f(q)$, for it to have a prime-adic valuation of $q-1$. But then this means $p\mid f(pq)$, so $p\mid (p-1)\cdot q^{pq-1}\cdot f(p)$. Thus $p\mid f(p)$. Since $f(p)$ is the $p-1$th power of a prime, $f(p)=p^{p-1}$. Note that if $p$ is an odd prime, then there is always a prime smaller than $p$, so we can repeat this process for all odd primes $p$.

Next we show $f(2)=2$. Suppose $f(2)=P$ for some odd prime $P$. Then take $p$ with $P\nmid p-1$. Note that $f(2p)\mid p^{2p-1}\cdot P$, and $f(2p)\mid (p-1)\cdot 2^{2p-1}\cdot f(p)$. Note that $P\nmid f(2p)$, from the last relation, as $P\nmid f(p), p-1, 2$. Thus $f(2p)\mid p^{2p-1}$ from the first relation. It follows $f(2p)=p^{2p-1}$. But then $p^{2p-1}\mid (p-1)\cdot 2^{2p-1}\cdot f(p)$, a contradiction as $v_p(f(p))=p-1 < 2p-1$. Thus $f(2)=2$. $\blacksquare$

[b]Lemma 2:[/b] $f(p^k) = p^{p^k-1}$.

[b]Proof:[/b] Note that $f(p^k)=f(p\cdot p^{k-1})\mid (p-1)\cdot \left(p^{k-1}\right)^{p^k-1} \cdot f(p)$. In other words, $f(p^k)$ divides $(p-1)\cdot p^r$ for some large $r$, by Lemma 1. Suppose $f(p^k)=(p-1)\cdot p^s$ for $s\le r$. But then $d(f(p^k)) = d(p-1)\cdot d(p^s)$. Note that $p\nmid d(p-1)$, as the p-adic valuation of any prime dividing $p-1$ must be less than $p-1$. Thus $f(p^k)$ is a power of $p$. It is easy to see, therefore, that $f(p^k) = p^{p^k-1}$, as desired. $\blacksquare$

Now we establish the multiplicativity. Suppose $n=\prod p_i^{e_i}$. We show that $f(n)=\prod f(p_i^{e_i})$.

First, we establish that the set of primes dividing $f(n)$ is a subset of the set of primes dividing $n$. Let $p_1$ be the smallest prime dividing $n$. Then $f(n)=f\left(p_1\cdot n/p_1\right) \mid (p_1-1)\cdot (n/p_1)^{n-1}\cdot f(p_1)=(p_1-1)\cdot (n/p_1)^{n-1}\cdot p_1^{p_1-1}$. Now, if some integer $m\mid f(n)$ and $m$ does not divide $n$, then $m\mid p_1-1$. But then the $p$-adic valuation of $m$ is strictly less than $p_1-1$ for any prime $p$, and thus $d(m)$ is relatively prime to $p_1,..., p_k\mid n$. In particular, $d(m)\mid d(f(n))=n$, a contradiction unless $d(m)=1$, or $m=1$. Thus the only integer $m$ such that $m\mid f(n)$ and $m$ doesn't divide $n$ is $m=1$.

Now we show that $v_{p_i} (f(n))\le p_i^{e_i} - 1$. Indeed, take $p=p_j$ and $e=e_j$ for some $j$ and $p_j\mid n$. Then $f(n)=f(p^e\cdot n/p^e)\mid \left(p^e-1\right)\cdot (n/p^e)^{n-1}\cdot f(p^e)$. Note that the $p$-adic valuation of the right side is $p^e-1$. Thus $v_{p_j} (f(n))\le p_j^{e_j} - 1$. But this implies that $d(f(n))\le \prod \left(p_i^{e_i} - 1 + 1\right) = n$. Thus each inequality must be an equality, so $v_{p_i}(f(n))=p_i^{e_i} - 1$. Moreover, since the set of primes dividing $f(n)$ is a subset of the primes dividing $n$, we have established that $f(n)=\prod p_i^{p_i^{e_i} - 1}$, as desired. It is easy to check that this $f$ works. $\square$

[quote=IMO ShortList 2008 N5]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: [list][*] $ d\left(f(x)\right) \equal{} x$ for all $ x\in\mathbb{N}$.
[*] $ f(xy)$ divides $ (x \minus{} 1)y^{xy \minus{} 1}f(x)$ for all $ x$, $ y\in\mathbb{N}$.[/list]

[i]Proposed by Bruno Le Floch, France[/i][/quote]

[hide=solution] Obviously $f(1)=1$ since $d(f(1))=1$. Note that for any prime $p$ we have $d(f(p))=p$ so $f(p)=q^{p-1}$ where $q$ is a prime. Our most important observation is $$f(xy) \mid \gcd\left((x-1)y^{xy-1}f(x), (y-1)x^{xy-1}f(y)\right).$$Henceforth, it will be referred as $P(x,y)$ and the original condition as $(+)$.

[b]Lemma 1[/b] For any $x>1$ we have $\gcd(x, f(x))>1$.

(Proof) Fix $x_0>1$ for which $\gcd(x_0, f(x_0))=1$. Set $y_0=1+x_0(x_0-1)f(x_0),$ then $$P(x_0, y_0) \Longrightarrow f(x_0y_0) \mid f(y_0) \Longrightarrow y_0<x_0y_0=d(f(x_0y_0)) \le d(f(y_0))=y_0,$$a contradiction!

As a corollary, $f(p)=p^{p-1}$ for all primes $p$. $\square$

[b]Lemma 2[/b] For all $k \geqslant 1$ we have $f(p^k)=p^{p^k-1}$.

(Proof) Proceed by induction on $k \geqslant 1$. The base case is already shown; so it suffices to show it for $k+1$. Put $x=p$ and $y=p^k$ in $(+)$ to obtain $$f(p^{k+1}) \mid (p-1)p^{p^{k+1}-1}f(p^k)=(p-1)p^{p^k+p^{k+1}-2}.$$Let $q \ne p$ be a prime, $q \mid f(p^{k+1})$. Note that $d(f(p^{k+1}))=p^{k+1}$ so $v_q(f(p^{k+1}))=p^j-1 \ge p-1$.

Thus, $q^{p-1} \mid (p-1)p^{p^k+p^{k+1}-2}$ so $q^{p-1} \mid p-1$ which is false, since $q^{p-1}>p-1$. It follows that $f(p^{k+1})=p^{\ell}$ and so by the divisor condition, we get $\ell=p^{k+1}-1$ completing the induction step. $\square$

[b]Lemma 3[/b] For any natural numbers $x, y$ with $\gcd(x,y)=\gcd(x-1, y-1)=1$ we have $f(xy)=f(x)f(y)$.

(Proof) Pick $x, y$ satisfying the condition of the lemma. Note that for any prime $p \mid f(xy)$ and $p \nmid f(x)f(y)$, condition $P(x, y)$ gives $$p \mid \gcd\left((x-1)y^{xy-1}, (y-1)x^{xy-1}\right)=1.$$Also, if $p \mid f(xy)$ then $v_p(f(xy)) \le v_p(f(x)f(y))$ since $p$ divides no more than one of the numbers $(x-1)y^{xy-1}, (y-1)x^{xy-1}$, so $f(xy) \mid f(x)f(y)$.

The divisor condition yields $$xy=d(f(xy)) \le d(f(x)f(y)) \le d(f(x))d(f(y))=xy,$$so we have $f(xy)=f(x)f(y)$. $\square$

[b]Lemma 4[/b] For all $n \geqslant 1$ and prime $p$ we have $p \mid f(n) \Longrightarrow p \mid n$.

(Proof) For $n=1$ its clear. For $n>1$ odd we have $\gcd(n, 2)=\gcd(n-1, 1)=1$ so $$f(2)f(n)=f(2n) \mid (2-1)n^{2n-1}f(2) \Longrightarrow f(n) \mid n^{2n-1},$$hence the claim is true. Observe that for $m \in \mathbb{N}$ we have $f(2m) \mid (2-1)m^{2m-1}f(2)=2m^{2m-1}$ so the result holds for even numbers as well. $\square$

Pick any number $n$ and write $n=p_1^{\alpha_1}\cdot \dots \cdot p_k^{\alpha_k}$ in its canonical form. Note that $$f(n) \mid \left(p_j^{\alpha_j}-1\right)\cdot \left(\frac{n}{p_j^{\alpha_j}}\right)^{n-1}p_j^{p_j^{\alpha_j}-1},$$for all $1 \le j \le k$. For an index $i$ let $p_i \mid f(n)$ be a prime. Then, choosing the equation for $j=i$ we get $v_{p_i}(f(n)) \le p_i^{\alpha_i}-1$. However, since $f(n)$ has no prime factors than those of $n$, we get $$n=d(f(n)) \le \prod^k_{j=1}\left((p_j^{\alpha_j}-1)+1\right)=n.$$
Evidently, it follows that for all $n \in \mathbb{N}$ we have $f(n)=\prod_{p \in \mathbb{P}} p^{p^{v_p(n)}-1}$ where $\mathbb{P}$ is the set of all primes and the empty product is conventionally taken to be $1$. One can verify that this function actually does work, so we are done!

[/hide]

Nice illustration of my firm belief, "All (good) FEs are motivated!" :P

Please check my solution :help:

[hide=Solution] Let the assertion $P(x,y)$ denote $f(xy)|(x-1)x^{xy-1}f(x)$, and let $S(n)$ be the set of distinct primes dividing $n$. We (over)use the [b]first holy fact[/b] $p^{x-1} > x-1$ and [b] second holy fact [/b]for any prime $p$, $min(v_p(d(f(x)))) > min(S(x))$.
[b] Claim-1 [/b]: For prime $p$, $f(p) = p^{p- 1}$
[hide = Proof] As $d(f(p)) = p = p*1$, we have $d(f(p)) = q^{p-1}_p$ for some prime $q_p$. Now, for $p \neq q_2,2$, let $S(f(2p)) = \{q_a, q_b \}$.We have $$P(2,p) \Rightarrow f(2p) | p^{2p-1}q_2 \Rightarrow S(f(2p)) \subset \{p, q_2 \}$$, and $$f(2p) \in \{ p^{p-1}q_2, p^{2p -1} \}$$. Also, we have $$P(p, 2) \Rightarrow f(2p) | (p-1) 2^{2p-1} q_p$$. Now, as $gcd(p, p-1) = gcd(p, 2) = 1$, we have $f(2p) = p^{p-1}q_2$.
)
Now, as atleast one of $\{3,5, 17 \}$ isn't $q_2$, taking pairwise $gcd$ of $f(3*2), f(5*2), f(17*2)$, we have $q_2 = 2$. So, $$f(p) = p^{p-1}$$ for all primes $p$. [/hide]

[b] Claim-2 [/b]:  For prime $p$ and any positive integer $k$, $f(p^k) = p^{p^k - 1}$
[hide = Proof] We prove it by induction.  The base case $k = 1$ is already covered in the previous claim. Assume it's true for $k \geq 1$, so $f(p^k) = p^{p^k - 1}$. Now, $$P(p, p^k) \Rightarrow f(p^{k+1} ) | (p-1) p^{\text{ A big number }} $$, so coupled with the second holy fact and $gcd(p, p-1) = 1$, we have $S(f(p^{k+1})) = \{p \}$. Now, from the condition $d(f(x)) = x$, we get $v_p(f(p^{k+1})) = p^{k+1} - 1$.  [/hide]

[b] Claim - 3 [/b] For any integer $n$, we have $$f(n) = \prod_{p \in S(n)} p^{p^{v_p(n)}-1} $$.
[hide = Proof] Integers with $|S(n)| = 1$, i.e having only a prime divisor is already covered. We prove the claim by induction on numbers with $|S(n)| > 1$, i.e has atleast $2$ distinct primes dividing it. Base case $n = 6$ is obvious by considering $P(2,3), P(3,2)$. We assume the assertion is true for all integers less or equal to $n \geq 6$. For the next least integer $k > n$ with $|S(k)| > 2$, let $min\{S(k) \} = p_s$.
[b] Claim [/b]: $S(f(k)) \subset S(k)$.
[hide = Proof]. Assume the contray, and let $q \in S(f(k))$ but $q \notin S(k)$. Also, from the second holy fact, we have $e := v_q(d(f(x))) \geq min(S(x))$ . But, $$P(p_s, \frac{k}{p_s} ) \Rightarrow  q^e | f(k) | (p_s - 1) * \text{ Terms relatively prime to q } $$ $$ \Rightarrow q^e | (p_s - 1)$$, but this produces a contradiction using the first holy fact, as $e \geq p_s - 1$  [/hide]

[b] Claim [/b]: For $p \in S(f(k))$, we have $v_p(f(k)) \leq p^{v_p(k) - 1}$
[hide = Proof] $$P(p, \frac{p}{k}) \Rightarrow p^{v_p(f(k))} | f(k) | (p-1)(\frac{k}{p})^{k-1} f(p^{v_p(k)}) = f(p^{v_p(k)}) * \text{Terms relatively prime to p }$$ $$ \Rightarrow p^{v_p(f(k))} | f(p^{v_p(k)}) \Rightarrow v_p(f(k)) \leq p^{v_p(k) - 1} $$, as desired. [/hide]

So now we have $d(f(k)) = d(\prod_{p \in S(k) } p^{v_p(f(k))}) \leq d(\prod_{p \in S(k) } p^{p^{v_p(k) - 1}} ) = \prod_{p \in S(k) } (p^{v_p(k)}-1+1) = k$, so equality assumes everywhere, so we prove the claim, as desired. [/hide]

Beautiful problem. Here's my solution: Let $P(x,y)$ denote the second condition given to us. We make a series of claims, which will help us in discovering $f(x)$.
--------
[size=150]CLAIM-1[/size][size=200]|[/size] $f(1)=1$ and $f(2)=2$.

[i][u]Proof of Claim[/u][/i] As $d(f(1))=1$, so we directly get that $f(1)=1$. Let $f(p)=p_1^{e_1}p_2^{e_2} \dots p_n^{e_n}$, for some primes $p,p_1,p_2, \dots ,p_n$. Then $$d(f(p))=p \Rightarrow (e_1+1)(e_2+1) \dots (e_n+1)=p \Rightarrow e_1=p-1,e_2=0,e_3=0, \dots ,e_n=0$$
Thus, we get that, for all primes $p$, $f(p)=q^{p-1}$, for some prime $q$. Taking $p=2$, we have $f(2)=q$.

Now, We have that $$P(2,q) \Rightarrow f(2q) \mid q^{2q-1} \cdot f(2) \Rightarrow f(2q) \mid q^{2q} \Rightarrow f(2q)=q^a \text{ for some } 0 \leq a \leq 2q$$
But, as $d(f(2q))=2q$, so $a+1=2q \Rightarrow a=2q-1$. However, taking $f(q)=q_1^{q-1}$ for some prime $q_1$, we get that $$P(q,2) \Rightarrow f(2q) \mid (q-1) \cdot 2^{2q-1} \cdot f(q) \Rightarrow q^{2q-1} \mid (q-1) \cdot 2^{2q-1} \cdot q_1^{q-1} \Rightarrow q=2$$
where the last statement follows using the fact that $\gcd(q^{2q-1},q-1)=1$. Thus, our claim is true. $\Box$
--------
[size=150]CLAIM-2[/size][size=200]|[/size] For all primes $p$, we have $f(p)=p^{p-1}$.

[i][u]Proof of Claim[/u][/i] We already showed (while proving Claim-1), that for all primes $p$, $f(p)=q^{p-1}$, for some prime $q$. We have already showed that this claim is true for $p=2$. So from now on assume that $p$ is an odd prime. Then, using Claim-1, we get that $$P(2,p) \Rightarrow f(2p) \mid 2p^{2p-1} \Rightarrow f(2p)=2^ap^b \text{ for some } o \leq a \leq 1 \text{ and } 0 \leq b \leq 2p-1$$
But, as $d(f(2p))=2p$, so we have $(a+1)(b+1)=2p$. When $a=0$, we have $b=2p-1$, and when $a=1$, we have $b=p-1$. Thus, we get that $p^{p-1} \mid f(2p)$ in both the cases. This gives $$P(p,2) \Rightarrow f(2p) \mid (p-1) \cdot 2^{2p-1} \cdot f(p) \Rightarrow p^{p-1} \mid (p-1) \cdot 2^{2p-1} \cdot q^{p-1} \Rightarrow q=p$$
where the last statement follows from our assumption that $p$ is odd, and the fact that $\gcd(p^{p-1},p-1)=1$. Thus, our claim is true. $\Box$
---------
[size=150]CLAIM-3[/size][size=200]|[/size] For all primes $p$ and positive integers $m$, we have $f(p^m)=p^{p^m-1}$.

[i][u]Proof of Claim[/u][/i] Using Claim-2, we can see that $$P(p,p^{m-1}) \Rightarrow f(p^m) \mid (p-1) \cdot p^{(m-1)(p^m-1)} \cdot p^{p-1}$$
Suppose, to the contrary, there exists a prime $p_0 \neq p$ such that $p_0^{e_0} \mid f(p^m)$ for some $e_0 \in \mathbb{N}$. Then, $e_0+1 \mid d(f(p^m))=p^m$, which gives that $e_0=p^k-1$ for some $1 \leq k \leq m$. Then, by the above condition, we have that $$p_0^{e_0} \mid f(p^m) \mid (p-1)p^{(m-1)(p^m-1)+p-1} \Rightarrow p_0^{p^k-1} \mid p-1 \Rightarrow p-1 \geq p_0^{p^k-1} \geq p_0^{p-1}$$
But, by FLT, we get that $$p \mid p_0^{p-1}-1 \Rightarrow p_0^{p-1} \geq p+1>p-1 \rightarrow \text{CONTRADICTION}$$
Thus, we must have $f(p^m)=p^s$ for some positive integer $s$. Then, as $d(f(p^m))=p^m$, so we have $s+1=p^m$, thus proving our claim. $\Box$
--------
[size=150]CLAIM-4[/size][size=200]|[/size] Let $p$ be a prime divisor of $f(n)$ for some positive integer $n$. Then $p \mid n$.

[i][u]Proof of Claim[/u][/i] Suppose, to the contrary, $p \nmid n$. Let $\nu_p(f(n))=k$. Then $k+1 \mid d(f(n))=n,$ which means that some prime divisor of $n$ (say $q$) divides $k+1$ also. Then we have $$q \mid k+1 \Rightarrow q \leq k-1 \Rightarrow p^{q-1} \mid p^k \mid f(n) \Rightarrow \text{By } P \left(q, \frac{n}{q} \right) \text{, we get that } p^{q-1} \mid f(n) \mid (q-1) \cdot n^{qn-1} \cdot q^{q-1}$$
As $\gcd(p,n)=\gcd(p,q)=1$, we get that $p^{q-1} \mid q-1$. However, by FLT, we have that $$q \mid p^{q-1}-1 \Rightarrow p^{q-1} \geq q+1>q-1 \Rightarrow p^{q-1} \nmid q-1 \rightarrow \text{CONTRADICTION}$$
Thus, our assumption must be wrong, which gives that $p \mid n$, hence proving our claim. $\Box$
---------
[size=150]CLAIM-5[/size][size=200]|[/size] $f$ is multiplicative on coprime integers, or equivalently, we have $f(p_1^{m_1}p_2^{m_2}...p_r^{m_r})=f(p_1^{m_1})f(p_2^{m_2}) \dots f(p_r^{m_r})$ for primes $p_1,p_2, \dots p_r.$

[i][u]Proof of Claim[/u][/i] Let $p_1^{m_1}p_2^{m_2} \dots p_r^{m_r}=n$. By Claim-4, we have that $f(n)=p_1^{k_1}p_2^{k_2} \dots p_r^{k_r}$ for non-negative integers $k_1,k_2, \dots ,k_r$. Note that, using Claim-3, we have that $$P(p_r^{m_r},p_1^{m_1}p_2^{m_2} \dots p_{r-1}^{m_{r-1}}) \Rightarrow p_1^{k_1}p_2^{k_2} \dots p_r^{k_r}=f(n) \mid (p_r^{m-r}-1)(p_1^{m_1}p_2^{m_2} \dots p_{r-1}^{m_{r-1}})^{n-1} \cdot f(p_r^{m_r}) \Rightarrow p_r^{k_r} \mid p_r^{p_r^{m_r}-1} \Rightarrow k_r \leq p_r^{m_r}-1$$
Repeating this same argument, one easily gets that $k_i+1 \leq p_i^{m_i}$ for all $i \in \{1,2, \dots ,r\}$. Then we have $$\prod_{i=1}^r (k_i+1)=d(f(n))=n \Rightarrow n \leq \prod_{i=1}^r p_i^{m_i}=n \text{, which means that equality must hold in all cases.}$$
Thus, we get that $k_i=p_i^{m_i}-1$, hence proving our claim (using Claim-3). $\Box$
---------
So finally we can determine all such functions $f$ by $$\boxed{f(1)=1,f(p^m)=p^{p^m-1} \text{ and } f \text{ is multiplicative.}}$$

Wow, what a problem... nothing non-elementary, yet... anyhow here's my solution, which I've tried to make as "motivated" as possible...

First, let $P(x,y)$ denote $f(xy) \mid (x-1)y^{xy-1}f(x)$, and there's no real point keeping $Q(x)$ as $d(f(x))=x$, so we won't.

Before we try to really attack the problem, let's try and get the obvious down- $f(1)=1$, by $Q(1)$, $f(2)$ must be prime, $f(p)$ must be $q^{p-1}$ for some primes $p$ and $q$... Hmm, we can already get a feel that the problem must heavily rest on primes, as such questions usually tend to.

So, considering there really isn't too much information to go by, perhaps let's begin with the only concrete information we have about a particular number- in other words, let's try to figure out what we could do with $f(2)=r$ ($r$ prime).
$$P(2,r): f(2r) \mid r^{2r}$$
As $d(f(2r))=2r$, and the only prime factor of $f(2r)$ is $r$, thus $f(2r)=r^{2r-1}$
Now, naturally the next substitution would be $(r,2)$, so:
$$P(r,2): f(2r)=r^{2r-1} \mid (r-1)2^{2r-1}f(r)=>r^{2r-1} \mid 2^{2r-1}f(r)$$
Say $r \neq 2$- Thus $r^{2r-1} \mid f(r)$, and as $f(r)=q^{r-1}$ for prime $q =>$ Contradiction, as $r$ is prime.

Hence $f(2)=2$.

Now comes the time for the key substitutions that we will spam throughout the rest of the solution- $P(2,y)$ and $P(x,2)$.
First let's take some $x=p^n$, for prime $p$ and integer $n$-
$$P(2,p^n): f(2p^n) \mid 2(p^n)^{2p^n-1}$$
As only possible prime factors of $f(2p^n)$ are $2$ and $p$, and $d(f(2p^n))=2p^n$, thus $f(2p^n)=p^{2p^n-1}$ or $2p^{p_n-1}$. But, as
$$P(p^n,2): f(2p^n) \mid 2^{2p^n-1}(p^n-1)f(p^n)$$
Hence, if $f(2p^n)=p^{2p^n-1} =>p^{2p^n-1} \mid f(p^n)$- but as $d(f(p^n))=p^n=>$ Contradiction. Thus $\boxed{f(2p^n)=2p^{p^n-1}}$.
Again, as $f(2p^n)=2p^{p^n-1} \mid 2^{2p^n-1}(p^n-1)f(p^n) =>p^{p^n-1} \mid f(p^n)$. As $d(f(p^n))=p^n=>\boxed{f(p^n)=p^{p^n-1}}$.

Till here we had a relatively smooth sail, at least after we got hold of the key idea- now we must be really careful, as going down the wrong path could really lead to some un-understandable mess, especially since we're dealing with towers of powers here...

Anyway, the key observation here comes with playing with $P(p^ny,2)$ and $P(2p^n,y)$ and its variants and building an inductive argument from this- first let's just write down all these aforementioned variants and see if we get something-
$$P(2p^n,y): f(2p^ny) \mid (2p^n-1)y^{2p^ny-1} \cdot 2p^{p^n-1}$$
$$P(y,2p^n): f(2p^ny) \mid (y-1)f(y)2^{2p^ny-1}p^{n(2p^ny-1)}$$
$$P(2,p^ny): f(2p^ny) \mid 2p^{n(2yp^n-1)} y^{2yp^n-1}$$
$$P(p^ny,2): f(2p^ny) \mid (p^ny-1) 2^{2p^ny-1}f(p^ny)$$
Hmm... so the idea here is to build a sort-of inductive argument using $gcd(p,y)=1$, building $x$ out of prime powers (this is also why we proved $f(p^n)=p^{p^n-1}$ for a prime power, not simply for a prime $p$)- thus we can let $y=q_1^{\alpha_1}q_2^{\alpha_2}...q_k^{\alpha_k}$, assuming $f(y)=q_1^{q_1^{\alpha_1}-1}...q_k^{q_k^{\alpha_k}-1}$.

Let's now try to set restrictions on the powers of primes dividing $f(p^ny)$, and then try to sneak in $d(f(x))$ somewhere.
First, notice by equation $3$, the only prime divisors of $f(2p^ny)$ are $2,p,q_1,q_2,...,q_k$ and $v_2(f(2p^ny) \leq 1$. Moreover, by equation $1$, $v_p(f(2p^ny)) \leq p^n-1$ and by equation $2$, $v_{q_i}(f(2p^ny) \leq q_i^{\alpha_i}-1$.

Now, perhaps, we have enough to finish this off- observe $f(2p^ny)=2p^{p^n-1}q_1^{q_1^{\alpha_1}-1}...q_k^{q_k^{\alpha_k}-1}$ satisfies $d(f(2p^ny)) =2p^ny$, and it's easy to see that it's the only value of $f(2p^ny)$ that satisfies $d(f(2p^ny))=2p^ny$ (if there was some other value, then this must mean that one of the powers of primes of this other $f(2p^ny)$ must be larger than the power on the prime of our old $f(2p^ny)$, which is of course impossible by our bounds.

There was one small assumption made throughout this argument, and that was $p$ must be an odd prime [hide=note] did you catch that :) [/hide]- in other words, we've only found $f(x)$ for odd $x$. Luckily for us, the even part becomes relatively simple once the odd part's done, and this is what we'll attempt to prove here.

First, following the $P(2,2^n)$ tradition, we get $f(2^{n+1}) \mid 2 \cdot 2^{n(2^{n+1}-1)} =>2$ is the only prime divisor of $f(2^{n+1}$.
As $d(f(2^n))=2^n$, we get $f(2^n)=2^{2^n-1}$. Now the rest of the argument remains the same, but instead of having to multiply by an arbitrary $p^n$, we do it with a more concrete $2^n$.

And now, finally, we're truly done, and hence our solution holds as:
$f(n)$, for $n=p_1^{\alpha_1}...p_k^{\alpha_k}$, equals $p_1^{p_1^{\alpha_1}-1}p_k^{p_2^{\alpha_2}-1}...p_1^{p_k^{\alpha_k}-1}$, and this indeed works.

[quote=harazi]Indeed, a terrible problem![/quote]
Solved with [b]william122[/b].

The unique function $f$ is constructed as follows:
[list]
[*] $f(p^e) = p^{p^e - 1}$, and
[*] $f$ is multiplicative.
[/list]
(So for instance, $f(6) = f(2)f(3) = 2 \cdot 3^2$.) This evidently satisfies the first condition, and for any prime that divides $xy$
$$\nu_p(xy) = p^{\nu_p(xy)} - 1 < xy-1 \leq \nu_p(y^{xy-1})$$
if $p \mid y$. If not, then $p^{\nu_p(xy)} - 1 = p^{\nu_{p}(x)} - 1 = \nu_p(f(x))$, so $f$ works.

We now show that it is unique. Evidently $f(1) = 1$. The primary claim is the following.

[b][color=#ff9a00]Claim 1.[/color][/b] For all primes $p$, $f(p) = p^{p-1}$.

[i][color=#ff9a00]Proof.[/color][/i] Pick a prime $q$ for which $p-1 < 2^{q-p}$. Then the second condition gives us
[list]
[*] $f(p \cdot q)$ divides $(p-1) q^{pq - 1} f(p)$, and
[*] $f(q \cdot p)$ divides $(q-1) p^{pq - 1} f(q)$.
[/list]
Because $d(f(pq)) = pq$, we have $f(pq) \in \{a^{pq - 1}, a^{q-1}b^{p-1}\}$ for primes $a$ and $b$; either way, there must exist a prime $a$ such that $\nu_a(f(pq)) \geq q-1$. So $a^{q-1} \mid (p-1) q^{pq-1} f(p)$, id est $a = q$ or $a^{q-1} \mid (p-1)f(p)$. But $(p-1)f(p) < 2^{q-p}f(p)$, so the latter case is impossible. Thus,
$$q^{a-1} \mid f(q \cdot p) \mid (q-1) p^{pq - 1} f(q),$$
which yields $f(q) = q^{q-1}$ and $\nu_q(f(pq)) = q^{q-1}$. Then plugging back into the first equation gives $f(pq) = p^{p-1}q^{q-1}$, and thus $f(p) = p^{p-1}$.

[b][color=#ff9a00]Claim 2.[/color][/b] For all primes $p$, $f(p^e) = p^{p^e - 1}$.

[i]Proof.[/i] Note that
$$f(p \cdot p^{e-1}) = (p-1)p^{(e-1)(p^e - 1)} p^{p-1}.$$
Moreover, all primes $a \mid f(p^e)$ must satisfy $\nu_a(f(p^e)) \geq p-1$ by Condition 1. Evidently $2^{p-1} > p-1$, so $f(p^{e})$ is a power of $p$, which quickly yields the desired.

[b][color=#ff9a00]Claim 3.[/color][/b] $f$ must take on the aforementioned form.

[i][color=#ff9a00]Proof. [/color][/i]We use induction on the number of prime factors (with multiplicity); $f(1) = 1$ is vacuous, and $f(p) = p^{p-1}$ by our first claim. As for the inductive step, if $p$ is the least prime factor of $n$ and $\nu_p(n) = e$, then
[list]
[*] $f(p^e \cdot n/p^e) \mid (p^e-1)(n/p^e)^{n-1} p^{p^e-1}$, and
[*] $f(n/p^e \cdot p^e) \mid (n/p^e - 1)p^{e(n-1)} f(n/p^e)$.
[/list]
Then by the hypothesis, $f(n) \mid p^{p^{e} -1} f(n/p^e)$, yielding $f(n) = p^{p^{e} - 1} f(n/p^e)$ by the first condition.

The end. $\square$

[i]Remark.[/i] The presence of the $(x-1)$ factor in Condition 2 is only there so substituting $x = 1$ doesn't kill the problem.

Let $x=p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n}$ be the prime factorization of $x$. Then we claim that
$$f(x)=\prod_{i=1}^np_i^{p_i^{\alpha_i-1}}$$
Obviously $d(f(x))=x$, now let $p_1,...,p_n$ be the prime factors of $xy$. WLOG assume $p_1,...,p_m$ are also prime factors of $y$, then we have
$$v_{p_i}(f(xy))=p_i^{\alpha_i-1}\leq xy-1=v_{p_i}(y^{xy-1})\leq v_{p_i}((x-1)y^{xy-1}f(x))$$
for eachi $1\leq i\leq m$. If $m+1\leq i\leq n$, then we have
$$v_{p_i}(f(xy))=p_i{\alpha_i-1}=v_{p_i}(f(x))\leq v_{p_i}((x-1)y^{xy-1}f(x))$$
this shows that $f$ also satisfies condition (ii).

Lable the equation
\begin{align}
f(xy)|(x-1)y^{xy-1}f(x)
\end{align}

Firstly since $d(f(p))=p$ we must have $f(p)=q^{p-1}$ for some prime $p$.
[color=#00f]CLAIM 1. [/color]$f(p)=p^{p-1}$ for all prime $p$.
[color=#00f]Proof. [/color]
It suffices to show that $(f(p),p)\neq 1$. Suppose on the contrary that $(f(p),p)=1$. Pick a number $r$ such that $(r,p)=1$. Therefore, sub. $x=p$ and $y=r$ in $(1)$ we have
$$f(pr)|(p-1)r^{pr-1}f(p)$$
Notice that the the g.c.d. of the right hand side and $p$ is 1. Hence $(f(pr),p)=1$. Now swapping $p$ and $r$ we have
$$f(pr)|(r-1)p^{pr-1}f(r)$$
hence
$$f(pr)|(r-1)f(r)             $$
If $p\geq 3$, then by Dirichlet's theorem there exists a prime $s$ with $s\equiv 1\pmod p$. Let $r=s+1$, then $(r,p)=1$. Hence
$$f(pr)|sf(r)$$
But then
$$pr=d(f(pr))\leq d(sf(r))\leq d(s)d(f(r))=2r$$
which is a contradiction since $p\geq 3$. In particular, $f(3)=9$. Therefore, suppose $(f(2),2)=1$, we have
$$f(2\cdot 3)|(3-1)f(3)=18$$
Since $d(f(6))=6=d(18)$ we must have $f(6)=18$. Now sub $x=2$, $y=3$ in $(1)$ we have
$$18=f(6)|3^5f(2)$$
Hence $(f(2),2)\neq 1$, contradiction. $\blacksquare$

[color=#00f]CLAIM 2.[/color] $f(p^n)=p^{p^n-1}$ for all positive integer $n$ and prime $p$.
[color=#00f]Proof. [/color]The case $n=1$ is exactly CLAIM 1. Now assume $n\geq 2$. Sub. $x=p$ and $y=p^{n-1}$ in $(1)$
We have
$$f(p^n)|(p-1)(p^{n-1})^{p^n-1}p^{p-1}$$
Let $q=(p-1,f(p^n))$, $r=\frac{f(p^n)}{q}$, then we have $(d,r)=1$. It suffices to show $q=1$. Otherwise we have $2\leq d(q)\leq p-1$. Moreover
$$p^n=d(f(p^n))=d(q)d(r)$$
Hence $p^n$ has a factor smaller than $p-1$ and larger than $d(q)$, contradiction.

Now we put together CLAIM 1 and CLAIM 2 to prove the case $n=1$.
Now let $k=p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n}$. WLOG assume $p_1<p_2<...<p_n$
[color=#00f]CLAIM 3. [/color]$v_{p_i}f(k)\leq p_i^{\alpha_i}-1$
[color=#00f]Proof. [/color]sub. $x=p_i^{\alpha_i}$ and $y=\frac{k}{x}$ into $(1)$. Then
$$f(k)|(x-1)y^{k-1}p_i^{p_i^{\alpha_i}-1}$$
Notice that $((x-1)y^{k-1}, p_i)=1$, this completes the proof of the claim. $\blacksquare$

Therefore, using CLAIM 3 and letting $x=p_1$ and $y=\frac{k}{p_1}$ we have
$$f(k)|(p_1-1)\prod_{i=1}^np_i^{p_i^{\alpha_i-1}}$$
We use the same trick as in CLAIM 2, let $q=(f(k),p_1-1)$ and $r=\frac{f(k)}{q}$. Suppose on the contrary that $q\neq 1$, then
$$k=d(f(k))=d(q)d(r)$$
Since $d(q)\leq q\leq p_1-1$. This implies that $k$ has a prime factor less than $p_1$ which is a contradiction. Hence $q=1$. This implies
$$f(k)|\prod_{i=1}^np_i^{p_i^{\alpha_i-1}}$$
Since $d(\prod_{i=1}^np_i^{p_i^{\alpha_i-1}})=k$, we must have
$$f(k)=\prod_{i=1}^np_i^{p_i^{\alpha_i-1}}$$
as desired.

[hide=Solution]We are given $d(f(x)) = x$, $f(xy)|(x - 1)y^{xy - 1}f(x)$ $\forall$ $x$, $y$ $\in$ $\mathbb{Z}^+$. We claim that the only solution is \[f(n) = p_1^{p_1^{\alpha_1} - 1}p_1^{p_2^{\alpha_2} - 1} \cdots p_k^{p_k^{\alpha_k} - 1}\] where $n = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ is the prime factorization of $n$ (In particular, $f(1) = 1$).

First, we show that this function works. We have $d(f(n)) = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k} = n$, and for any prime $p$, if $p \not | y$, then \[v_p(f(xy)) = p^{v_p(xy)} - 1 = p^{v_p(x)} - 1 = v_p(f(x)) \le v_p((x - 1)y^{xy - 1}f(x))\] Otherwise, if $p|y$, then \[v_p(f(xy)) = p^{v_p(xy)} - 1 \le xy - 1 \le (xy - 1)v_p(y) \le v_p((x - 1)y^{xy - 1}f(x))\]  This implies $f(xy)|(x - 1)y^{xy - 1}f(x)$ $\forall$ $x$, $y$ $\in$ $\mathbb{Z}^+$, so this function is indeed a solution.

We now show that no other functions work. First, note that since $d(f(1)) = 1$, $f(1) = 1$.

[b]Lemma I:[/b] $\forall$ $x > 1$ $\in \mathbb{Z}^+$, all prime divisors of $f(x)$ also divide $x$. Moreover, $f$ is a multiplicative function.

[b]Proof:[/b] Let $y = x^2 + 1$, $x > 1$. Then, $gcd(x, y) = gcd(x - 1, y - 1) = 1$. We know that $f(xy)|(x - 1)y^{xy - 1}f(x)$, and switching $x$ and $y$, we also have $f(xy)|(y - 1)x^{xy - 1}f(y)$, so \[f(xy)|gcd((x - 1)y^{xy - 1}f(x), (y - 1)x^{xy - 1}f(y))\] Additionally, \[gcd((x - 1)y^{xy - 1}f(x), (y - 1)x^{xy - 1}f(y))|f(y)gcd((y - 1)x^{xy - 1}, (x - 1)y^{xy - 1}f(x))\] but $(y - 1)x^{xy - 1}$  is relatively prime to $(x - 1)y^{xy - 1}$, so \[gcd((y -1)x^{xy - 1}, (x - 1)y^{xy - 1}f(x)) = gcd((y - 1)x^{xy - 1}, f(x))\] therefore \[f(xy)|gcd((x - 1)y^{xy - 1}f(x), (y - 1)x^{xy - 1}f(y)|f(y)gcd((y - 1)x^{xy - 1}, f(x)) = f(y)gcd(x^{x^3 + x + 1}, f(x))\] since $y = x^2 + 1$. However, since \[f(xy)|f(y)gcd(x^{x^3 + x + 1}, f(x))\] it follows that \[d(f(xy)) = xy \le d(f(y)gcd(x^{x^3 + x + 1}, f(x)))\] but as \[gcd(x^{x^3 + x + 1}, f(x))|f(x)\] we must have \[d(gcd(x^{x^3 + x + 1}, f(x))) \le x\] so \[d(f(y)gcd(x^{x^3 + x + 1}, f(x))) \le d(f(y)) \cdot d(gcd(x^{x^3 + x + 1}, f(x))) \le yx\] with equality only if \[d(gcd(x^{x^3 + x + 1}, f(x))) = x\] Since we must have equality, then \[d(gcd(x^{x^3 + x + 1}, f(x))) = x\] which implies \[gcd(x^{x^3 + x + 1}, f(x)) = f(x)\] so $f(x)|x^{x^3 + x + 1}$, hence  all prime divisors of $f(x)$ also divide $x$.

Now, let $y$ be any positive integer relatively prime to $x$. We have \[f(xy)|gcd((x - 1)y^{xy - 1}f(x), (y - 1)x^{xy - 1}f(y))\] but since $y^{xy - 1}$ is relatively prime to $(y - 1)x^{xy - 1}$, then for any prime $p|y$, \[v_p(gcd((x - 1)y^{xy - 1}f(x), (y - 1)x^{xy - 1}f(y))) \le v_p(f(y))\] hence we obtain \[f(xy)|gcd((x - 1)y^{xy - 1}f(x), (y - 1)x^{xy - 1}f(y))|(x - 1)f(x)f(y)\] Similarly, we can show that $f(xy)|(y - 1)f(x)f(y)$, therefore \[f(xy)|gcd(x - 1, y - 1)f(x)f(y)\] However, since all prime factors of $f(xy)$ also divide $xy$, $f(xy)$ is relatively prime to $gcd(x - 1, y - 1)$, so we find that $f(xy)|f(x)f(y)$ $\forall$ relatively prime $x$, $y$ $\in$ $\mathbb{Z}^+$. It follows that \[d(f(xy)) = xy \le d(f(x)f(y))\] with equality only if $f(xy) = f(x)f(y)$, but we also know that \[d(f(x)f(y)) \le d(f(x))d(f(y)) = xy\] so we must have equality, therefore $f(xy) = f(x)f(y)$ $\forall$ relatively prime $x$, $y$ $\in \mathbb{Z}^+$, so $f$ is multiplicative.

Hence, we have shown that all prime factors of $f(x)$ are also prime factors of $x$, and $f$ is a multiplicative function, as desired $\blacksquare$

From [b]Lemma I[/b], we find that $f(p^k) = p^{p^k - 1}$, where $p$ is any prime and $k$ $\in \mathbb{Z}^+$. Also, as $f$ is multiplicative, we must have \[f(n) = f(p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}) = f(p_1^{\alpha_1})f(p_2^{\alpha_2}) \cdots f(p_k^{\alpha^k}) = p_1^{p_1^{\alpha_1} - 1}p_1^{p_2^{\alpha_2} - 1} \cdots p_k^{p_k^{\alpha_k} - 1}\] $\forall$ $n = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k} > 1$ $\in$ $\mathbb{Z}^+$. Thus, we conclude that $f(1) = 1$, \[f(n) = p_1^{p_1^{\alpha_1} - 1}p_1^{p_2^{\alpha_2} - 1} \cdots p_k^{p_k^{\alpha_k} - 1}\] $\forall n > 1$, where $p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ is the prime factorization of $n$, is the only solution, as desired $\blacksquare$

Let $P(x,y)$ denote the second assertion.At first few observations about $f$:[list]
[*]$d(f(1))=1\implies f(1)=1$
[*]For all odd prime $p$ $d(f(p))=p\implies f(p)=\text{(prime)}^{p-1}$ and $d(f(2))=2\implies f(2)=\text{prime}$

[*]For any odd prime $p$,$P(2,p)$ gives $f(p)|p^{2p-1}f(2)$ and as $f(2)$ is only a prime hence $f(p)=p^{p-1}$
[*]If $f(2)=q$,a odd prime then,$$P(2,q):f(2q)|q^{2q}$$ and $d(f(2q))=2q$ gives $f(2q)=q^{2q-1}$.But$$P(q,2):f(2q)=2^{2q-1}|(q-1)2^{2q-1}q^{q-1}\implies q^{q}|(q-1)2^{2q-1}$$
It is a contradiction,Hence,$f(2)=2$
[/list]

[b][color=#f00]Claim:[/color][/b]For prime $q\nmid n\implies q\nmid f(n)$
[size=100][i]Proof.[/i][/size]FTSOC,assume $q\nmid n$ but $q^r||f(n)$.$p$ is the least prime divisior of $n$.Then $P(p,\frac{n}{p})$ gives:$$q^r||f(p. \frac{n}{p})|(p-1)(\frac{n}{p})^{n-1}p^{p-1}\qquad {(*)}$$
Also,as $d(f(n))=n,$ hence $r+1|n\implies r\ge p-1$.But then,$q^{r}\ge q^{p-1}>p-1$.Contradicting $(*)$,since $gcd(q,(\frac{n}{p})^{n-1}p^{p-1})=1$$\blacksquare$

So from the claim and from $d(f(p^m))=p^m$ we get $f(p^m)=p^{p^m-1}$

Finally,we will prove by induction on $n$ that if  $n=p_1^{a_1}p_2^{a_2}\dots p_r^{a_r}$ then $f(n)=\prod_{i=1}^ r p_i^{p_i^{a_i}-1}$
For $p|n$ with $v_p(n)=r$ we have by $P(p^r,\frac{n}{p^r})$and $P(\frac{n}{p^r},p^r)$:
$$f(n)|(p^r-1)(\frac{n}{p^r})^{n-1}p^{p^r-1}\qquad (1)$$
$$f(n)|(\frac{n}{p^r}-1)p^{r(n-1)}.f(\frac{n}{p^r})\qquad (2)$$

So $f(n)$ devides the GCD of above 2.Also,by the claim we can simply discard any common divisor of $(p^r-1),(n/p^r-1)$ that does not devide $n$.Hence,$f(n)|p^{p^r-1}.f(\frac{n}{p^r})$.But then by size issue on $d(f(n))=n$[and induction hypothesis on $f(\frac{n}{p^r})$ and uniqueness of prime factorisation $f(n)=p^{p^r-1}.f(\frac{n}{p^r})$ $\blacksquare$.

Solved with [b]gabrupro[/b]

The answer is a multiplicative function $f$ defined on primes as $f(p^k) = p^{p^k - 1}$. This can be easily checked to work.

Let $P(x,y)$ denote the second condition given. First, $f(1) = 1$ since $d(f(1)) = 1$ and say $f(2) = c$ for a prime $c$ since $d(f(2)) = 2$. Let $p$ be an odd prime.

[color=#f00][b]Claim 1:[/b][/color] $f(p) = p^{p-1}$ and $c = 2$

[color=#00f][b]Proof:[/b][/color] $P(2, p)$ gives $f(2p) | cp^{2p-1}$ and $P(p,2)$ gives $f(2p) | (p-1)2^{2p-1}f(p)$. Since $d(f(2p)) = 2p$, we must have some prime $q$ dividing $f(2p)$ with $v_q$ at least $p-1$, so this can only be $p$. So we have either $f(2p) = cp^{p-1}$ or $f(2p) = p^{2p-1}$.

But in the latter case, we have $p^{2p-1} = f(2p) | (p-1)2^{2p-1}f(p) \implies p^{2p-1} | f(p)$ meaning $p = d(f(p)) \ge 2p$, impossible. So we have $f(2p) = cp^{p-1}$ for all odd primes $p$.

So we have $cp^{p-1} | (p-1)2^{2p-1}f(p)$ and so $p^{p-1} | f(p)$, which forces $f(p) = p^{p-1}$ for all primes $p$, picking $p = 3$, we have $9c | 64f(3) = 64(9) \implies c | 64 \implies c = 2$, so $f(2) = 2$ as well.$\square$

[color=#f00][b]Claim 2:[/b][/color] $f(p^k) = p^{p^k - 1}$

[color=#00f][b]Proof:[/b][/color] In duck. The base case is $k = 1$, suppose it is true until $k-1$, then we have, from $P(p,p^{k-1})$, that $f(p^k) | (p-1)p^{(k-1)(p^k - 1)}f(p) = (p-1)p^{(k-1)(p^k - 1) + p^{k-1} - 1} = (p-1)p^{kp^k - p^k - k}$. Suppose there existed a prime $q \neq p$ dividing $f(p^k)$, then we must have $q^{v_q(f(p^k))} | p-1$, but since the LHS is at least $2^{p-1}$, it is too big, so this is impossible. So $p$ is the only prime dividing $f(p^k)$ and so $f(p^k) = p^{p^k - 1}$, as claimed.$\square$

[color=#f00][b]Claim 3:[/b][/color] The set of primes dividing $f(n)$ is a subset of the primes dividing $n$

[color=#00f][b]Proof:[/b][/color] Let $n = pm$ such that $p$ is the smallest prime dividing $n$. Suppose there was a prime $q$ dividing $f(pm)$ but not $pm$. Then $P(p,m)$ gives $q^{v_q(f(pm))} | f(pm) | (p-1)m^{pm-1}p^{p-1} \implies q^{v_q(f(pm))} | p-1$ but LHS is again at least $2^{p-1} > p-1$, impossible. So indeed the claim follows.$\square$

[color=#f00][b]Claim 4:[/b][/color] $f$ is multiplicative

[color=#00f][b]Proof:[/b][/color] Let $p$ be a prime dividing $n$ and suppose $n = p^km$ with $p \nmid m$. $P(p^k, m)$ gives $f(n) | (p^k - 1)m^{n-1}p^{p^k - 1}$, so we have $v_p(f(n)) \le p^k -1$, and so since $d(f(n)) = n$ and these are the only primes dividing $f(n)$ by claim 3, we have that $f$ is indeed of the claimed form and hence multiplicative. $\square$.

So $f$ must be indeed of the said form, so we are done. $\blacksquare$

Writeup was pretty annoying ngl but a nice problem nevertheless.

[hide=Answer]
$f(n) = \prod_{i=1}^{r}p_i^{p_i^{\alpha_i}-1}$ where $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_r^{\alpha_r}$.
[/hide]

[hide=solution]
Let $P(x, y)$ denote the second condition of the problem.

[hide=Claim 1]
$f(1) = 1, f(2) = 2$
[/hide]
[hide=Proof]
$d(f(1)) = 1 \implies f(1) = 1$. From $d(f(2)) = 2$ we get that $f(2) = p$ for a prime $p$. Similarly, from $d(f(3)) = 3$ we see that $f(3) = q^2$ for a prime $q$. $P(2, 3)$ gives $f(6) \mid 3^5 \cdot p$. Since $d(f(6)) = 6$, we require either $f(6) = 9p$ or $f(6) = 3^5$. Interchange $2$ and $3$ in the above step to get $f(6) \mid 2^6 \cdot q^2$. This is only possible if $p = 2, q = 3$, implying $f(2) = 2, f(3) = 9$.
[/hide]

[hide=Claim 2]
$f(p) = p^{p-1}$ for any odd prime $p$.
[/hide]
[hide=Proof]
$P(2, p)$ gives $f(2p) \mid 2p^{2p-1} \implies f(2p) = 2p^{\lambda}$, but by the first condition $d(f(2p)) = 2p \implies d(2p^{\lambda}) = 2p \implies 2(\lambda + 1) = 2p \implies \lambda = p-1$ so $f(2p) = 2p^{p-1}$.

Now simply taking $P(p, 2)$ gives $2p^{p-1} \mid (p-1)2^{2p-1}f(p) \implies p^{p-1} \mid f(p)$ but since $d(f(p)) = p$, it is necessary that $f(p) = p^{p-1}$.
[/hide]

[hide = Claim 3]
$f(p^{\alpha}) = p^{p^{\alpha}-1}$.
[/hide]
[hide=Proof]
We proceed by induction on the exponent. Clearly true for $\alpha = 1$. Suppose $f(p^k) = p^{p^k-1}$ for some $k$. Then taking $P(p, p^k)$ gives $f(p^{k+1}) \mid (p-1)p^{p-1}p^{k(p^{k+1} - 1)}$. Suppose a prime $q \neq p$ exists such that $q \mid f(p^{k+1})$. Because of $d(f(p^{k+1})) = p^{k+1}$, we require the exponent ($\beta$) of $q$ to be at least $p-1$ (as $\beta+1$ must divide $p^{k+1}$ and $\beta \neq 0$ by assumption). Therefore $q^{p-1} \mid f(p^{k+1}) \mid (p-1)p^{p-1}p^{k(p^{k+1} - 1)} \implies q^{p-1} \mid p-1$, impossible due to size reasons. Thus, $p$ is the only prime factor of $f(p^{k+1})$ and it follows trivially from condition one that $f(p^{k+1}) = p^{p^{k+1} - 1}$.
[/hide]

[hide=Finish]
Finally we prove that for any $n$, the answer described above is the only possibility. To do this, we proceed by induction on the number of prime divisors of $n$. Clearly it works for $m$ having a single prime divisor (as shown above). Assume it works for all numbers that have at most $k$ prime divisors. Consider a number $m$ that has $k+1$ prime divisors. Let $p$ be its smallest prime divisor. Write $m = p^{\alpha}q_1^{\beta_1}q_2^{\beta_2} \cdots q_k^{\beta_k}$ and we write $\mu = q_1^{\beta_1}q_2^{\beta_2} \cdots q_k^{\beta_k}$ for convenience.

Observing  $P(p, m/p)$ tells us that all prime divisors of $f(m)$ which are not divisors of $m$ must be divisors of $p-1$
Suppose $f(m)$ had a prime divisor other than the prime divisors of $m$, say $s$. Then we must have $s^{q_i-1} \mid f(m)$. But $s^{q_i-1} > p-1$ as $q_i-1 > p-1$. Therefore $f(m)$ has no other prime divisors except for the ones that divide $m$.

Taking $P(\mu, p^x)$ gives $f(m) \mid (\mu - 1)f(\mu)p^{x(m-1)} \implies f(m) \mid \left(\prod_{i=1}^kq_i^{q_i^{\beta_i} - 1} \right) p^{x(m-1)}$. Taking $P(p^x, \mu)$ gives $f(m) | \mu^{m-1}p^{p^x - 1}$. Comparing the maximum powers of primes in the RHS of the two divisibility results, we see that $f(m) \mid p^{p^x - 1} \cdot \prod_{i=1}^kq_i^{q_i^{\beta_i} - 1} $. But observe that $p^{p^x - 1} \cdot \prod_{i=1}^kq_i^{q_i^{\beta_i} - 1}$ is the only number $t$ that satisfies $t \mid p^{p^x - 1} \cdot \prod_{i=1}^kq_i^{q_i^{\beta_i} - 1}$ and $d(t) = m$, So we are done!
[/hide]
[/hide]

[hide = Side Note]
[quote=L567]
[color=#00f][b]Proof:[/b][/color] In duck.
 [/quote]
Nice :D
[/hide]

This is a shortened version of the official solution that I found after reading the official solution. The main thing I will do here is directly reducing the problem to showing that $p \nmid n$ implies $p \nmid f(n)$. In this solution, the exact values $\nu_p(f(n))$ will not be that much important.

--------------------

The answer is
\[ f\left(\prod_{i = 1}^k p_i^{a_i}\right) = \prod_{i = 1}^k p_i^{p_i^{a_i} - 1} \]
for all distinct primes $p_1, \ldots, p_k$ and positive integers $a_1, \ldots, a_k$.

--------------------

One can directly check that this function works. The equality $d(f(x)) = x$ follows by the formula for number of divisors in terms of prime factorization. The second condition follows, for example, by checking $p$-adic valuations at each prime $p$. In fact, $f(xy)$ divides $y^{xy - 1} f(x)$ for any $x, y \in \mathbb{N}$.

For the converse, it suffices to show that for any $p$ prime and $n \in \mathbb{N}$,
\[ \nu_p(f(n)) \leq p^{\nu_p(n)} - 1. \]
Then the condition $d(f(n)) = n$ will force equality at each prime since $\nu_p(k) + 1 \mid d(k)$ for any $k \in \mathbb{N}$ and $p$ prime.

First, if $p$ divides $n$, take $x = p^{\nu_p(n)}$ and $y = n/x$. Then $p$ does not divide $x - 1$ and $y$, so the second condition implies
\[ \nu_p(f(n)) \leq \nu_p(f(x)) = \nu_p(f(p^{\nu_p(n)})) \leq d(f(p^{\nu_p(n)})) - 1 = p^{\nu_p(n)} - 1. \]
If $p$ divides $n$, the inequality is equivalent to saying that $p$ does not divide $f(n)$. Thus, it now remains to show that $p \nmid n$ implies $p \nmid f(n)$.

We start by showing that $f(p) = p^{p - 1}$ for any $p$ prime. All we actually need is that the only prime divisor of $f(p)$ is $p$. Since $d(f(p)) = p$, $f(p) = q^{p - 1}$ for some $q$ prime. In particular, $f(2)$ is prime. We just need to show that $q = p$.

If $p$ is odd, then the second condition implies that $f(2p)$ divides $p^{2p - 1} f(2)$ and $(p - 1) 2^{2p - 1} q^{p - 1}$. If $q \neq p$, then $p \nmid f(2p)$ and thus $f(2p) \mid f(2)$. But the first property implies $f(2p) > 1$. Since $f(2)$ is prime, we get $f(2p) = f(2)$; a contradiction since the first property implies that $f$ is injective.

For $p = 2$, the second property implies that $f(6)$ divides $3^5 f(2)$ and $(3 - 1) 2^5 f(3) = 2^6 3^2$. If $f(2)$ is odd, then $f(6) \mid 9$. But then $6 = d(f(6)) \leq d(9) = 3$; a contradiction. Thus, $f(2) = 2$.

Finally, we show that $p \nmid n$ implies $p \nmid f(n)$.
Let $q$ be the smallest prime divisor of $n$. Clearly, $q \neq p$, so $\nu_p(f(q)) = 0$. Now plug $x = q$ and $y = n/q$ into the second property. Since clearly $p \nmid y$, we have
\[ \nu_p(f(n)) \leq \nu_p(q - 1) + \nu_p(f(q)) = \nu_p(q - 1) < q - 1. \]
On the other hand, $\nu_p(f(n)) + 1$ divides $d(f(n)) = n$. Since $\nu_p(f(n)) + 1 < q$, we necessarily have $\nu_p(f(n)) = 0$. Thus $p \nmid f(n)$, as desired.


Now I get "Alcumus is currently undergoing maitenence". Is it really? If so, what is being changed?


Find all polynoms with real coeficients, that solve the equation:      P(x)P(x+1)=P(x^2)

MY solution goes like that:
At first we check, that the polynominal P(x)=0 is a solution.
Now let us consider P(x)=a(n)x^n +a(n-1)x^(n-1)+......+a(1)x+a(0)
If we compare the coeficients,by each x^n.....and we conclude, that a(n)=1.....in other words, we know that the sistem of
a(i) has a unique solution for each natural n.
Now let us asume, that 0 and 1 are not solutions of P(x)=0 and n is odd, than P(x) has at least one real root.
Than we can see if P(a)=0 , than P(a^2)=0,P(a^4)=0......and we conclude that P has infinitely many real roots, which is imposible, for a polynominal.
Now we know, that P isn`t odd, and we can easily check, that the polinom P(x)=x^k(x-1)^k , n=2k is a solution of the given equation. And because we know that for every n there exsist excactly one polinom, those are all the solutions of this problem.

Case 1 $ \tex{degP} > 0$
The first prove that $ \tex{degP}\equiv 0 (\mod 2)$
Use lemma :
[u]1.[/u] If $ h(x),g(x)$ is solution then $ h(x)g(x)$ is also solution.
[u]2.[/u] For each n there exist at most one $ P(x)$ has degree n satisfy condition.
Case 2 : $ p(x)\equiv c$ then
$ c\in\{0,1\}$

If the polynomial has some complex root $ a$ than it has infinitely many complex roots $ a^2,a^4,a^8 etc.$ which means infinite degree. contradiction.

Therefore $ a\equal{}0,1$ are the only possible roots of $ P(x)$ :lol:

[quote="Jure the frEEEk"]If the polynomial has some complex root $ a$ than it has infinitely many complex roots $ a^2,a^4,a^8 etc.$ which means infinite degree. contradiction.

Therefore $ a \equal{} 0,1$ are the only possible roots of $ P(x)$ :lol:[/quote]
Why $ a,a^2,a^4$...are diffrerent?for example if $ a \equal{} i$ then $ \{a,a^2,a^4,a^{16}...\} \equal{} \{i, \minus{} 1,1\}$

[quote="primoz2"]Find all polynoms with real coeficients, that solve the equation:      $ P(x)P(x \plus{} 1) \equal{} P(x^2)$[/quote]
if $ P\equiv constant$ then $ P\equiv 0\ or\ 0$.
if $ deg(P) > 0$
$ \forall a\in S(P) \equal{} \{x\in\mathbb{C}: \ p(x) \equal{} 0\}$
$ \{a^{2^n}: \ n\in\mathbb{N}\}\cup \{(a \minus{} 1)^{2^n}: \ n\in\mathbb{N}\}$ is finite gives $ \{|a|,|a \minus{} 1|\}\in\{0;1\}$ so $ a \equal{} e^{\frac {\pm i\pi}{3}},0\ or\ 1$
so $ S\subset \{0,1,e^{\frac {\pm i\pi}{3}}\}$
then $ {\exists b,c,d,h\in\mathbb{N}: \ P(x) \equal{} x^b(x \minus{} 1)^c(x \minus{} e^{\frac {i\pi}{3}})^d(x \minus{} e^{\frac { \minus{} i\pi}{3}})^h}$
$ P(x)P(x \plus{} 1) \equal{} P(x^2)$ gives $ b \equal{} c$ and $ d \equal{} h \equal{} 0$
so $ P(x) \equal{} (x(x \minus{} 1))^b$

[quote="Jure the frEEEk"]If the polynomial has some complex root $ a$ than it has infinitely many complex roots $ a^2,a^4,a^8 etc.$ which means infinite degree. contradiction.

Therefore $ a \equal{} 0,1$ are the only possible roots of $ P(x)$ :lol:[/quote]

ah i tought it aint that simple  :blush: anyhow it stil holds because:
if $ a$ is a complex root other than $ 0,1$ than $ a^2$ and $ (a \minus{} 1)^2$ are also roots therefore
if there is a complex root $ a$ then there are infinitely many roots $ a^2,a^4,a^8 etc.$ except if $ |a| \equal{} 1$. but if $ |a| \equal{} 1$ than $ |a \minus{} 1|$ isn't equal to $ 1$. therefore we have infinitely many roots $ (a \minus{} 1)^2,(a \minus{} 1)^4,(a \minus{} 1)^8,etc$ except if $ a \equal{} \frac {1}{2}\pm\frac {\sqrt3}{2}i$ but than $ (a \minus{} 1)^2$ is a root and consequently $ (a \minus{} 2)^4$ is a root with $ |a \minus{} 2|$ not equal to $ 1$. again infinitely many roots.

the only possible roots are $ 0,1$. everything else is easy now

Why does (a-1)^2 has to be a root?? I dont think this is necesary,because if a is a root it doesnt mean tat also a-11 has to be a rott.  We know just, that if a is a root it follows that a^2 is a root.

to answer [b]primoz2[/b]

Let $ a$ be a root of $ P$, then

(1)  $ P(a^2)\equal{}P(a)P(a\plus{}1)\equal{}0\Longrightarrow a^2$ is a root and
(2)  $ P((a\minus{}1)^2\equal{}P(a\minus{}1)P(a)\equal{}0\Longrightarrow (a\minus{}1)^2$ is a root


AMC
USA(J)MO
USAMO
AMC 12
AMC 12 A
AIME
geometry

Alright guys, don't clutter the board, keep it in here.

Edit: please vote only if you took the 12 A, we're trying to get the USAMO index "curve" here. Thanks.

amc12a was hard haaha

cant wait for the B XP

hmm...
i don't think it was that hard...
i would give it a thumbs up!
WOOOT! :D

(i think it would be a good idea if you could make a Poll...or maybe that that would be another thread...)

GROAN! Sigh... missed two in the first 10... 126.

well, I took the 10, it was my second to last chance, as I'm a sophomore
and I have to say, I think there was an overflow of counting questions on the 10...

Hmm...I solved 17 problems (1-16 and 18) in 45 minutes and then didn't get anything else...

I answer 20 questions (guess on one, it happens that I got it wrong...) so I get 126.5 on AMC 12

If I took the B also, do they pick the highest score out of the two???

yes, they take the higher score, nothing wrong with 126.5 tho
get like double digits on AIME, and you're a lock for USAMO

[quote="jackb1115"]Wow ... they opened the forum already!

Here are my thoughts.  Questions 1-15 were easier than usual.  Questions 16-20 were a little less approachable than those of previous years, especially 17, 19, 20.  Eighteen was basically trivial after you saw the trick, but I think the notation scared some people off.

21 through 25 were about the same difficulty as usual.

In light of these thoughts, I think we will see more people with scores in the 112 - 130 range and less in the 130 and up range.

Other people's thoughts?

JB[/quote]

Yeah, I was surprised at the difficulty level on the first 15 and the last 5 (such a gap)...

The angry thing is, 5 min after I walk out I solved 3 problems... :mad:  :mad:

I answered
1-19, 21, 24 and got 15 wrong AFAIK.

thanks for the Poll!

i solved confidently 23 problems (all except for 19 and 22). i assumed something for #22 without knowing how to show its true, but got it right!
and 19 took me the most time to solve...

but i got a perfect ( at least that's what i think after checking my answers twice with the key)

hahah wow u beast

i got like 1-14 right and stupidly missed 15 heh

umm and yea missed a few others...

i got 20 right 3 blank and 2 wrong so 127.5

till this point i know another person from my state who got a 150, but that was no suprise to me, since he has a USAMO HM last year :D

Just in the 130-146.5 range :D

131!

Blanked 17 (d'oh!) and 23 (d'oh)

Missed 15&16 OMFG !@#%!@#!@%!@

I came into it thinking "If I get 131, Hallelujah" (sp?). After taking the test and going over my dumb mistakes, I think I could've gotten a perfect... which I would've cut off a finger for (j/k).

IMO really easy year, of course, it's only my second official AMC 10 ever.

The problems aren't drawn to scale, are they??

they are definitely NOT drawn to scale
a great example is #17 on this year's AMC 10. the desired area was in fact a square, not the rhombus in the picture

for most problems tho, learning how to work off of a rough sketch is a really important skill, especially when time is so crucial as on the AMC's

drawing accurate diagrams with protractor/compass is probably best reserved for olympiad/AIME problems(generally when time isn't that much of a pressure), where a crucial fact can be seen from the diagram, and you set out to rigorously prove that it is true

edit: heh took some later posts into accont

[quote="krustyteklown"]drawing accurate diagrams with protractor/compass is probably best reserved for olympiad problems, where a crucial fact can be seen from the diagram, and you set out to rigorously prove that it is true[/quote]

What?? No way! Always draw freehand! It's definitely the coolest way to go... ;) oh wait maybe you're talking about trying to maximize your score, in which case, I dunno.... (I think I'm actually better at freehand than at compass though, because those compasses slip so easily :()

wow, okay, i had to keep looking at the first question, that was like 3rd grade.   wow.

i have something to add: Putnam problems are much harder than these questions, no contest.

[quote="rrusczyk"][quote="krustyteklown"]
drawing accurate diagrams with protractor/compass is probably best reserved for olympiad problems, where a crucial fact can be seen from the diagram, and you set out to rigorously prove that it is true[/quote]

Take that skill into the AIME, too.  Every once in a while they mess up and give you this out.  I'm an example of this - my first year taking the AIME, I hit the cut-off exactly to qualify for the USAMO.  I got one of the AIME questions right by drawing the diagram precisely and measuring the length the question asked for.  The test writers don't make this mistake often.  Curiously, there were no perfect scores that year, and only one 14.  He missed this question (and was most put out when I told him how I did it :) ).[/quote]

Oh wow!  Man...why didn't I think of this???  An integral answer from 0-999...heh.

But there probably won't be a question like this on the 2006 AIME eh?

[quote="1234567890"]You have to account for the pressure while taking it. I can solve pretty much all AMC problems given enought time, but only got 126.5 on the actual thing.[/quote]I do better with pressure. That's just something I've learned to do after a few months of Academic Team practice. :)

However, I'm not so great at math right now, so...  :roll:

[quote="tongos"]i have something to add: Putnam problems are much harder than these questions, no contest.[/quote]

Uh, yeah.  I'd say so :P

Time really is a large factor on the AMC.  I'll agree that if I did AMC practice tests on my own I would probably score lower than how I do/have done on the real thing.  But when solving AMC problems at my leisure I can do just about all of them.  I think that was the point...it's much easier to do AMC problems when the pressure is of as opposed to working with only, say, 5-10 minutes left.

[quote="Boy Soprano II"]I wish I had known about AMC and AoPS in middle school.  Life would be so different.[/quote]

Me too... I wish I had discovered AoPS sooner especially.  I only fully realized its scope after bombing the AMC 12A on the 31st.  And my school will not administer the B  :mad:

I guess there's always next year, but unfortunately (yes, this is lame and cliche) I won't be able to report next year's score to colleges since I'm already a junior.  I really wish I could take the 12B as well... seeing as to the fact that I got 2 questions wrong in the first 10 and forgot to grid-in one of my (correct) answers :oops:.  Way to back up my score from last year (126.5 sans any studying)... compared to the rest of my school, the next closest score on the AMC 10 was more than 15 points below mine.  This year I know of 2 not-very-good-at-these-contests people that scored higher than me  :(

Speaking of questions wrong... I have issues with pizza questions.  I got that one wrong on the AMC  :ninja: <--- hiding... then missed another pizza question on yesterday's embarrassingly terrible National Assessment.  I put 9 slices of pizza in the AMC problem and answered the number of people who liked only olives on the National Assessment  :mad:

I thought 23 and 24 were too easy for 23 and 24. And 25 was trivialized by an 89. Other than that the log function that made circles was frustrating becuase people who ignored the fact that logs might be negative (they aren't of course, but it requires some time) were rewarded because they didn't have to take the time to check. I thought this AMC looked harder than others but was in reality easier.

my school won't take the time to administer the AMC12B.  Is it possible to register with another school, and take it there?  I only got a 115, because I was being conservative, but I want to go all out on the B test.  I hope I can just take it at another school.  I hope its legal.

EDIT: sorry about the off-topic-ness   :oops:

i think you can

contact the Contest Manager of the closest location that you can take it at ASAP and ask them what to do

Uh, from what I heard, friday was the last day for registering through another school. Uh, I still suggest you try to contact AMC to find out whether or not you can still take it.

[quote="K81o7"]
On $\sqrt{120-\sqrt{x}}$, I forgot about 0...
[/quote]

Me too. I went from a 125 on the 10 last year (8th grade) to a 112.5 on the 12 this year. I could have done better, but I suppose I'm satisfied.


Let $ f(x)$ be a polynomial in $ x$ with integer coefficients such that for 5 distinct integers $ a_1,a_2,a_3,a_4,a_5$ we have

$ f(a_1) \equal{} f(a_2) \equal{} f(a_3) \equal{} f(a_4) \equal{} f(a_5) \equal{} 2$.

Show that there does not exist an integer $ b$ such that $ f(b)\equal{}9$.

$ b\minus{}a_i$ has to be a divisor of $ 7$, which is feasible iff $ b\minus{}a_i \equal{} 7, \minus{}7$ or $ 1, \minus{}1$.

Polynomial $ P(x) \in \mathbb{Z}[x]$ takes values $ \pm1$ at three different integer points. Prove that it has no integer zeros.


Before the competition starts, is it OK if you make boxes for each problem on a sheet of paper to organize your work?

It's against the rules but if no one sees then...

At nationals last year we asked one of the Mathcounts people and they said we can't do it until the competition starts. But we did it anyways :P

At chapter last year they said it was ok but at states they said you couldn't. Ask the people in charge, which shouldn't be too hard. leewongjao I wouldn't be admitting that...

[quote="math154"]No, it's not against the rules. You just can't use your own scratch paper--you have to use the paper provided. After they distribute it, it is not illegal to write on it.[/quote]

You can't use your own scratch paper??   Luckily I wasn't caught... :D


\[ \begin{gathered} {\text{(x \plus{} y \plus{} z) (xR}}^2 _1 {\text{ \plus{} yR}}^2 _2 {\text{ \plus{} zR}}^2 _3 {\text{)}} \hfill \\
{\text{ }} \geqslant {\text{yza }}^{{\text{2 }}} {\text{ \plus{} zxb }}^{\text{2}} {\text{ \plus{} xyc }}^{\text{2}} {\text{ ,}} \hfill \\
{\text{where x, y}}{\text{. z are arbitrary real numbers and R}}_{\text{1}} \hfill \\
{\text{R }}_{\text{2}} {\text{ , R}}_{\text{3}} {\text{ are the distances from an arbitrary point}} \hfill \\
{\text{P to the vertices A, B, C, respectively}}{\text{. of the}} \hfill \\
{\text{triangle ABC}} \hfill \\
\end{gathered}\]

[quote="rt_08"]i think its  the same question given by apratimdefermat[/quote]

i know that  :D
but nobody replied there so i copied Apratimdefermat's post here as the inequality is rather interesting!~~~


analytic geometry
geometry
trapezoid
angle bisector

Jest dany trojkat $ABC$. Rysujemy linie laczaca punkty w ktorych dwusieczne katow $ABC$ i $ACB$ przecinaja przeciwlegle sciany trojkata. Przez punkt przeciecie tej prostej z dwusieczna kata $BAC$, rysujemy prosta rownolegla do $BC$. Niech ta prosta przecina $AB$ w $M$ i $AC$ w $N$. Udowodnij, ze $2MN = BM + CN$

P.S. Zapodalem prosciutka geometrie, bo w koncu forum trzeba rozruszac  :)

a to podpowiedz z czego tu korzystać  :)  bo z moją geometrią na poziomie gimnazjum trudno cokolwiek zauważyć  :D

odświeżam dość stary wątek, bo może Cinek dalej nad tym myśli :) można wszystko przeliczyć korzystając z tw. o dwusiecznej i z podobieństwa. A może jest jakiś ładniejszy sposób?

Could someone translate the problem to english :?:

Sure.
There is a given triangle $ABC$. We draw a line connecting points in which angle bisectors of $\angle ABC$ and $\angle ACB$ intersect the opposite sides of triangle. From a point of intersection of this line and angle bisector of $\angle BAC$ we draw line which is parallel to line $BC$. This line intersects $AB$ in $M$ and $AC$ in $N$. Prove that: $2MN = BM+CN$

[quote]In $\triangle ABC,$ let $V_a,V_b,V_c$ be the feet of the internal angle bisectors of $\widehat{A},\widehat{B},\widehat{C}.$  Let $P$ be the intersection of $AV_a$ with $V_bV_c.$ The parallel to $BC$ through $P$ cuts $AB,AC$ at $ M,N.$ Then $ 2 \cdot MN \equal{} BM \plus{} CN.$ [/quote]
We use trilinear coordinates with respect to $ \triangle ABC.$ Thus

$ V_a  (0: 1: 1) \ , \ V_b  (1: 0: 1) \ , \ V_c  (1: 1: 0)$

Hence $V_bV_c \equiv \alpha \minus{} \beta \minus{} \gamma \equal{} 0,$ which means  that the line $V_bV_c$  is the locus of the points whose sum of oriented distances to $AB,AC$ equals the oriented distance to $BC.$ Therefore if $X,Y,Z$ denote the orthogonal projections of $ P$ onto $ BC,CA,AB,$ we have $PY \plus{} PZ \equal{} PX,$ but $PY \equal{} PZ$ $\Longrightarrow$  $PX \equal{} 2 \cdot PZ.$

$[BMNC]=[PBM]+[PCN]+[PBC]=\tfrac{1}{2}PY \cdot (BM+NC)+\tfrac{1}{2}PX \cdot BC.$

But the area of trapezoid $BMNC$ is $[BMNC]=\tfrac{1}{2}PX \cdot (MN+BC) \Longrightarrow$

$PX \cdot (MN+BC)=PY \cdot (BM+NC)+PX \cdot BC \Longrightarrow$

$PX \cdot MN=PY \cdot (BM+CN) \Longrightarrow 2 \cdot MN=BM+CN.$


linear algebra
matrix
inequalities
linear algebra unsolved

Please try this easy but nice problem [not sure if already posted :blush: ]:

If $A \in M_n(R), A = (a_{ij}), \sum_{i,j=1}^n a_{ij}^2 < 1$ then $I_n - A$ and $I_n + A$are inversible.

Well, an one line solution: the sum of the squares of the absolute values of the eigenvalues is smaller than or equal to the sum of the squares of all elements (Schur theorem, already discussed on the forum).

I have found this ugly proof on http://www.epsilon.ro .

of course it is true in any Banach space that if $|x|<1$ then $1+x$ and $1-x$ are invertible.

[quote="spix"]Sorry I`m having difficulties finding that post about Schur inequalities.... and mathworld doesn`t say when the equality occurs... So when does equality occur? :?[/quote]

For matrices which can be diagonalised using an orthonormal basis.

In particular, Hermitian matrices yield equality. (matrices which satisfy $A=A^H$)

[quote="harazi"]Has anyone noticed that it is a trivial consequence of Cauchy-Schwarz inequality?[/quote]

What Cauchy-Schwarz? If the "real" one... then no  :(

I think I've finally seen the light... :lol:
\begin{eqnarray*}
\| Ax \|^2 &=& \sum_{i=1}^n \left\| \left( Ax \right)_i \right\|^2 = \sum_{i=1}^n \left( \sum_{j=1}^n a_{ij} x_j \right)^2
\\ \ &\leq& \sum_{i=1}^n \left( \sum_{j=1}^n a_{ij}^2 \right) \left( \sum_{j=1}^n x_j^2 \right) < \| x \|^2
.\end{eqnarray*}
I'm slow, you see... :o


Determine all triplets $ (a,b,c)$ of natural numbers such that $ a^2 \plus{}b^2\equal{}2^c$

[hide="Remark"] Without loss of generality $ a, b$ are odd.  Then $ a^2 \plus{} b^2 \equiv 2 \bmod 8 \Rightarrow c \equal{} 1$.  Thus all solutions are given by $ 2^{2n} \plus{} 2^{2n} \equal{} 2^{2n\plus{}1}$.

This is by far the most boring base to ask this question about; replacing $ 2$ by $ 5$, for example, gets you a much larger family of solutions. [/hide]

[hide] This is not my own problem,and probably base $ 2$ is to make problem easier.[/hide]

[quote="t0rajir0u"][hide="Remark"] Without loss of generality $ a, b$ are odd.  Then $ a^2 \plus{} b^2 \equiv 2 \bmod 8 \Rightarrow c \equal{} 1$.  Thus all solutions are given by $ 2^{2n} \plus{} 2^{2n} \equal{} 2^{2n \plus{} 1}$.

This is by far the most boring base to ask this question about; replacing $ 2$ by $ 5$, for example, gets you a much larger family of solutions. [/hide][/quote]
i am sorry if it is elementary but what is the reason behind assuming them both to be odd? how do you get the final solution from your work?

Oh, the problem is the very 2004 Kyoto University entrance exam/Humanities

What's the source of your problem, enndb0x?

Let $ n,\ a,\ b\geq 0$ be integers. Consider an equation in $ a,\ b: a^2 \plus{} b^2 \equal{} 2^n\ \cdots(*)$

(1) For $ n\geq 2$, if $ a,\ b$ satisfy $ (*)$, then prove that both $ a$ and $ b$ are even.

Note that we regard the number $ 0$ as even.

(2) Find all pairs of non negative integer $ (a,\ b)$ for $ n\geq 0$.

2004 Kyoto University entrance exam/Humanities

[quote="geniusbliss"]what is the reason behind assuming them both to be odd? [/quote]
If one is even and the other is odd then $ n \equal{} 0$.  If both are even then we can divide by $ 4$.

my doubt was not regarding the parity but how such an assumption can be made?
ok i think i figured it out is this it?
you have assumed them to be odd with an intution and got only one solution and the other case of both even is obvious
i think it was just two cases u took but i got misled by the word assume
again am i right?  :huh:

Often in a sufficiently homogeneous Diophantine we make the simplifying assumption that the numbers involved are relatively prime; this greatly simplifies, for example, solving $ a^2 \plus{} b^2 \equal{} c^2$.  In this case, if $ a, b$ are both even we can divide by $ 4$ and decrease $ c$ by $ 2$.  Thus if we have all the relatively prime solutions then we can recover every solution by multiplying by the appropriate power of $ 2$.


While reading about the synthesis of Periplanone B (a sex pheromone secreted by an American cockroach) I came across this general strategy developed by Schreiber to synthesize large rings. It's quite nice so I think I might post it as a problem.

Now the challenge is to synthesize cyclodecadienone.

1. Let's start with allene and cyclohexanone and carry out a [2+2] Cycloaddition. Now what reaction condition is required?

2. The product obtained is then reacted with the Grignard Reagent vinylmagnesium bromide. It was discovered that this reagent adds primarily to one face of the molecule. Which face is this and why?

3. Now we use $ \ce{KH}$ in 18-crown-6 at $ 25^{\circ}C$. What does this do?

4. Now the molecule undergoes anionic oxy-Cope rearrangement. What is the product? Can you see a region of high structural strain?

5. Using $ \ce{PhCH3}$ at $ 180^{\circ}C$ an electrocyclic ring opening is induced. How many products obtained?

Note: show the products at each stage. This is a very nice technique that can be used to tackle general synthetic problems, namely the total synthesis of complex natural molecules.

[quote]
1. Let's start with allene and cyclohexanone and carry out a [2+2] Cycloaddition. Now what reaction condition is required? [/quote]
do you mean allene + cyclohex-2-enone?

If so, then the reaction solution would have to be irradiated with light since it is a photochemical [2+2] cycloaddition

The product of that reaction, which is a chiral bicyclo compound (don't know how to name it  :maybe: ), would not be very flat, in fact, it would be sort of U-shaped.  For that reason, the Grignard reagent would prefer to attack the carbonyl from the "outside" of the molecule, rather than from the "inside" which is sterically encumbered.

Anyways, that's all I know so far -- I'm interested to see the rest of the synthesis.  Those 2 steps seem reminiscent of Woodward's synthesis of reserpine.

[quote="VARUNARASU"]i know what KH does. it deprotonates the alcohol, and increases the rate of oxy cope rearrangement[/quote]
could anyone explain to me what cope rearrangement i have heard of only cope condensation and elimination!!! whats this??? :roll:

[quote="Hideaway"]
do you mean allene + cyclohex-2-enone?

[/quote]

Yes you are right, I typed the name wrong. You're reasonings are perfectly right but as far as I am aware we refer to the faces as being convex or concave but it doesn't make any difference, well done.

Now the next bit is the interesting part, involving Oxy-Cope Rearrangement. Maybe Wiki it if you don't know what it is.

concave, convex..makes sense!

ok, so KH is used to deprotonate the alcohol, and this speeds up the oxy-cope rearrangement since the starting material, now an alkoxide rather than an alcohol, is destabilized more than the intermediate is (now an enolate rather than an enol).  The 18-crown-6 is simply a phase transfer reagent, which is required since KH is a very polar compound and the alcohol is not.

The product of the oxy-cope rearrangement is another cyclic compound, but with a bridgehead alkene (not sure of naming).  This time a 10-membered ring with, oddly enough, a double-bonded bridgehead carbon.  That last bit seems a bit too extreme...

And for the last step, 2 products are formed: the cis and trans isomer.  The cis isomer can be converted to the more stable trans isomer by irradiation.

that is quite a synthesis, and only 5 reactions...

You seem to interested in advanced organic chemistry. Then try [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=188319]this problem[/url] I posted. And also [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=188315]this one[/url].


Find all monic polynomials $P(x)$ with integer coefficients such that: there exists infinity irrational numbers $t$ satisfying $P(t) \in Z^+$
(where $Z^+$ be set of positive integer numbers).

All the polynomials whose degree is greater than 1.
A few remarks:
If P(x) in $R[x]$ satisfied:P(x) is rational iff x is rational.Then P(x) is a rational linear polynomial:
      P(x)=$ax+b$,a and b are rational.

[quote="dreammath"]If P(x) in $R[x]$ satisfied:P(x) is rational iff x is rational.Then P(x) is a rational linear polynomial:
P(x)=$ax+b$,a and b are rational.[/quote]
The far more general statement by mine is here http://www.mathlinks.ro/Forum/viewtopic.php?t=18474&highlight=resultant


geometry
symmetry
search
power of a point
radical axis
projective geometry
cyclic quadrilateral

In an acute $ \Delta ABC$, $ AC>BC$ and M is the midpoint of AB. Let AP be the altitude from A. Let BQ be the altitude from B meeting AP at H. Let the lines AB and PQ meet at R. Prove that the line RH is perpendicular to CM.

Hint:[hide]
Use Radical Axis Theorem[/hide]

[hide]It's just one application of the following well known lemma:

Let $ ABCD$ be a quadrilateral inscribed in circle $ \omega$.  Let $ AB \cap CD\equal{}E$, $ AC \cap BD\equal{}F$ and $ AD \cap BC\equal{}G$.  Then $ \triangle{EFG}$ is self-polar with respect to $ \omega$.

Proof: Let the tangents to the circle at $ A$ and $ C$ meet at $ H$, and let the tangents to the circle at $ B$ and $ D$ meet at $ I$.  Then $ HI$ is the polar of $ F$.  By Pascal's Theorem applied to quadrilateral $ AABCCD$, the points $ E$, $ G$ and $ H$ are collinear.  By Pascal's Theorem applied to quadrilateral $ ABBCDD$, the points $ E$, $ G$ and $ I$ are collinear.  Hence, $ E, G, H$ and $ I$ are collinear.  Then $ EG$ is the polar of $ F$.  By symmetry, this proves the lemma.

Apply this lemma to cyclic quadrilateral $ AQPB$ and you've got your solution.[/hide]

[quote="hell_ever"]My solution turned out very long.....
what do you mean by self-polar? and what is pascal's theorem? can u post some links where i can look it up?[/quote]

[urlhttp://www.cut-the-knot.org/Curriculum/Geometry/Pascal.shtml]Pascal's Theorem[/url]

[urlhttp://www.cut-the-knot.org/Curriculum/Geometry/PolePolar.shtml]Poles and polars[/url]

A self-polar triangle is one where each vertex is the pole of the opposite side.

See the first problem from

http://www.mathlinks.ro/viewtopic.php?search_id=1390827536&t=46146


f:N - N

f(n+1)>f(n)
f(f(n))=3n for all n.
Evaluate f(2001)

Answer (I can post solution if somebody wants):
[hide]
3816
[/hide]

It has appeared several times before: http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1078531140&t=203163

Myth claims this is from the Tournament of Towns, 1983

Hey, please post the solution for this question. I need it very much!

The solution in those references. My solution is same as those.


Well is there any one out here who has appeared for ZIO 2009 (zonal Informatics Olympiad)
If yes, then how was the paper?? how many were you able to solve ?? and when will the results be out??
 :?:

problem 1 good
problem 2 bad (logicless)
problem 3 O.K.
problem 4 dirty (extreme hard work required)

are these ur answers or are the answers official? the thing is that many of my answers match with these.

Well the Questions will be soon available on the official Website, You can check them out there!!

Aman, you r talking to Nadeem Moidu[bruteforce] a bronze medallist in IOI 2008 for India.
Well , Nadeem, the questions are too long to be remebered and posted. :(    :)

I asked because most of the maths olympiad questions are posted here . ( and informatics questions won't have any diagrams or equations like math , so it should be easier )

Well that is really awesome, I didn't know that!!
Congrats Nadeem

U better start preparing for INOI as u have got all 4 i assume. :D


geometry
perimeter
incenter
trigonometry
inradius
inequalities
area of a triangle

How do you prove that the triangle with least area, for a given incircle, is equilateral?

What I mean is you start with a circle, and then draw a triangle around it, and the one with the smallest area is equilateral.  Also, this is the one with the least perimeter, since A=(1/2)*(a+b+c)*r, if that helps.

[hide="Strategies I would suggest"] Drop the altitudes from the incenter to the triangle.

After that, you might want to use trig and express everything in terms of the angles of the triangle.

Or you could use Pythagoras to express everything in terms of the distances from the incenter to the vertices.   [/hide]

[hide]
For an equilateral triangle with side length $a$, the area is $\frac{a^{2}\sqrt{3}}{4}$ and the inradius is $\frac{a}{2\sqrt{3}}$, so our problem is equivalent to proving that for any triangle with area $K$ and inradius $r$,
\[\frac{K}{r^{2}}\geq 3\sqrt{3}\]
Let the sides of the triangle be $a,b,c$; then by Heron's formula and $K=rs$ ($s$ being the semiperimeter),
\[K=\sqrt{s(s-a)(s-b)(s-c)}\]
\[r^{2}=\frac{(s-a)(s-b)(s-c)}{s}\]
So the inequality reduces to
\[s^{3}\geq 27(s-a)(s-b)(s-c)\]
But $s=(s-a)+(s-b)+(s-c)$, so this is just AM-GM.
[/hide]


Pythagorean Theorem
geometry
algebra unsolved
algebra

A Pythagorean triple is a set of numbers representing the sides of a triangle (a, b & c coming from the Pythagorean theorem a^2 + b^2 = c^2). A good example is 32 + 42 = 52 (9 + 16 = 25) which means that 3, 4 & 5 are the lengths of the sides of a right triangle. Using the formula n^2 + 3^2 = x^2, find 2 values of n and 2 values of x that satisfies the formula (which is not n = 4 and x = 5)

Using the pythagorean triple finder formula, you can plug 3 into two of the three expressions and then guess-and-check. But how?

also, is there a better way to do this?

Well, $ n^2 \plus{} 3^2 \equal{} x^2$ can be written as $ (x \plus{} n)(x \minus{} n) \equal{} 9$; considering the factors of $ 9$ we can see that the only possibility is $ x \plus{} n \equal{} 9,x \minus{} n \equal{} 1$ (since $ x,n$ are positive) and this implies $ (x,n) \equal{} (5,4)$ is the only possible pair.