# Math Help - Help with Fermat's Little Theorem

1. ## 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!

2. 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$.

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

4. 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$.