Proving a solution exist? (mod p)

  • Thread starter firefly767
  • Start date
  • #1
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:
 

Answers and Replies

  • #2
1,056
0
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.
 
  • #3
disregardthat
Science Advisor
1,866
34
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.
 
  • #4
841
0
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
 
  • #5
124
0
You have to look at the group of units of the field [tex]\textbf{F}_{p} = \textbf{Z}/p\textbf{Z}[/tex]. For every prime [tex]{p}[/tex] the group [tex]\textbf{F}_{p}^{*}[/tex] (with respect to multiplication) is of order [tex]p - 1[/tex] and cyclic as well. Now it is easy to count squares and cubics. Tell me if you need more help.
 
Last edited:

Related Threads on Proving a solution exist? (mod p)

Replies
5
Views
5K
Replies
5
Views
4K
Replies
2
Views
7K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
6K
  • Last Post
Replies
4
Views
7K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
13
Views
10K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
1
Views
3K
Top