Find all natural numbers $n$ for which $n = n'$

Question

The following was a question in the final of the Flanders Mathematics Olympiad 2017:

For each natural number $n$, $n'$ is defined as follows:

• $0' = 1' = 0$

• If $n$ is prime, then $n' = 1$

• If $n = ab$, then $n' = a'b + ab'$

Find all natural numbers $n$ for which $n = n'$.

Since I have no background in theoretical mathematics, I generally try to solve problems like this intuitively. For instance, by distinguishing several cases:

• If $n = p$ with $p$ prime, then $n'= 1 < p = n$

• If $n = p q$ with $p$ and $q$ prime, then $n' = 1 \cdot p + q \cdot 1 = p + q < p q = n$

• If $n = p r$ with $p$ prime and $r \in \mathbb{N}$, then: $$n = n' \iff pr = r + p r' \iff r' = \frac{p-1}{p}r$$ Since $r' \in \mathbb{N}$, we find that $p | r$. We can thus redefine $r$ so that $n = p^2 r$: $$n = n' \iff p^2r = pr + p(r + p r') \iff pr = 2r + pr' \iff r' = \frac{p-2}{p}r$$ Again, we find that $p|r$. This goes on until we find that $r' = \frac{1}{p}r$, which, since $0' = 1' = 0$, can only hold for $r = p$. We thus conclude that for $n$ to equal $n'$, $n$ must equal $p^p$ with $p$ prime.

Would this answer be adequate enough? If not, is there a way to turn it into a more rigorous and mathematically sound proof? Are there any alternative approaches to solve this problem?

Answer 1

Your proof is good and you found all nonzero numbers $n$ with the property that $n'=n$.

A different approach. All integers considered here are positive, as for $n=0$ we have nothing to prove.

Lemma. $(abc)'=a'bc+ab'c+abc'=abc\left(\dfrac{a'}{a}+\dfrac{b'}{b}+\dfrac{c'}{c}\right)$.

Proof. Easy. $\square$

This easily extends by induction to any number of factors.

Lemma. $(a^k)'=ka^{k-1}a'$.

Proof. If $k=1$, this is obvious. Suppose it holds for $k$; then $$ (a^{k+1})'=(aa^k)'=a'a^k+a(a^k)'=a'a^k+aka^{k-1}a'=(k+1)a^{k-1}a'\tag*{$\square$} $$

Now suppose $n>1$ and decompose it as $n=p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}$ (with distinct $p_1,p_2,\dots,p_r$) to get $$ n'=(p_1^{k_1}p_2^{k_2}\dots p_r^{k_r})'= n\sum_{i=1}^r \frac{(p_i^{k_i})'}{p_i^{k_i}}= n\sum_{i=1}^r \frac{k_i}{p_i} $$ If $n=n'$, we obtain $$ p_1p_2\dots p_r=k_1p_2\dots p_r+p_1A $$ for some integer $A$, which implies $p_1\mid k_1$. Similarly, $p_i\mid k_i$ also for $i=2,\dots,r$. Set $k_i=p_ih_i$. Then we get $$ \sum_{i=1}^r h_1=1 $$ so $r=1$ and $h_1=1$.

Conversely, if $n=p^p$ with $p$ prime, we have $n'=pp^{p-1}p'=p^p=n$.

Answer 2

In my perspective, you must also prove for $n=ab$ with $a,b \in \mathbb{N}$.

Now by FTA, $$ n = ab $$ then we can also write $a$ as $$ a =p_{1}^{q_{1}} ... p_{m}^{q_{m}}$$ so $$ n = (p_{1}^{q_{1}} ... p_{m}^{q_{m}})b $$ we can take one from $p_{i}^{q_{i}}$, let this $i=m$ and get $$ n = p_{m} (p_{1}^{q_{1}} ... p_{m-1}^{q_{m-1}}p_{m}^{q_{m}-1})b = p_{m} c$$ with $c = (p_{1}^{q_{1}} ... p_{m-1}^{q_{m-1}}p_{m}^{q_{m}-1})b \in \mathbb{N}$.

Using your result, if $$n = pr, \:\:\: p \in \mathbb{P}, \:\:\: r \in \mathbb{N}$$

then $n = n' \iff n = p^{p}$.

So i think this may be enough.