Originally posted by PBE6
Excellent!
Here's another one:
Problem 2 (MathBattle) It is known that m^2 + n^2 + m is divisible by mn
for some positive integers m and n. Prove that m is a perfect square.
Yikes, this one was a lot tougher than the Piglet/Pooh question!! It has taken me a while, but I believe that I have a proof (by contradiction). It might be hard for me to summarize it here clearly, but whatever, here goes:
Suppose it is not the case that m is a perfect square. Then, there must be at least one odd power in the prime-power factorization of m. This means there must exist some prime number P such that P^(2a+1) exactly divides m where a is some element of the set [0,1,2,3,....]. (Since positive integer m is a perfect square if and only if all powers in the prime-power factorization of m are even.***) By "exactly" divides I mean that P^(2a+1) divides m but P^(2a+2) does not.
Since we know that m^2 + n^2 + m = bmn (for some positive integer b), it is clear that m divides n^2. Since m divides n^2; and since P^(2a+1) divides m; it follows that P^(2a+1) divides n^2. But, it further is the case that P^(2a+2) divides n^2 because n^2 is a perfect square and because, again, such a perfect square must have all even powers in its prime-power factorization*** (here, I am using the idea that if P^k divides a perfect square integer where k is an odd positive integer then it must be that P^(k+1) also divides the same perfect square). It follows that P^(a+1) divides n. Of course, P^(a+1) also divides m.
Since P^(a+1) divides both m and n, it follows that P^(2a+2) divides mn. Since bmn = m^2 + n^2 + m, it follows that P^(2a+2) divides m^2 + n^2 + m. Since P^(2a+2) divides both m^2 and n^2, it follows that P^(2a+2) also divides m. But from above, P^(2a+1) exactly divides m, which entails that P^(2a+2) does not divide m. So we have a contradiction.
So m is a perfect square.
-------------------------------
***Since a couple parts of the proof hinge on this, I will show the basic idea for proof of this here:
Suppose that n has all even powers in its prime-power factorization. Then we could write n = P1^(2c1)*P2^(2c2)*...*Pk^(2ck). In that case, n = m^2 where m = P1^(c1)*P2^(c2)*...*Pk^(ck). So n is a perfect square. To show the other way, suppose n is a perfect square, such that n = m^2. The integer m will have some prime-power factorization m = P1^(c1)*P2^(c2)*...*Pk^(ck). Then n has prime-power factorization n = P1^(2c1)*P2^(2c2)*...*Pk^(2ck). So n has all even powers in its factorization. So positive integer n is a perfect square if and only if all powers in the prime-power factorization of n are even.