using fermat's little theorem show that each prime divisor of (2^p) -1, where p is a prime is greater than p.

any help on this would be appreciated. thanks in advance!

Printable View

- March 3rd 2008, 02:29 PMthebrownguy01Help with Fermat's Little Theorem
using fermat's little theorem show that each prime divisor of (2^p) -1, where p is a prime is greater than p.

any help on this would be appreciated. thanks in advance! - March 3rd 2008, 02:45 PMThePerfectHacker
Since it means . Let be the order of modulo then , but by properties of orders we know since it means thus the is the order of modulo . But by Fermat's little theorem we know and hence by properties of order. In particular, this means . Thus, , a prime divisor of , is greater than .

- March 3rd 2008, 04:02 PMthebrownguy01
thanks for the response but I don't quite understand still. Is there a way you could explain it some more or provide a link to a place where I might find something to help me understand it?

Thanks - March 3rd 2008, 04:14 PMThePerfectHacker
Given a prime and an integer (with ) we define the

__order__of mod to be the__least__positive exponent such that . Of course such a can always be found and furthermore because and is the__least__(smallest) such exponent. For example, take and then because . Now there is a simple theorem with orders. Suppose is a positive integer such that then *. This theorem is telling us that the order must divide any exponent which raises congruent to . So in the above proof we concluded that but since is a prime it forces .

*)In case you want to see the proof it is simple. We can write where by the division algorithm. That means but so but that is impossible since and is__least__so . Which means . And so clearly .