(b) x^2 ≡ 6780 (mod 6781)
Determine whether each of the following congruences has a solution in integers.
Anyone know how to do this?
Solving congruences watch
- Thread Starter
- 25-01-2015 17:21
- 25-01-2015 23:51
- 26-01-2015 02:11
Firstly it's pretty important to know (or find out) that 6781 is prime.
For a prime p, the multiplicative group G = has order p-1.
Suppose we can find g with g^2 = -1. Then g^4 = 1. So g has order 4. But by Lagrange, the order of g divides the order of the mutiplicative group. So 4 | p-1.
Conversely, you should know that G is always cyclic, so we can find g s.t. g has order p-1. Then g^(p-1) = 1, but g^(p-1)/2 is not 1, from which we see g^(p-1)/2 = -1. But then setting x = g^(p-1)/4 we have x^2 = -1.