Problem involving existence of solutions for x^2 = a (mod p)

  • Thread starter demonelite123
  • Start date
  • Tags
    Existence
In summary, we are given the statement "If p is prime and (a, p) = 1, show that x^2 \cong a (mod p) has solutions if a^{\frac{p-1}{2}} \cong 1 (mod p) and does not have solutions if a^{\frac{p-1}{2}} \cong -1 (mod p) .", and asked to prove it. The proof involves considering the numbers from 1 to p-1 and pairing them in a certain way, similar to Wilson's proof of Wilson's theorem. By raising both sides of the
  • #1
If p is prime and (a, p) = 1, show that [itex] x^2 \cong a (mod p) [/itex] has solutions if [itex] a^{\frac{p-1}{2}} \cong 1 (mod p) [/itex] and does not have solutions if [itex] a^{\frac{p-1}{2}} \cong -1 (mod p) [/itex].

So because of Euler's theorem i know that [itex] a^{p-1} \cong 1 (mod p) [/itex] and from the hypothesis [itex] a^{\frac{p-1}{2}} \cong 1 (mod p) [/itex]. I am first trying to show that [itex] x^2 \cong a (mod p) [/itex] has solutions. I've tried things such as multiplying both sides of the first 2 congruences by a, [itex] a^{p} \cong a (mod p) [/itex] and [itex] aa^{\frac{p-1}{2}} \cong a (mod p) [/itex] so [itex] aa^{\frac{p-1}{2}} \cong a^p (mod p) [/itex]. and multiplying by the inverse of [itex] a^{\frac{p-1}{2}} [/itex] on both sides i get [itex] a \cong a^{\frac{p-1}{2}} (mod p) [/itex]. but i can't seem to find such an x since i don't think i can split [itex] a^{\frac{p-1}{2}} [/itex] into something of the form [itex] x^2 [/itex]. i have been trying to manipulate the 2 congruences but i can't seem to find a way to show that [itex] x^2 \cong a (mod p) [/itex] has a solution. can someone offer a hint or two in the right direction? thanks!
 
Physics news on Phys.org
  • #2
First, the question probably says that p is an odd prime; with p=2 the question has not much sense, since [itex]1 \equiv -1 \pmod 2[/itex]. Then the exponent (p-1)/2 is always an integer, by the way.

When looking for a solution "x", you consider the numbers 1, 2,..., p-1, because 0 is not going to be a solution of your equation: "a" is non-zero if (a,p)=1. Now, play with a small numerical example, p=7 and a=3, to get some idea. Play with these numbers to see which multiply to give 3: 1x3, 2x5, 4x6 all give 3 modulo 7. (So none repeats: it's always one number times a different number, so your congruence has no solutions in this case.) At this point, go back to your book and review the proof of Wilson's Theorem... you may find it illustrative.

P.S.: By the way, if something (in this case, 5) multiplies 2 in order to give 3 (mod 7), then nothing else will multiply 2 to give 3 (mod 7). It's not hard to check that the congruence [itex]by \equiv a \pmod p[/itex], for some given "b" (and "a" and "p") has a unique solution (when "a" and "b" are non-zero, that is).

P.P.S: This is a known statement, so this line of proof is not mine -- I cheated and saw the proof so that you don't have to, and can have a shot at trying yourself.
 
Last edited:
  • #3
i've reviewed the proof of Wilson's theorem but i don't know how that helps me out. the proof uses the fact that [itex] x^2 \equiv 1 (mod p) [/itex] has soutions [itex] x \equiv 1 (mod p) [/itex] or [itex] x \equiv -1 (mod p) [/itex]. but i can't figure out how to apply that to [itex] x^2 \equiv a (mod p) [/itex].

i've also tried taking [itex] x^2 \equiv a (mod p) [/itex] and raising both sides to the power of (p-1)/2. then i get [itex] x^{p-1} \equiv a^\frac{p-1}{2} (mod p) [/itex]. in the case where [itex] a^\frac{p-1}{2} \equiv 1 (mod p) [/itex] i can see that [itex] x^{p-1} \equiv 1 (mod p) [/itex] which is definitely a true statement given that (x, p) = 1. On the other hand, when [itex] a^\frac{p-1}{2} \equiv -1 (mod p) [/itex] i can see that [itex] x^{p-1} \equiv -1 (mod p) [/itex] and if (x, p) = 1 then this cannot be true for any x so there are no solutions in this case. I'm not sure if this argument is valid or not but its all i could think up of as of now. if this is wrong i would greatly appreciate some further assistance on this problem.
 
  • #4
Perhaps I had in mind an analogy too remote, but in Wilson's proof there is a pairing of the numbers from 1 to p-1 which is reminiscent (not exact) of what a possible proof for the statement here would be. (And Wilson's result is involved at some point after this pairing. Think: if 1x3, 2x5, 4x6, all give 3 modulo 7, how do you obtain the factorial of 6? And what power of 3 is that?) Leaving that aside for a moment, let me go to the work you did.

