I've been studying elementary number theory for a while now, and when it's possible, to wit somewhat elegant, I love using induction. I was solving the following problem: "if m$\phi$(m) = n$\phi$(n), for positive integer m and n, prove that m=n".
The problem itself is not that hard, but I think I had an intuition that makes the problem quite trivial to solve, but I'm not so sure that it is formally rigorous. So, the base case is trivial, and the induction says that if we have multiply m by a prime p and n by a prime q, then we have those prime being equal. Clearly the problem is trivial given that this intuition is correct.
I tried to give reasons to all of this, and I came up with the fact that if the given equation has a pair of different integer as a solution, they clearly have to differ from at least a prime (meaning its power). But if they have some prime in common, we can easily get rid of them and use the fact that for smaller integers the result is demonstrated; clearly they cannot differ from all prime for if a prime with an exponent greater than the unit divides an integer, it also divides its Euler's function.
The proper way to solve this involves finding the largest prime $p$ such that $p \mid m \phi(m) = n \phi(n)$, if such a prime exists. Let $k$ be the largest natural number such that $p^k \mid m \phi(m) = n \phi(n)$. Conclude $k$ is the largest $k$ such that $p^k$ divides $m$, and also the largest $k$ such that $p^k$ divides $n$. Show that $(n/p^k) \phi(n / p^k) = (m / p^k) \phi(m / p^k)$, and apply the inductive hypothesis.
You need to let $p$ be the largest such prime for things to work out.