0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Commented Feb 17, 2023 at 22:57
  • $\begingroup$ 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). $\endgroup$
    – Bill Dubuque
    Commented Feb 17, 2023 at 23:06

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I've found this solution but I was more interested in knowing whether my conclusioss were correct or not. Firstly because I found the method rather amusing, but also because it's faster and I consider it to be efficient in some problem. Thanks a lot for your help $\endgroup$
    – temp
    Commented Feb 17, 2023 at 22:08
  • $\begingroup$ Please strive not to post more (dupe) answers to dupes of FAQs, cf. recent site policy announcement here. $\endgroup$
    – Bill Dubuque
    Commented Feb 17, 2023 at 22:13
  • $\begingroup$ @BillDubuque I do not view this question as a dupe, since it asks whether a particular induction scheme can be applied to solve the problem, not necessarily how to solve it in general. My answer simply noted that for the simplest solution to the problem, the provided induction scheme doesn’t work since it doesn’t stipulate that the prime is the largest. But I will keep your suggestion in mind. $\endgroup$
    – Mark Saving
    Commented Feb 17, 2023 at 22:21
  • $\begingroup$ @MarkSaving What you wrote in this answer is already written many times in the linked dupe answers (and the dupes linked there). Please don't post duplicate answers - it is very bad for site heatlh. $\endgroup$
    – Bill Dubuque
    Commented Feb 17, 2023 at 22:24

Not the answer you're looking for? Browse other questions tagged .