# Solving congruences

Watch
#1
(b) x^2 ≡ 6780 (mod 6781)

Determine whether each of the following congruences has a solution in integers.

Anyone know how to do this?
0
6 years ago
#2
(Original post by CammieInfinity)
(b) x^2 ≡ 6780 (mod 6781)

Determine whether each of the following congruences has a solution in integers.

Anyone know how to do this?
I can solve it quickly computationally, but can't solve it via any other means.
0
6 years ago
#3
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.
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### Who is winning Euro 2020

France (83)
26.18%
England (108)
34.07%
Belgium (27)
8.52%
Germany (38)
11.99%
Spain (5)
1.58%
Italy (28)
8.83%
Netherlands (10)
3.15%
Other (Tell us who) (18)
5.68%