# On a rather strange induction [duplicate]

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.

• Please read carefully the linked common proofs. For multiplicative functions / problems it is natural to use prime factorizations in the induction (e.g see here and here and here). Here in the inductive step we compare the powers of the largest prime in both because $\phi$ of all smaller primes is coprime to it, so they don't interact with it, making the comparison easy. Commented Feb 17, 2023 at 22:57
• Such inductions that peel off a prime (power) factor are not only not "strange" but are rather quite common in number theory, e.g. here is one such (simple) proof of a powerful result (which Weil views as the essence of Fermat's method of infinite descent). And of course this method is also used in common proofs of the Fundamental Theorem of Arithmetic (existence and uniqueness of prime fractorizations of integers). Commented Feb 17, 2023 at 23:06

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.