Basic doubt in Fermat's Little Theorem The minimum positive integer p such that 3^p modulo 17 = 1 is
a. 5
b. 8
c. 12
d. 16
I got the answer as 16  by applying Fermat's Little theorem. But does this theorem makes sure that is the min. value?I mean is it possible to have number less than 16 which can satisfy the above equation?How can i prove that whether or not this is the smallest p satisfying the equation?
 A: FlT tells you that $3^{16} \equiv 1 \pmod{17}$ but doesn't guarantee that this
is the minimum.  (We'd call that the "order" of $3$.)  But you do know that the order divides $16$, so you just have to check that $3^2$, $3^4$, $3^8$ are NOT $1 \pmod{17}.$   Actually, if you think about it, you just have to check that $3^8 \equiv -1 \pmod{17}.$
A: If you have the law of Quadratic Reciprocity at your disposal, then it's easy to see that
$$\left(3\over17\right)=\left(17\over3\right)=\left(2\over3\right)=-1$$
which implies $3^8\equiv-1$ mod $17$.  The other options are ruled out on the more elementary grounds that $3^d\equiv1$ mod $p$ with $1\lt d\lt p$ implies $d\mid p-1$.
If all you have is Fermat's little theorem, then it may be easiest to compute
$$3^3=27\equiv-7\implies3^6\equiv(-7)^2=49\equiv-2\implies3^{12}\equiv(-2)^2=4\implies3^{24}\equiv4^2=16\equiv-1$$
from which you can see that 
$$-2\equiv3^6=3\cdot3^5\implies 3^5\not\equiv1$$
and
$$-1\equiv3^{24}=3^{16}\cdot3^8\equiv1\cdot3^8\implies 3^8\not\equiv1$$
(and, of course, $3^{12}\equiv4\not\equiv1$).