I think it's only half there. You need to prove two statements: one for the situation where the power of "a" is 1, and one for when it is -1. I think the contradiction you find for the second part is OK, but not finding a contradiction in the first part is not a proof. Some rephrasing could also be used: raising the statement [itex]x^2 \equiv a \pmod p[/itex] to the power of (p-1)/2 is fine... as long as your reader is remainded that, at this stage, we don't know if an "x" exists at all. The assumptions are the statements about 1 and -1, on each case; the existence of a solution to the quadratic congruence is the place to arrive, and you'd only assume the latter (or its new version after raising to the (p-1)/2 power) when the intention is to find a contradiction.

Back to my original suggestion, in my defense :) I should say that the "known" statement I mentioned happens to consist actually of "if-and-only-if" propositions, thus stronger than the one you set to prove. If you just need to deliver a proof of the milder statement as given, maybe (I don't know) a complete proof (more than half of it) can be found on the direction you are attempting; I can't think of one right now, but that may be me.

I hope I'm not being too sadistic :), I just had the impression that you wanted to do this yourself. Also, please let me know if I missed something in your reasoning about the first part of the proof.
 
  • #5
demonelite123 said:
i've reviewed the proof of Wilson's theorem but i don't know how that helps me out. the proof uses the fact that [itex] x^2 \equiv 1 (mod p) [/itex] has soutions [itex] x \equiv 1 (mod p) [/itex] or [itex] x \equiv -1 (mod p) [/itex]. but i can't figure out how to apply that to [itex] x^2 \equiv a (mod p) [/itex].

i've also tried taking [itex] x^2 \equiv a (mod p) [/itex] and raising both sides to the power of (p-1)/2. then i get [itex] x^{p-1} \equiv a^\frac{p-1}{2} (mod p) [/itex]. in the case where [itex] a^\frac{p-1}{2} \equiv 1 (mod p) [/itex] i can see that [itex] x^{p-1} \equiv 1 (mod p) [/itex] which is definitely a true statement given that (x, p) = 1. On the other hand, when [itex] a^\frac{p-1}{2} \equiv -1 (mod p) [/itex] i can see that [itex] x^{p-1} \equiv -1 (mod p) [/itex] and if (x, p) = 1 then this cannot be true for any x so there are no solutions in this case. I'm not sure if this argument is valid or not but its all i could think up of as of now. if this is wrong i would greatly appreciate some further assistance on this problem.
You might consider that the complete set of residues equals {r^n} with r being a primitive root of p and 0 < n < p. Then the set with n even will be the square residues while the set with n odd will be the non-square residues. n(p-1)/2 will then be a multiple of p-1 when n is even but will only be a multiple of (p-1)/2 when n is odd.
 

1. What is the meaning of "x^2 = a (mod p)" in the context of this problem?

In this problem, x^2 = a (mod p) means that we are looking for a value of x that, when squared and divided by p, leaves a remainder of a. This is known as a modular equation and is used in number theory to find solutions to certain equations.

2. Why is finding solutions for x^2 = a (mod p) important?

Finding solutions for x^2 = a (mod p) is important in number theory and cryptography. It allows us to understand properties of prime numbers and to create secure encryption methods.

3. Can x^2 = a (mod p) have multiple solutions?

Yes, x^2 = a (mod p) can have multiple solutions. In fact, for every value of a, there are either two solutions or no solutions for x^2 = a (mod p). These solutions can be found by using the quadratic formula.

4. How can we prove the existence of solutions for x^2 = a (mod p)?

The existence of solutions for x^2 = a (mod p) can be proven using the Chinese Remainder Theorem. This theorem states that if two numbers, p and q, are relatively prime, then any set of remainders mod p and mod q can be combined into a unique remainder mod pq. This allows us to find solutions for x^2 = a (mod p) by combining solutions for x^2 = a (mod q) and x^2 = a (mod p).

5. Are there any restrictions on the values of a and p in x^2 = a (mod p)?

Yes, there are restrictions on the values of a and p in x^2 = a (mod p). Specifically, p must be a prime number and a must be a quadratic residue mod p. This means that there must exist a number b such that b^2 = a (mod p). If a is not a quadratic residue mod p, then x^2 = a (mod p) will have no solutions.

Suggested for: Problem involving existence of solutions for x^2 = a (mod p)

Replies
5
Views
797
Replies
52
Views
2K
Replies
5
Views
733
Replies
1
Views
681
Replies
3
Views
707
Replies
1
Views
2K
Back
Top