Fermat's Little theorem states taht ....
If p is prime, then P divides ap-a
A good question for congruences.... To understand and implement it....
I am giving the guidelines on how to approach and solve.. see if it fits your mind ;)
a is positive and not divisible by p. The idea is that if we write down the sequence of numbers
a, 2a, 3a, ... (p-1)a
and see the remainder they will be all different (Why try to prove using congruences)
and will be 1, 2, 3, ... (p-1)
Therefore, if we multiply together the numbers in each sequence, the results must be identical modulo p:
Now multiply on both sides to get a result..
Write down that .. then see that there is something common on both sides.. (Is that divisible by p?) if no can we remove that??
Have we proved fermat's theorem
19nice bit of knowledge ! bookmarked the thread ! deserves a pink ...hehe !
62Thanks Debotosh.. ;)
i was only giving a question so that you guys could get an example as to how to make use of congruences...
39the first p-1 positive multiples of a:
a, 2a, 3a, ... (p -1)a
Suppose that ma and na are the same modulo p, then we have m ≡ n (mod p), so the p-1 multiples of a above are distinct and nonzero; that is, they must be congruent to 1, 2, 3, ..., p-1 in some order.
Multiplying all these congruences together we find
a.2a.3a.....(p-1)a ≡ 1.2.3.....(p-1) (mod p)
i.e ap-1(p-1)! = (p-1)! (mod p).
Divide both side by (p-1)! to get the result to be proved
62hmm.. good one bhargav..
But i wonder if this helped anyone whom I intended this to help!!
(*you must have already known this one?)
39yes, knew it before..
but ya , nowadays what i am seeing here is that threads are just started and no active participation and enthusiasm shown in finishing it off..
was waiting to see of anyone would atleast post what they were thinking about proof, but no one came ahead...
and ya , even if a person does not know the proof before, with the amount of help given by your clues in your post itself is enough to finish the proof..
1can anyone explain.......
how barghav concluded that
"if we have m ≡ n (mod p), then the p-1 multiples of a above are distinct and nonzero"
here
62That is because if p is prime and two multiples m, n of a are not distinct (m,n both lie between 0 and p-1)then
ma≡na (mod p)
then (m-n)a≡0 (mod p)
so either p divides a or m-n
|m-n|<p so p cannot divide m-n
also a and p are coprime by assumption....
Hence a contradiction.
