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.

Printable View

- April 28th 2007, 09:35 PMflorestquadratic 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. - April 29th 2007, 06:04 AMThePerfectHacker
- April 29th 2007, 11:08 AMflorest
(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?? - May 2nd 2007, 05:02 PMThePerfectHacker
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.