CammieInfinity
Badges: 1
Rep:
?
#1
Report Thread starter 6 years ago
#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
reply
username1560589
Badges: 20
Rep:
?
#2
Report 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
reply
DFranklin
Badges: 18
Rep:
?
#3
Report 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 = Z_p^* 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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

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%

Watched Threads

View All