A question about coprime numbers.

[Anzas]

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?

 

[matt grime]

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.

 

[Anzas]

p-1! and p a coprime if and only if p is prime

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.

 

[Muzza]

But 6 and 4 are not coprime.

 

[AKG]

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

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

(a + b)^p = a^p + b^p (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]

 

[matt grime]

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.

 

[Anzas]

the reason I am asking this is because there is a proof to fermat's little theorem using this rule
"[URL
(its the Inductive proof with the binomial theorem)
what i can't understand is why fermat's little theorem sometimes works also for non prime numbers if the proof for this only works when p is prime.

 

[matt grime]

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

 

[Anzas]

but the proof relies on
(a+b)^p = a^p + b^p (mod p)

http://content.answers.com/main/content/wp/en/math/c075c9f5f8cf5901bc7256b2ff1604ba.png

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.

 

[matt grime]

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?

 

[Anzas]

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