# Help with Fermat's Little Theorem

• Mar 3rd 2008, 03:29 PM
thebrownguy01
Help 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, 03:45 PM
ThePerfectHacker
Quote:

Originally Posted by thebrownguy01
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!

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

Originally Posted by thebrownguy01
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

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

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