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!!!:smile:

[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!!!:smile:
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.