x^2=14(mod p) where p is prime.
Given: solution exists or basically, a^((p-1)/2)=1 (mod p).
Find values of p.
Here is my professor's approach to this problem. But based on my commentaries.
The way this problem is actually solved is through a most beautiful result, Quadradic Reciprocity.
I will use the following theorem.
Theorem: Let p be an odd prime then (2/p)=1 if p=1,7(mod 8) otherwise (2/p)=-1.
Proof: This is a well-known fact, that can be easily be proven with Gauss' Lemma.
Now, I said there are two cases to consider.
1) Both Legendre symbols are 1.
2) Both Legendre symbols are -1.
I shall do case #1 and leave case #2 for you to do.
Throughout this derivation you are expected to know the basic properties of the Legendre symbol.
----
So in case #1 we require that (2/p)=1 and (7/p)=1.
Note, by theorem, (2/p)=1 for p=1,7(mod 8).
Now, to do (7/p) we will rely on Quadradic Reciprocity.
Thus,
(7/p) = (p/7) if p=1(mod 4).
(7/p) = -(p/7) if p=3(mod 4).
Now let us do the first case first with p=1(mod 4).
Under modulo 7, p=1,2,3,4,5,6(mod 7)
Check each one:
(1/7)=1, (2/7)=1 , (3/7)=-1, (4/7)=1, (5/7)=-1, (6/7)=-1
This tells us that if p=1(mod 4).
Then p=1,2,4(mod 7).
And if p=3(mod 4).
Then p=3,5,6(mod 7).
Combining these under the same modulos since gcd(4,7)=1. With Chinese Remainder Theorem.
Thus, p= 1,3,9,19,25,27 (mod 28)
So if you multiply 8k+1,8k+7 with this out you get,
p=1,3,7,9,19,21,25,27,63,133,175,189(mod 224)
And this is only the first case.
The second case will produce more prime forms.