Are there distinct positive integers m and n such that m n evenly divides m 2 + n 2 ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
FYI A much better way to resolve the diophantine equation p 2 − 4 = q 2 is that ( p − q ) ( p + q ) = 4 and factorize accordingly. It can also be generalized to other constants, and we don't have to seek out "sum of consecutive odd numbers".
Log in to reply
In general I agree that factoring is going to be simpler. I just happened to see two perfect squares being separated by 4 , remembered the consecutive odd numbers thing, and saw 1 + 3 being the only such partition. In this instance it happened to be faster for me
"Since all perfect squares are separated by an odd number"
This needs to be rephrased. I don't quite get what you mean by "separated by". Usually that means "their difference is", which clearly isn't true in this context.
You also
seem
to be saying that p and sqrt(p^2-4) are "at least two consecutive odd numbers....apart". I don't know what that is supposed to mean but -1 and 1 are two consecutive odd numbers.
You seem to want to be saying that these two numbers are at least the sum of two consecutive positive odd numbers distant from each other, but I'm not getting how you reach that point (if that is, indeed, the point you are aiming for).
Log in to reply
Yeah, that part of the solution was very poorly worded and had several typos. I believe all consecutive perfect squares have an odd difference would be much better for the first section, and
I was then saying that since 4 is even, p 2 and p 2 − 4 cannot be consecutive perfect squares. A faster method than factoring in this particular case (at least I found it faster) would be to say that we need to add some number of consecutive odd numbers together to get 4 , and these numbers can quickly give our values of p 2 and p 2 − 4 . The only way to partition this is 1 + 3 , which implies that p 2 = 4 and p 2 − 4 = 0 .
Thanks for letting me know of that atrocious write-up :P
You seem to be using n for two distinct variables here ... it might be better to use a different symbol
Log in to reply
Oh wow you're right didn't notice that when writing this up. Thanks for pointing that out!
1 1 is a factor of 1+1. Isn't 0 0 a factor of 0+0? If 0 and 1 are integers, then isn't there a solution set, {(0,0) and (1,1)} ?
Log in to reply
In the general case yes, but this question says that m , n must be distinct, so we have to reject all cases like ( 0 , 0 ) , ( 1 , 1 ) , ( 2 , 2 ) , . . .
0 is not a positive integer
Relevant wiki: Greatest Common Divisor
Any solution m , n induces a solution p = m / g c d ( m , n ) , q = n / g c d ( m , n ) where p and q are coprime.
Then p ∣ p 2 + q 2 so p ∣ q so p = 1 , and symmetrically q = 1 which implies that m and n were not distinct.
While this proof is fine, there are some general errors being made throughout other proofs below I'd like to highlight:
Assuming that if x + y is an integer, then x and y must be integers.
Assuming that showing specific cases deals with the general scenario (showing a specific case is good for a counterexample falsifying some statement, but this is a problem where we need to demonstrate something is true for all distinct pairs of integers)
Assuming that if x divides y 2 then it also divides y .
It would be nice to know what "evenly divides" means.
Otherwise just whistling in the dark.
Log in to reply
As in, if you divide by that number, you get an integer answer (no remainder).
This is common knowledge by the point that this sort of mathematical proof is taught, or so I thought.
Great, indeed. A closely related technique is Fermat's Method of Infinite Decent?
For item 3, my proof would have been clearer if I'd highlighted that it's true in the specific case of x and y being coprime. Perhaps I should have just jumped from p ∣ q 2 to p = 1 instead.
Log in to reply
Indeed. That is a necessary condition, which you have stated.
The "correct theorem" to apply is that if a ∣ b c and g cd ( a , b ) = 1 , then a ∣ c . We can apply this to show that p ∣ 1 because p and q are coprime.
Best solution!
Relevant wiki: Greatest Common Divisor
Set d = g cd ( m , n ) and m = m ′ d , n = n ′ d . Then we know m ′ and n ′ are coprime. Note that since m 2 + n 2 = ( m + n ) 2 − 2 m n , we know m n ∣ m 2 + n 2 → m n ∣ ( m + n ) 2 , and then canceling the d 2 , we get m ′ n ′ ∣ ( m ′ + n ′ ) 2 . Since m ′ + n ′ is coprime to both m ′ and n ′ , we know this can only be possible when m ′ = n ′ = 1 . Given m = n , we know there are no solutions.
Let A = m n m 2 + n 2 where A is an integer:
We are going to prove that A is always not an integer for all m = n
⇒ A = n m + m n
For A to be an integer, both n m and m n must also be integers
So:
{ n ∣ m m ∣ n ⟹ m = n
But that's a contradiction to m = n
Therefore, A = m n m 2 + n 2 ∈ / Z ⇒ m n ∤ m 2 + n 2 for all m = n
You have shown that, m n ∣ m 2 + n 2 . I think you mean m n ∤ m 2 + n 2 .
Log in to reply
oh yeah thanks for the notice i was a little clumsy :D
Note: It is not true that "if x + y is an integer, then x and y must both be integers. For example, 1 . 2 5 + 1 . 7 5 = 3 , but neither of the individul terms are integers.
Given that,
Assume m and n can be odd or even. In this way, any pair wouldn't work. Let's prove that.
Step 1: O d d × O d d = O d d 3 × 5 = 1 5
Step 2: O d d 2 + O d d 2 = E v e n 3 2 + 5 2 = 3 4
(Even, odd) and (Odd, even) are also allowed in the first step.
____________________________________________________________________________
Step 1: E v e n × E v e n = E v e n 2 × 4 = 8
Step 2: E v e n 2 + E v e n 2 = E v e n 2 2 + 4 2 = 2 0
(Even, odd) and (Odd, even) are also allowed in the first step.
Now, we have (15 , 34) and (8,20)
According given conditions, we need to divide it.
3 4 ÷ 1 5 = 2 . 2 6 2 0 ÷ 8 = 2 . 5
( m , n ) has infinitely many values, but it is true that they can be odd or even. Which satisfies this method.
Hence m n ∤ m 2 + n 2 .
There are some issues mentioned in the comments, but the main one is that since the answer to the question is No, we need a proof that encompasses all distinct integers m and n in general, not just specific examples where the integers are chosen using specific properties. (For example, there are clearly cases where an even number divided by an even number is an integer - why does it not happen here?)
A specific example would be fine if the answer was Yes - that's just producing a counterexample.
In the case that m , n are both odd, don't we end up with o d d e v e n which has solutions: 3 6 = 2 . It's m n m 2 + n 2 , not the other way around.
In the second case, we have e v e n e v e n , which can also be an integer: 2 6 = 3
There's also the case where m is even and n is odd. There we end up with e v e n o d d which indeed has no solutions.
Log in to reply
You need multiply 6 and 3 before divide.
Log in to reply
I wasn't giving 6 and 3 in the context of the problem, I was giving them as an example that o d d e v e n , which is what you would get using two odd numbers, doesn't necessarily give a non-whole number upon division.
Also, your other comment doesn't answer the question the problem is asking. A single counter example does not show that it works for no pairs. It only shows that it doesn't work for that single pair.
Based on what you did, how do you know for certain that ( 4 6 , 7 9 ) doesn't work without trying it out? When you confirm that doesn't work, how about ( 1 2 3 , 3 9 9 ) ? This keeps going
Log in to reply
@Brandon Monsen – Both pairs are (Even, odd) and (Odd, odd). Which satisfies my condition.
I am considering 34 and 15 . Which calculated step by step( see the side notes). Also 20 and 8.
Log in to reply
It asks if there exists a pair of distinct positive integers which satisfies some conditions, not if every pair of distinct positive integers satisfies some conditions
Because of this, a counterexample isn't enough. You've only shown that it isn't satisfied for one out of infinitely many possible pairs.
Also, the first case was a typo. You put e v e n o d d when you calculated out 1 5 3 4 which is o d d e v e n
Log in to reply
@Brandon Monsen – No, it will work for none.
m = 3 n = 5
m n = 3 × 5 = 1 5 .
m 2 + n 2 = 3 2 + 5 2 = 3 4
1 5 3 4 = 2 . 6 6 6
Hence, my solution shown that it will not work for infinitely many pairs.
Log in to reply
@Munem Shahriar – What if the question "does there exist a pair of distinct positive integers m , n such that m n + 7 divides m 2 + n 2 − 2 ?" was posed?
Taking m = 3 , n = 5 does not work, since 3 × 5 + 7 = 2 2 does not divide 3 2 + 5 2 − 2 = 3 2 . Hence, we could "conclude" that there are no solutions. However, ( m , n ) = ( 4 , 8 ) is in fact a solution.
When the question asks whether there exists a pair of such integers, and you want to show that the answer is No, then you must show that no possible pair of integers can satisfy this condition , not that one pair of integers does not satisfy the condition.
Hope this helps :)
Sir you can't just try examples and claim it will always hold. Also, in your odd, odd case, the fraction should be even/odd, not odd/even. Odd/even can never be an integer, while even/odd could be.
Log in to reply
You need to calculate m × n and m 2 + n 2 before m × n ÷ m 2 + n 2 . In this way it will never can be an integer.
Log in to reply
Either I am misunderstanding your response, or you are misunderstanding the original question. Within the context of this problem, m 2 + n 2 m n being an integer is entirely irrelevant. It's m 2 + n 2 m n that is an integer. Also, you can't "calculate" m n or m 2 + n 2 explicitly without assuming they have a specific value, which defeats the purpose of solving in generality.
We can rewrite the expression m 2 + n 2 as ( m + n ) 2 − 2 m n .
Then we would just have to find number m , n such that m n ∣ m + n .
it can be easily seen that there are no such positive number.( as m n becomes much larger as compared to m + n . )
This isn't fully justified.
For example, you claim that m n ∣ ( m + n ) 2 if and only if m n ∣ ( m + n ) .
However, for example, 9 divides 6 2 but 9 does not divide 6. So, you're going to need to provide some additional justification of your claim.
Apart from what Eli pointed out, "mn is not much larger compared to m+n when n=1". Thus, that statement needs to be clarified further.
IE To find m n ∣ m + n , we will require m n ≤ m + n , and can figure out what the necessary conditions are.
If a solution exists and m and n have a common factor, divide both sides by this factor squared, so that m and n are now co-prime and m^2 = 2kmn - n^2. The right hand side is a multiple of n and the left hand side is not, so this is not possible. The only exception is if n = 1, in which case n^2 = 2kmn - m^2, so 1 = 2km -m^2, which is possible only if m = 1, since the right hand side is a multiple of m.
FYI A better way to present your solution is:
Suppose m = n satisfies k m n = m 2 + n 2 .
Let g = g cd ( m , n ) , m = g m ′ , n = g n ′ . Then, we have k m ′ n ′ − n ′ 2 = m ′ 2 and g cd ( m ′ , n ′ ) = 1 .
Since n ′ divides the LHS, it must divide the RHS, which tells us that n ′ = 1 .
Then, 1 = k m ′ − m ′ 2 . Since m ′ divides the RHS, it must divide the LHS, which tells us that m ′ = 1 . Hence, m = n .
Using contradition:
Assume m 2 + n 2 = 2 k m n
Solve for m: m = k n ± n k 2 − 1 (*)
k, n, kn are integers. So n k 2 − 1 is integer. k 2 − 1 is integer as well. For m to be integer, we need k 2 − 1 to be perfect square. So k 2 − 1 = a 2 where a is integer. Rewrite it as k 2 − a 2 = 1 . The farther apart k (k>a) and a are the farther their difference from 1 ( ≥ 1). In hope to have k 2 − a 2 = 1 , take closest k and a, k=a+1, then k 2 − a 2 = ( a + 1 ) 2 − a 2 = 2 a + 1 = 1 . So a = 0, k = 1. From (*), it follows that m = n. Contradition! So no distinct m and n exist.
Both m and n have to be at least even for m n m 2 + n 2 to be an integer.
So one could assume that m = 2p and n = 2q with p, q belonging to N*.
So m n m 2 + n 2 = 4 p q 4 p 2 + 4 q 2 = p q p 2 + q 2 . For it to be true, you need both p and q to be even numbers again, which by luck could be the case, that would thus lead to the same loop, again. Eventually, this will not be true anymore after a finite number of loops, thus this problem has no solution.
This is how I did it, but you should also consider the case for m=1.
I took a simple view: The result of the division = m/n + n/m. If m and n are distinct then one of those fractions is <1 so there is necessarily a remainder.
Let g c d ( m , n ) = d and m = d m 0 and n = d n 0
m n m 2 + n 2
= m 0 n 0 m 0 2 + n 0 2
= n 0 m 0 + m 0 n 0
Since these two terms are reciprocals to each other and in its simplest form, the sum cannot be an integer unless both are equal.
∴ m 0 = n 0 ⟺ m = n
Definition: For a prime p and natural number x we define o r d p ( x ) to be the largest non-negative integer e such that p e divides x
If m , n are distinct then there is a prime p such that o r d p ( m ) = o r d p ( n ) . So we have o r d p ( m n ) = o r d p ( m ) + o r d p ( n ) > 2 min { o r d p ( m ) , o r d p ( n ) } = o r d p ( m 2 + n 2 ) . However if m n divides m 2 + n 2 then o r d p ( m n ) ≤ o r d p ( m 2 + n 2 ) . So there are no distinct positive numbers m , n for which m n divides m 2 + n 2 .
We require m 2 + n 2 = I m n where I is an integer. This is a quadratic equation with solution m = 0 . 5 n ( I ± I 2 − 4 ) . For m and n to be integers, I 2 − 4 must be an integer. The only solution to this is I = 2 which is the trivial solution m = n not allowed by the problem.
Because simply, mn < m^2 + n^2
mn < (m^2 + n^2) does not prove that mn does not divide (m^2 + n^2) evenly
Evenly divides means there's a remainder and of course there's no remainder when dividing mn / ( m^2 + n^2 ) while mn < m^2 + n^2
I guess using a spreadsheet is 'cheating' ? (Took about one minuit to see the pattern)
I have another approach for the solution.
Consider m n m 2 + n 2 .
m n m 2 + n 2 = n m + m n
Now, if this has to belong to integers and that too, even, then m ≤ n and n ≤ m which gives n = m (non - distinct integers). Hence there does not exist any integers which can give the required result.
Let m and n be sides of a right-angle triangle. If m=n, m*n divides m^2 + n^2 (in other words, the area of hypotenuse squared) neatly into 2.
For any other case where (n>0; m>0; n!=m), always 2mn < m^2 + n^2
The problem requires that m!=n AND z m n = m^2 + n^2, however the right side solution can only be solved if m=n, and z=2; OR m=n=0. Therefore the answer is that there aren't distinct positive integers that fit the problem. Comments encouraged - visual solution was the first thing that came to mind, however I realize it does not count as a mathematical proof. Would be great if someone could elaborate on a geometric proof.
We have that m n ∣ m 2 + n 2 with m = n , which is the same as saying that, for some integer k ,
m 2 + n 2 = k m n
m n m 2 + n 2 = k
And finally n m + m n = k
We know k is an integer, and the only integer solution to x + x 1 = k with rational x is k = 2 , which implies
m = n , a contradiction.
Corrections are welcome
If mn | m 2 + n 2 ) , then m 2 + n 2 ) = kmn for some positive integer k. Then m(kn - m) = n 2 . This shows that m | n 2 . Similarly n | m 2 . Let p be a prime dividing m, then p | n 2 , then this shows that p | n. Simiarly if p | n, then p | m. So, since m and n are positive, let m = p 1 k 1 … … … … . p r k r , and n = p 1 l 1 … … … … . p r l r . If p j || m and p t || n, then m = p j x and n = p t y, where (p, x ) - (p, y) = 1. Then p 2 j x 2 + p 2 t y 2 =k p j + t xy. If j < t, then x 2 + p 2 t − 2 j y 2 = k p t − j xy. This shows that p | x 2 and therefore p | x which is a contradiction since by definition (p , x) = 1. Similarly if t < j, we again reach a contradiction. Therefore j = t, and m = n.
If m2+n2 is evenly divisible by mn then
m2+n2 = 2mn
Which means m2+n2 - 2mn = 0 (m - n)2 = 0.
This is only possible if m = n
Suppose this is true. Then there an integer k such that m 2 + n 2 = k m n . Then dividing by n 2 (which is allowed, since n > 0 ) gives the quadratic equation ( n m ) 2 − k ( n m ) + 1 = 0 . Now solve for n m to get n m = 2 k ± k 2 − 4 . Since m and n are distinct, suppose that m < n . Then n m < 1 , from which it follows that 2 k ± k 2 − 4 < 1 .
From the last equation, it must be true that both k < 2 and k > 2 ; that is, no such k exists. Supposing that m > n gives a similar contradiction.
NO SOLUTION AS YET, JUST A COMMENT! When the question says .... evenly divides m^2 + n^2 should it read 'exactly divides .....'. Regards, David
The key information is that m and n are distinct . Let n = m + k for integer k = 0 .
It follows m 2 + k m and 2 m 2 + 2 k m + k 2 are the numbers. Inspecting, there is nonzero remainder, k 2 .
Set up the equation: m^2+n^2=amn where a is some integer. (Since m^2+n^2 is an integer multiple of mn if mn divides). Dividing by mn and rearranging gives; m/n = a - n/m. Simply the fractions m/n and n/m such that it is in its most reduced form and the fraction becomes b/c = a - c/b. b and c are coprime or either or both is 1. Rearrange gives b/c = (ba-c)/b and then c(ba-c)=b^2. One case is that b and c are coprime and are both greater than 1 but then b cannot divide c or divide ba-c. So no solutions here. The other case is that either of b and c are 1. If b=1 then c>1. c(ba-c)=1. c is an integer greater than 1 so c*(ba-c) is either 0<, 0 or >1. This does not satisfy the equation. b and c are symmetrical since we could have taken away b/c instead of the c/b earlier. So no solutions here. The other case is that both c and b are 1. But then m=n from earlier. But this is not distinct so no solutions here.
Problem Loading...
Note Loading...
Set Loading...
Relevant wiki: Using the Quadratic Formula
m n m 2 + n 2 = n m + m n .
Let n m = x . It is clear that x can be any positive rational number except 1 due to the 'distinct' constraint.
We now have x + x 1 = p ⇒ x 2 − p x + 1 = 0 where p is an integer. Quadratic formula gives:
x = 2 p ± p 2 − 4
Clearly, p 2 − 4 must be a perfect square for x to be rational. Since all consecutive perfect squares are separated by an odd number, we must have that p 2 and p 2 − 4 have a difference being the sum of some number of consecutive positive odd numbers. It is easy to see that the only such sum is 1 + 3 which gives p 2 = 4 or p = ± 2 .
This results in x + x 1 = ± 2 or x = ± 1 , both of which we can reject due to the constraint that m and n are positive and distinct.
Hence, 0 solutions exist