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

- Mar 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! - Mar 3rd 2008, 02:45 PMThePerfectHacker
Since $\displaystyle q|(2^p-1)$ it means $\displaystyle 2^p\equiv 1(\bmod q)$. Let $\displaystyle k$ be the order of $\displaystyle 2$ modulo $\displaystyle q$ then $\displaystyle 2^k \equiv 1(\bmod q)$, but by properties of orders we know $\displaystyle k|p$ since $\displaystyle k\not = 1$ it means $\displaystyle k=p$ thus the $\displaystyle p$ is the order of $\displaystyle 2$ modulo $\displaystyle q$. But by Fermat's little theorem we know $\displaystyle 2^{q-1} \equiv 1(\bmod p)$ and hence $\displaystyle k|(q-1)\implies p|(q-1)$ by properties of order. In particular, this means $\displaystyle p\leq q-1 < q$. Thus, $\displaystyle q$, a prime divisor of $\displaystyle 2^p-1$, is greater than $\displaystyle p$.

- Mar 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 - Mar 3rd 2008, 04:14 PMThePerfectHacker
Given a prime $\displaystyle p$ and an integer $\displaystyle a$ (with $\displaystyle \gcd(a,p)=1$) we define the

__order__of $\displaystyle a$ mod $\displaystyle p$ to be the__least__positive exponent $\displaystyle k$ such that $\displaystyle a^k \equiv 1(\bmod p)$. Of course such a $\displaystyle k$ can always be found and furthermore $\displaystyle k\leq p-1$ because $\displaystyle a^{p-1} \equiv 1(\bmod p)$ and $\displaystyle k$ is the__least__(smallest) such exponent. For example, take $\displaystyle p=5$ and $\displaystyle a=4$ then $\displaystyle k=2$ because $\displaystyle 4^2 \equiv 1(\bmod 15)$. Now there is a simple theorem with orders. Suppose $\displaystyle n$ is a positive integer such that $\displaystyle a^n \equiv 1(\bmod p)$ then $\displaystyle k|n$*. This theorem is telling us that the order must divide any exponent which raises $\displaystyle a$ congruent to $\displaystyle 1$. So in the above proof we concluded that $\displaystyle k|p$ but since $\displaystyle p$ is a prime it forces $\displaystyle k=p$.

*)In case you want to see the proof it is simple. We can write $\displaystyle n=qk+r$ where $\displaystyle 0\leq r < k$ by the division algorithm. That means $\displaystyle a^n = a^{qk+r} = \left( a^k \right)^q a^r \equiv a^r (\bmod p)$ but $\displaystyle a^n \equiv 1(\bmod p)$ so $\displaystyle a^r \equiv 1(\bmod p)$ but that is impossible since $\displaystyle r<k$ and $\displaystyle k$ is__least__so $\displaystyle r=0$. Which means $\displaystyle n=qk+r\implies n=qk$. And so clearly $\displaystyle k|n$.