Proving a solution exist? (mod p)

[firefly767]

hi all,

i am wondering how to go about proofs such as the following:

1. if p is an odd prime, show that x^2== a(mod p) has a solution for exactly half the values of a between 1 and p-1 inclusive. if 1<=a<=p-1, and x^2 == a (mod p) has a solution show that it has exactly 2 congrence classes of solutions modulo p.

2. does x^3 == a (mod p) always have a solution for every value of a, when p is prime?

it'll be much appreciated you can also give me some tips as to the ways to approach proofs involving mod, congruence classes (one is exactly the other) etc... thanks in advance!

 

[robert Ihnot]

We know by Fermat's Little Theorem, that x^(p-1) ==1 Mod p for all residues of the multiplicatie group. This handles p-1 cases. But we can factor for p odd, arriving at
x^(p-1)/2 -1 == 0 and x^((p-1)/2 ==1 Mod P.

Of the p-1 residues half are in one set, and half in the other since a polynominal of order n, Mod p can have no more than n roots, and here all the roots of the multiplicative group are present. The half of the form x^(p-1)/2 ==1 are quadratic residues.

 

[disregardthat]

1. Suppose a^2 = b^2 mod p. What can you deduce?

2. Try to see if that is possible by considering different primes p.

 

[ramsey2879]

hi all,

i am wondering how to go about proofs such as the following:

1. if p is an odd prime, show that x^2== a(mod p) has a solution for exactly half the values of a between 1 and p-1 inclusive. if 1<=a<=p-1, and x^2 == a (mod p) has a solution show that it has exactly 2 congrence classes of solutions modulo p.

2. does x^3 == a (mod p) always have a solution for every value of a, when p is prime?

it'll be much appreciated you can also give me some tips as to the ways to approach proofs involving mod, congruence classes (one is exactly the other) etc... thanks in advance!

1. For i = 1 to (p-1)/2 show that i^2 == (p-i)^2
2 For i and j in the range <1 - (p-1)/2> show that i^2 <> j^2 mod p

 

[Outlined]

You have to look at the group of units of the field \textbf{F}_{p} = \textbf{Z}/p\textbf{Z}. For every prime {p} the group \textbf{F}_{p}^{*} (with respect to multiplication) is of order p - 1 and cyclic as well. Now it is easy to count squares and cubics. Tell me if you need more help.