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

A question about coprime numbers.

  1. Dec 28, 2005 #1
    is it true that
    (a+b)^p = a^p + b^p (mod p)
    (a,b,p natural)

    only if (p-1)! and p are coprime?
     
  2. jcsd
  3. Dec 28, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    wel,, p-1! and p a coprime if and only if p is prime, but unless you introduce some quantifiers it is anbiguous.

    it is true for all a,b, and p a prime, and false for some a,b and p composite.

    given some composite p, say p=rs you might want to split r into two things ie p=(u+v)s to see what's going on.
     
    Last edited: Dec 28, 2005
  4. Dec 28, 2005 #3
    thats not true
    for example p=4
    3!=2*3=6
    edit: ignore the above i just confused a few things up in my head.
     
    Last edited: Dec 28, 2005
  5. Dec 28, 2005 #4
    But 6 and 4 are not coprime.
     
  6. Dec 28, 2005 #5

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Why is it ambiguous? (p-1)! and p are coprime iff p is prime, so the statement can be reworded:

    (a + b)p = ap + bp (mod p) only if p is prime

    Doesn't look ambiguous to me. It says:

    [tex][(a + b)^p \equiv a^p + b^p\ (\mbox{mod } p)] \Rightarrow p \mbox{ is prime}[/tex]

    which is equivalent to its universal closure:

    [tex](\forall x)(\forall y)(\forall z)\{[(x+y)^z \equiv x^z + y^z\ (\mbox{mod } z)] \Rightarrow z \mbox{ is prime}\}[/tex]
     
    Last edited: Dec 28, 2005
  7. Dec 28, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It doesn't say *for all a and b* that is where it is ambiguous. It might be understood by most, but it is better stated, and since the OP thinks 4 and 6 are coprime you can understand why I prefer explicit things. For instance if a=0 and b=1 it is true for all p. As too many people when starting out confuse proof with an example it is better not to take chances.

    I was also trusting that people can allow for the degenerate p=1 case themselves without it needing to be stated, but I think i need to say it outloud first now, recalling recent threads.
     
    Last edited: Dec 28, 2005
  8. Dec 28, 2005 #7
    Last edited: Dec 28, 2005
  9. Dec 28, 2005 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    What you're talking about are fermat pseudoprimes. Try googling for them.

    In anycase, the proof by induction in the link does not at any point imply the result you cite (which is false for any fermat pseudoprime p), and at no point anywhere does anything rely on "if and only if p and p-1! are coprime".
     
  10. Dec 29, 2005 #9
    but the proof relies on
    (a+b)^p = a^p + b^p (mod p)

    [​IMG]

    note here that i goes from 1 to p-1 so in order for the sum to be a multiple of p i! must be coprime to p for every value of i from 1 to p-1 or else i! could possibly divide the p term in p! which would mean the sum isn't a multiple of p.
     
    Last edited: Dec 29, 2005
  11. Dec 29, 2005 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Nope, still can't see what the problem is.

    One step in a proof might be if and only if, but that doesn't mean all other steps and deductions are. I mean the induction requires you to deduce something for k+1 from k whcih might not be applicable in the composite case since we would be trying to prove something about numbers coprime to the something else.



    Fermat's Little Theorem: If p is a prime and a is coprime to p then a^{p-1}=1 mod p (or equivalently a^p=a for all a which your link claims is fermat's little theorem; i was always taught the p-1 statement).

    Numbers that pass a^(t-1)=1 mod t for all a coprime to t where t is composite are called carmichael numbers. I don't believe, though I may be wrong, that the passage to a^t=a mod t for all a is equivalent for composite t: in the prime case we rely upon the fact that all numbers are invertible mod p or a multiple of p which fails mod t a composite.

    In anycase, the statement you first give is *for all a,b* presumably (note the quantifiers) which carmichael numbers (fermat pseudeoprimes for all numbers *coprime* to t) might fail because of the coprimality thing. Notice the difference.

    Not that I actually see at any point any statement that something is "if and only if p and p-1! are coprime" on that page, no one states that and no one uses that. All I see is some deduction made if p is prime then (a+b)^p=a^p+b^p mod p (and i see no reverse deduction attempted about how if that were true for all a and b then p is prime, in fact off the top of my head I now don't even see that that is necessarily true; there are also other ways for that sum to be zero mod p than because the binomial coefficients are divisible by p).

    I can't say I've worked out what you need to do because I really can't tell what the problem is (partly because I still can't tell what the proper statement of your first post ought to be).

    for all a and b?
    for all a and b coprime to p?
    for a,b and a+b coprime to p?
     
    Last edited: Dec 29, 2005
  12. Dec 29, 2005 #11
    my original question was simply
    if its true that for any natural numbers a,b,p
    (a+b)^p = a^p + b^p (mod p)
    is satisfied if and only if p and (p-1)! are co-prime.
    i now understand that the answer is no because even if the p factor is divided from p! it does not necessarily mean that the sum from my previous link isn't a multiple of p though if p and (p-1)! are indeed co prime (which also means that p is prime) the sum is necessarily a multiple of p. this explains why fermat's little theorem does work for all prime numbers and also for pesudo prime numbers p whose factorials p! are a multiple of p^n n>1 (because then even though the p factor gets divided from p! the factorial and thus the sum are still a multiple of p).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A question about coprime numbers.
Loading...