Step by step solution to "Solve the congruence x2≡1(mod105)"

Lipossig

Answered question

2021-02-09

Solve the congruence

x^{2} \equiv 1 (mod 105)

Isma Jimenez

Skilled2021-02-10Added 84 answers

Step 1
Given:

x^{2} \equiv 1 (mod 105)

To Solve:
The given congruence

x^{2} \equiv 1 (mod 105)

Step 2
For odd prime p and

a \in Z

, the Legendre symbol

(\frac{a}{p})

is given by,

(\frac{a}{p}) = {(0, if p ∣ a,), (1, if p d o e s \neg \div a and x^{2} \equiv a (mod p) h a s s o l u t i o n .), (- 1, if p d o e s \neg \div a and x^{2} \equiv 1 (mod p) h a s n o s o l u t i o n .)

Hence,

(\frac{a}{p}) = (\frac{b}{p}) w h e r e, a \equiv b (mod p)

...(1)
The Legendre symbol can be evaluated by,

(\frac{a}{p}) = a^{\frac{p - 1}{2}} (mod p)

...(2)
Here,
The congruence is

x^{2} \equiv 1 (mod 105)

a=1 and p =105
The prime factorization of p is,

p = 105 = 3 \times 5 \times 7

Thus,

(\frac{1}{105}) = (\frac{1}{3}) (\frac{1}{5}) (\frac{1}{7})

(\frac{1}{3}) = 1^{\frac{3 - 1}{2}} (mod 3)

(from using formula 2)

(\frac{1}{3}) = 1^{\frac{2}{2}} (mod 3)

(\frac{1}{3}) = 1 (mod 3)

Now,

(\frac{1}{5}) = 1^{\frac{5 - 1}{2}} (mod 5)

(from using formula 2)

(\frac{1}{5}) = 1^{\frac{4}{2}} (mod 5)

(\frac{1}{5}) = 1 (mod 5)

Now,

(\frac{1}{7}) = 1^{\frac{7 - 1}{2}} (mod 7)

(\frac{1}{7}) = 1^{\frac{6}{2}} (mod 7)

(\frac{1}{7}) = 1 (mod 7)

From above,

This is helpful 5 Flag

Do you have a similar question?

Recalculate according to your conditions!

Didn't find what you were looking for?