You are Here: Home >< Maths

# 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?
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.
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.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: January 26, 2015
Today on TSR

### Three reasons you may feel demotivated right now

...and how to stay positive

### Can I get A*s if I start revising now?

Discussions on TSR

• Latest
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE