# Math Help - quadratic congruences

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.

2. Originally Posted by florest
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.
First it is trivial for p=2.

You need to find all values for odd primes p such that, the Legendre symbol, (14/p)=1.
That is,
(2/p)*(7/p)=1
Thus,
(2/p)=(7/p)=1
or
(2/p)=(7/p)=-1

3. (2/p)=(7/p)=1
or
(2/p)=(7/p)=-1
Hmm.
would that mean
1=2^((p-1)/2) mod p
1=7^((p-1)/2) mod p

or
-1=2^((p-1)/2) mod p
-1=7^((p-1)/2) mod p
?

Wouldn't that exist for all odd prime values of p excluding 7??

4. Originally Posted by florest
(2/p)=(7/p)=1
or
(2/p)=(7/p)=-1
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).

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.