Hacker News Reader

Comment by bustermellotron | Hacker News Reader

Here is an elementary proof:

Since m and n are distinct, we may assume that m > n >= 2. From the equation and unique factorization, we know that n divides m, so write m = nd.

Then (nd)^n = n^(nd). Hence d^n = n^{n(d-1)}, which yields d = n^{d-1} >= 2^{d-1}.

Claim: if k is an integer greater than or equal to 3, then k < 2^{k - 1}.

Proof: the base case is clear: 3 < 4. Suppose k > 3 and k - 1 < 2^{k - 2}. Then k < 2^{k-2} + 1 <= 2^{k-1}, where the last inequality holds because 2^{k-1} - 2^{k-2} = 2^{k-2} >= 1. QED

So, d must be less than 3. Since m = nd and m and n are distinct, d is not 1, so d = 2. Since d = n^{d-1} and d - 1 = 1, we have n = d, so m = 4.

View on HN

How exactly do we know that n divides m? I think it's clear that they have the same prime factors, but it's not clear why they couldn't be like n = 12 and m = 18.

Say m contains the prime factor p^i and n contains the prime factor p^j, then m^n will contain p^in and n^m will contain p^jm. For them to be equal we need in = jm or i/j = m/n but for a given solution m/n is constant and the prime factor multiplicity ratio must be equal to that. And that applies to all prime factors, their multiplicities must all have the same constant ratio, therefore the smaller of the two numbers must have smaller multiplicity for all prime factors and therefore divide the larger number. There is probably a simpler way to say this, this feels too complicated.

Focusing on v_x(p), the multiplicity of some prime p in the prime factorization of x:

  m = j p^a → v_m(p) = a

  n = k p^b → v_n(p) = b

p is not a factor of j or k

  m^n = j^n (p^a)^n
      = j^n p^(an)
      = k^m p^(bm)
      = …
      = n^m


  v_{m^n}(p) = an = bm

Note that a=0 iff b=0. This is the case where p is neither a factor of m nor n.

  b/a = m/n >=1

This ratio is the same for all primes, so every prime has:

  v_m(p) >= v_n(p)

  n | m

(We didn't need the ratio to be the same, but we did need the ratios to be all greater >= 1)

n^n * n^(m - n) = n ^ m = m ^ n, so n^n divides m^n, so n divides m.

This is almost word for word the proof that would appear in a solid number theory textbook. Very nice.

I think it's even simpler after you figured out that m = kn = n^k => n is an integer > 1 and equal to the (k-1)-th root of k where k is an integer > 1.

The only integer (k-1)-th root of k is 2 for k = 2. Thus, n = 2, k = 2, m = 4.

The “claim” more or less proves that k-1 th root of k is less than 2 if k is larger than 2. So I think your argument is equivalent.

this appears to be a(n incorrect!) gpt comment

No, it's a carefully constructed logical argument. Miles ahead of anything GPT is capable of producing, based on my experiments with it.

There's a clear signal that it's constructed by a person with advanced mathematical training: the laconic, "high points only" style. It makes small, but nontrivial and correct, logical leaps, expecting that you will work through the details needed to justify the leap yourself.

For example, the reasoning in this sibling comment is needed to justify the "n divides m" claim https://news.ycombinator.com/item?id=35638344

In my experience, GPT writes much more verbose arguments and cannot reliably reason at this level.

But if this were a college homework assignment you would be expected to explain briefly why n divides m, the comment did skip over it which can confuse people.

Thanks for this awareness exercise. Still, I forget to add gpt to my internal reading filter

What drove you to this conclusion? We have an enlightening reply explaining how we know it isn't, but I would also like to know what heuristic you used (so that we know to be wary of it!)

Reply on news.ycombinator.com