1. ## mathematical proof of congruence

Hi,

Given the following three equations

$a=k^2(m^2-2mn-n^2)^2$
$b=k^2(m^2+n^2)^2$
$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 $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

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

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

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

this can be reduced to the smaller problem of

$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 $6^3$ combinations.

Is there another way of showing that if none of the factors $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 $mn(m+n)(m-n) \equiv 0 \pmod{6}$. After doing so, multiply by $k^2$ to get the final result. Now show that $mn(m+n)(m-n) \equiv 0 \pmod{2}$ and $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 $d=mn(m+n)(m-n)$

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

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

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

Then do the same for $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 $mn(m+n)(m-n)\equiv 0\ mod\ p$ ?

7. ## Re: mathematical proof

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

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: $mn(m+n)(m-n)\equiv 0\ mod\ p$ for all m and n mod p is only true for prime p where $p\le 3$

PROOF

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

(i) $m\equiv 0\ mod\ p$ or
(ii) $n\equiv 0\ mod\ p$ or
(iii) $m\equiv n\ mod\ p$ or
(i) $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 $p^2$

Since we require all combinations to be covered, we require

$4p-3\ge p^2$

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

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

$QED$

10. ## Re: mathematical proof

Originally Posted by diofantus
Still not sure about the above.

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

PROOF

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

(i) $m\equiv 0\ mod\ p$ or
(ii) $n\equiv 0\ mod\ p$ or
(iii) $m\equiv n\ mod\ p$ or
(i) $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 $p^2$

Since we require all combinations to be covered, we require

$4p-3\ge p^2$

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

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

$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.