# Thread: mathematical proof

1. ## mathematical proof of congruence

Hi,

Given the following three equations

$\displaystyle a=k^2(m^2-2mn-n^2)^2$
$\displaystyle b=k^2(m^2+n^2)^2$
$\displaystyle c=k^2(m^2+2mn-n^2)^2$

I can show programatically that a, b and c are always congruent MOD 24 for any of the $\displaystyle 24^3$ combinations of k, m and n MOD 24.

Is there a 'nicer', more mathematical method I can use to prove the same, rather than this 'sledgehammer' approach?

Thank you

2. ## Re: mathematical proof of congruence

Given the equations in the OP it can be shown that

$\displaystyle c-b=b-a=4k^2mn(m+n)(m-n)$

So, going from a different angle, I would need to prove that

$\displaystyle 4k^2mn(m+n)(m-n)\equiv 0\ mod\ 24$ which it always is.

this can be reduced to the smaller problem of

$\displaystyle k^2mn(m+n)(m-n)\equiv 0\ mod\ 6$ which it always is.

but again, the only way I can see of doing this is the sledgehammer approach of showing it correct for all $\displaystyle 6^3$ combinations.

Is there another way of showing that if none of the factors $\displaystyle k,\ m,\ n,\ (m+n),\ (m-n)$ is congruent 0 mod 6 then one of them must be congruent 3 mod 6 and at least one of the others must be congruent 2 mod 6 (i.e. even)?

Thanks again

3. ## Re: mathematical proof

First, just show that $\displaystyle mn(m+n)(m-n) \equiv 0 \pmod{6}$. After doing so, multiply by $\displaystyle k^2$ to get the final result. Now show that $\displaystyle mn(m+n)(m-n) \equiv 0 \pmod{2}$ and $\displaystyle mn(m+n)(m-n) \equiv 0 \pmod{3}$. Each congruence can be proved by considering just a few cases. You don't need to list every single possibility. Please post again if this hint isn't clear, or you need more help.

4. ## Re: mathematical proof

Hi Petek

Thanks for the pointer.

I think I understand what you're saying so here goes...

given $\displaystyle d=mn(m+n)(m-n)$

show that $\displaystyle d\equiv 0\ mod\ 2$

There are 4 possible combinations mod 4 for m and n.
Three of these have either $\displaystyle m\equiv 0\ mod\ 2\ or\ n\equiv 0\ mod\ 2$ so for these $\displaystyle d\equiv 0\ mod\ 2$
The final combination is where m and n $\displaystyle \equiv 1\ mod\ 2$ so that both $\displaystyle (m+n)\ and\ (m-n)\equiv 0\ mod\ 2$ showing that $\displaystyle d\equiv 0\ mod\ 2$ for all m and n.

This means that any multiple of d will also be $\displaystyle \equiv$ 0 mod 2, so we can say that $\displaystyle k^2d\equiv 0\ mod\ 2$

Then do the same for $\displaystyle d\equiv 0\ mod\ 3$

5. ## Re: mathematical proof

Yes, that's correct. Well done!

6. ## Re: mathematical proof

Many thanks Petek.

As a quick aside, is it possible to prove (or contradict) that 2 and 3 are the only primes p, where $\displaystyle mn(m+n)(m-n)\equiv 0\ mod\ p$ ?

7. ## Re: mathematical proof

Let's rephrase your question as

Is it true that if p is a prime greater than 3, then there exist integers m and n such that mn(m+n)(m-n) is not divisible by p?

Can you find suitable m and n? (Hint: the same m and n work for all such p.)

8. ## Re: mathematical proof

Originally Posted by Petek
(Hint: the same m and n work for all such p.)
Not sure what you mean by this but I will take a closer look later. 1:00 am here now

Thanks for your help

9. ## Re: mathematical proof

Originally Posted by Petek
(Hint: the same m and n work for all such p.)
Still not sure about the above.

My proposition: $\displaystyle mn(m+n)(m-n)\equiv 0\ mod\ p$ for all m and n mod p is only true for prime p where $\displaystyle p\le 3$

