2

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?

rahul sharma
  • 291
  • A priori, it would seem possible that there's some $a$ such that $a^2 \equiv 3 \pmod{17}$; and if that were the case, then we would have $3^8 \equiv a^{16} \equiv 1 \pmod{17}$. (As it happens, though, by using quadratic reciprocity you can calculate that there is no such $a$.) – Daniel Schepler Jun 19 '17 at 23:25
  • Since $3^16 = 1$, that means that $(3^8)^2 = 1$.

    Fermat's little theorem only gives that there is a number that works for all of them and that number is at most $16$.

     – user357980 Jun 19 '17 at 23:26

2 Answers2

3

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

B. Goddard
  • 1
  • Not 100% sure the OP understands that the integers mod $17$ form a multiplicative group, so you might want to be explicit there. – Chris Jun 19 '17 at 23:32
0

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

Barry Cipra
  • 79,832