Results 1 to 14 of 14
Like Tree2Thanks
  • 1 Post By Petek
  • 1 Post By diofantus

Math Help - mathematical proof

  1. #1
    Newbie
    Joined
    Mar 2014
    From
    United Kingdom
    Posts
    8
    Thanks
    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
    Last edited by diofantus; March 15th 2014 at 08:41 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Mar 2014
    From
    United Kingdom
    Posts
    8
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2014
    From
    United Kingdom
    Posts
    8
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    Re: mathematical proof

    Yes, that's correct. Well done!
    Thanks from diofantus
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2014
    From
    United Kingdom
    Posts
    8
    Thanks
    1

    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 ?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    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.)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Mar 2014
    From
    United Kingdom
    Posts
    8
    Thanks
    1

    Re: mathematical proof

    Quote Originally Posted by Petek View Post
    (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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Mar 2014
    From
    United Kingdom
    Posts
    8
    Thanks
    1

    Re: mathematical proof

    Quote Originally Posted by Petek View Post
    (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
    Last edited by diofantus; March 16th 2014 at 11:18 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    Re: mathematical proof

    Quote Originally Posted by diofantus View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Mar 2014
    From
    United Kingdom
    Posts
    8
    Thanks
    1

    Re: mathematical proof

    Quote Originally Posted by Petek View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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).
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Mar 2014
    From
    United Kingdom
    Posts
    8
    Thanks
    1

    Re: mathematical proof

    That's right Deveno, I was just too lazy to show the proof for mod 3, but thanks anyway.
    Thanks from Deveno
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: mathematical proof

    Quote Originally Posted by diofantus View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: February 1st 2013, 06:10 AM
  2. Mathematical Proof
    Posted in the Calculus Forum
    Replies: 1
    Last Post: August 31st 2011, 07:49 AM
  3. Mathematical induction proof, help?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 23rd 2010, 08:39 PM
  4. mathematical induction proof
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 27th 2010, 01:35 PM
  5. Mathematical proof help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 18th 2009, 02:33 AM

Search Tags


/mathhelpforum @mathhelpforum