Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruence problem

  1. Jul 8, 2005 #1
    Thanks to those who gave me advice on my last post, "Simple solution to FLT?" I found the info on Germain primes useful.

    I have a related problem.

    Consider the equation f(z,y) = [tex][(z^5-(z-y)^5)-y^5]/5[/tex]
    which reduces to [tex]zy(z^3 -2z^2y +2zy^2 -y^3)[/tex]

    If z is congruent to y, the congruent sum of the first and last terms within the ( ) is congruent to 0 mod 5, and likewise for the second and third terms, with the result that
    f(z,y) is congruent to 0 mod 5 if z is congruent to y mod 5.

    By brute force, I can prove that if z is not congruent to y mod 5 that
    f(z,y) is not congruent to 0 mod 5. This involved substituting all the possible congruent combinations values of z and y, adding them up, and determining that they never equal 0.

    My question is, can one derive a general mathmetical proof of this?

    Better still, can one derive a general proof for this if we use p=any prime number, instead of 5?
     
  2. jcsd
  3. Jul 8, 2005 #2
    There is supposed to be a /5 at the end.
    If you expand the term [tex](z-y)^5[/tex], eliminate the first and last term and divide the result by 5 (since 5 is a prime number, all the internal terms are divisable by 5), can we prove that resultant function is NOT divisable by 5 if z is NOT congruent to y mod 5.
     
  4. Jul 8, 2005 #3

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    You also need z and y not congruent to 0 mod 5.

    If you take p=7, z=3 and y=2 then

    [tex][z^p-(z-y)^p-y^p]/p\equiv 0 \mbox{ mod p}[/tex]

    So if this is the generalization you had in mind, it's not true.
     
  5. Jul 8, 2005 #4
    What this says is that if p is prime and y is congruent to z-1 mod p, that f(z,m) is always congruent to 0 mod p. I have to figure out why I don't get this result when I plug these values into the n=5 equation?
     
  6. Jul 8, 2005 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    In the general p case, what is f(z,m)? What I had guessed? Are you not after an if and only if statement then?

    Why the z-1 that I bolded above and not just z? I thought you had the result you were after with the p=5 case?
     
  7. Jul 8, 2005 #6
    Sorry, but I have to get back to this later. I will respond.
     
  8. Jul 8, 2005 #7
    I'm finally back on line.
    I confused everyone with a mix of mathmetical and congruence equations. I reduced f(z,y) mathmetically first and then treated the result as a congruence equation. In other words, my intent is to do the mathmetical division (by 5 or by p) first, and then treat the result as a congruent equation. Otherwise, if you are strictly dealing with a congruent equation you wind up dividing by 5 mod 5, or p mod p, which is the same as division by zero. Thus , the congruent equations will always be congruent to 5 mod 5, or p mod p, which is the proof offered; however, the mathmetical equation does not produce this same result. That's why my brute force method had a different result.

    I might better state the question as:

    Is it possible to prove that [tex]zy(z^3 - 2z^2y + 2zy^2 - y^3)[/tex]
    can never have a factor of 5 if z is not congruent to y mod 5.
    Since I designate this equation as equal to f(z,y), I can rephrase it as:
    Is it possible to prove that f(z,y) is always incongruent to 5 mod 5 (or 0 mod 5, if you prefer) if z is not congruent to y mod 5?

    And, if so, can we expand this proof to substitute p for 5, (without dividing by p mod p), so that the proof covers all prime values?
     
  9. Jul 9, 2005 #8
    Back again for a minute. I forgot that there is another restriction on the congruent values of z and y ---neither can be congruent to 5 mod 5.
     
  10. Jul 9, 2005 #9
    One other thing - f(z,m) was a typo. It should have been f(z,y)
     
  11. Jul 9, 2005 #10

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    What you did was fine, f(x,y) was an integer if x and y were, so asking about it's residue class mod 5 shouldn't have confused anyone.

    You already did though? There's nothing wrong with a proof that manually checks the possible congruences (there's not many to check!).

    No, take y=1, z=3 then p=7 divides zy(z^3 - 2z^2y + 2zy^2 - y^3) so this is not true for all p.
     
  12. Jul 9, 2005 #11
    Thanks. I guess that settles the issue. It looks like there may be a relationship here to Germain primes? 2(5) + 1 = 11 which is prime but
    2(7) + 1 = 15 which is not prime.
     
  13. Jul 9, 2005 #12
    Wait a minute!! The equation we used was based on mod 5 not mod 7. There is a different equation we must develop for mod 7.

    [tex] z^7 -(z-y)^7 - x^7[/tex] and divide(mathmetically) by 7. Then we apply values of z=3 and y=1. Haven't done that yet, but I'll bet the result isn't congruent to 7 mod 7
     
  14. Jul 9, 2005 #13

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    This is why I asked in posts 3 and 5 what generalization you had in mind. See post #3 for a counter example for this new f.
     
  15. Jul 9, 2005 #14
    Ignore my post 4, it is completely in error based on a bad assumption of mine.
    The f(z,m) was also in error, so ignore.
    The generalization I am trying to prove is that the f(z,y) equation i can derive for each mod prime value (after factoring out the prime that is contained in all the internal terms of the expansion) is not divisable by that prime, given that z is not congruent to y mod p and z and y are not congruent to p mod p.
     
  16. Jul 9, 2005 #15

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    [tex](3^7-(3-2)^7-2^7)/7=2058/7=294[/tex]

    which is divisible by 7. I can't make this any more explicit.
     
  17. Jul 9, 2005 #16
    Here again you are dividing by zero so your answer will always be 7.

    [tex]a^p -(a-b)^p -b^p[/tex] is congruent to a - (a-b) -b mod p = 0 mod p

    You have to do the binomial expansion of [tex]9a-b)^p[/tex], eliminate the first and last terms and THEN divide by p. If you divide by p before you eliminate the first and last terms you are dividing a number congruent to p mod p by a number congruent by p mod p (or 0 mod p), which is a no-no.
     
  18. Jul 9, 2005 #17
    excuse the typo. The "9" should be a "9". Forgot to use the shift key.
     
  19. Jul 9, 2005 #18
    I did it again. The "9" should be a " ( " .
     
  20. Jul 9, 2005 #19

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Do you really think expanding first will yield a different answer? Alright, here ya go:

    [tex]z^7-(z-y)^7-y^7=7z^6y-21z^5y^2+35z^4y^3-35z^3y^4+21z^2y^5-7zy^6[/tex]

    Divide by 7 and factor zy:

    [tex]zy(z^5-3z^4y+5z^3y^2-5z^2y^3+3zy^4-y^5)[/tex]

    Now evaluate at z=3, y=2:

    [tex](3)(2)((3)^5-3(3)^4(2)+5(3)^3(2)^2-5(3)^2(2)^3+3(3)(2)^4-(2)^5)[/tex]

    or

    [tex](6)(243-486+540-360+144-32)=(6)(49)[/tex]

    But I guess you could have checked that yourself no?


    You're really considering whether or not [tex]z^7-(z-y)^7-y^7[/tex] is congruent to 0 mod 7^2. You know it's divisible by 7, so it's enough to consider if [tex](z^7-(z-y)^7-y^7)/7[/tex] is congruent to 0 mod 7. There's no "dividing" by zero problem as you are proclaiming. If it makes you more comfortable forget about congruences altogether and just rephrase everything in terms of divisibility.
     
  21. Jul 9, 2005 #20
    I did check an example of z=2, y=1 mod 7 and I got a result of 5 mod 7.
    Thanks. I got ta go back to the drawing boards. Really appreciate your time!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Congruence problem
  1. Congruence Solving (Replies: 6)

  2. Congruence relation (Replies: 0)

Loading...