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
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.Quote:
Originally Posted by florest
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
(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??
Here is my professor's approach to this problem. But based on my commentaries.Quote:
Originally Posted by florest
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.