5 ms·
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, s
by bustermellotron 3y ago
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.
- civilized 3y agoThis is almost word for word the proof that would appear in a solid number theory textbook. Very nice.
- andygeorge 3y agothis appears to be a(n incorrect!) gpt comment
- dTal 3y agoWhat 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!)
- civilized 3y agoNo, 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 https://news.ycombinator.com/item?id=35638344 In my experience, GPT writes much more verbose arguments and cannot reliably reason at this level.
- calf 3y agoBut 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.
- yonrg 3y agoThanks for this awareness exercise. Still, I forget to add gpt to my internal reading filter
- giik 3y agoI 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.
- bustermellotron 3y agoThe “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.
- OscarCunningham 3y agoHow 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.
- danbruc 3y agoSay 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.
- hgsgm 3y agoFocusing 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) so n | m (We didn't need the ratio to be the same, but we did need the ratios to be all greater >= 1)
- nmmnthrowaway 3y agon^n * n^(m - n) = n ^ m = m ^ n, so n^n divides m^n, so n divides m.