PROOF

For any prime p, $\displaystyle mn(m+n)(m-n)\equiv 0\ mod\ p$ for m and n mod p if and only if

(i) $\displaystyle m\equiv 0\ mod\ p$ or
(ii) $\displaystyle n\equiv 0\ mod\ p$ or
(iii) $\displaystyle m\equiv n\ mod\ p$ or
(i) $\displaystyle m\equiv -n\ mod\ p$ (i.e m is the additive inverse of n mod p)

Cases (i) and (ii) combined cover 2p-1 combinations
Case (iii) covers p-1 combinations (not including 0, 0)
Case (iv) covers p-1 combinations

So total number of combinations covered are 4p – 3

The total number of combinations for m and n mod p are $\displaystyle p^2$

Since we require all combinations to be covered, we require

$\displaystyle 4p-3\ge p^2$

and this is when $\displaystyle 1\le p\le 3$

so $\displaystyle mn(m+n)(m-n)\equiv 0\ mod\ p$ is only true for all m and n mod p when $\displaystyle p<=3$

$\displaystyle QED$

10. ## Re: mathematical proof

Originally Posted by diofantus
Still not sure about the above.

My proposition: $\displaystyle mn(m+n)(m-n)\equiv 0\ mod\ p$ for all m and n mod p is only true for prime p where $\displaystyle p\le 3$

PROOF

For any prime p, $\displaystyle mn(m+n)(m-n)\equiv 0\ mod\ p$ for m and n mod p if and only if

(i) $\displaystyle m\equiv 0\ mod\ p$ or
(ii) $\displaystyle n\equiv 0\ mod\ p$ or
(iii) $\displaystyle m\equiv n\ mod\ p$ or
(i) $\displaystyle m\equiv -n\ mod\ p$ (i.e m is the additive inverse of n mod p)

Cases (i) and (ii) combined cover 2p-1 combinations
Case (iii) covers p-1 combinations (not including 0, 0)
Case (iv) covers p-1 combinations

So total number of combinations covered are 4p – 3

The total number of combinations for m and n mod p are $\displaystyle p^2$

Since we require all combinations to be covered, we require

$\displaystyle 4p-3\ge p^2$

and this is when $\displaystyle 1\le p\le 3$

so $\displaystyle mn(m+n)(m-n)\equiv 0\ mod\ p$ is only true for all m and n mod p when $\displaystyle p<=3$

$\displaystyle QED$
I'm afraid I don't understand what you mean by saying that some expression "covers a number of combinations." My hint was to suggest taking m = 2 and n = 1. Then, for any prime p > 3, it's obvious that none of m, n, m + n or m - n are divisible by p, so neither is their product.

11. ## Re: mathematical proof

Originally Posted by Petek
I'm afraid I don't understand what you mean by saying that some expression "covers a number of combinations."
Of all the possible combinations of m and n mod p there will be exactly p instances where m=0 mod p
The same is true where n=0 mod p, but one of these is where m also equals 0, this means that all possible combinations where either m=0 mod p or n=0 mod p will be 2p-1

My hint was to suggest taking m = 2 and n = 1. Then, for any prime p > 3, it's obvious that none of m, n, m + n or m - n are divisible by p, so neither is their product.
A lot more succinct than mine

Many thanks again.

12. ## Re: mathematical proof

Post 4 is a bit incomplete, here is the full proof for the "mod 3" case:

If m or n = 0 (mod 3), we have nothing to prove. If m = n (mod 3) then the factor m - n = 0 (mod 3), so assume m = -n (mod 3) and thus m + n = 0 (mod 3).

13. ## Re: mathematical proof

That's right Deveno, I was just too lazy to show the proof for mod 3, but thanks anyway.

14. ## Re: mathematical proof

Originally Posted by diofantus
That's right Deveno, I was just too lazy to show the proof for mod 3, but thanks anyway.
I realized since you had solved it "the hard way" in another post this was probably so, but someone else may read this thread one day.