# Solve the congruence x^2 -= 1 (mod 105)

Solve the congruence ${x}^{2}\equiv 1\left(\text{mod}105\right)$
You can still ask an expert for help

## Want to know more about Congruence?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Isma Jimenez
Step 1
Given:
${x}^{2}\equiv 1\left(\text{mod}105\right)$
To Solve:
The given congruence ${x}^{2}\equiv 1\left(\text{mod}105\right)$
Step 2
For odd prime p and $a\in \mathbb{Z}$, the Legendre symbol $\left(\frac{a}{p}\right)$ is given by,
$\left(\frac{a}{p}\right)=\left\{\left(0,\phantom{\rule{1em}{0ex}}\text{if}\phantom{\rule{1em}{0ex}}p\mid a,\right),\left(1,\phantom{\rule{1em}{0ex}}\text{if}\phantom{\rule{1em}{0ex}}pdoes\mathrm{¬}÷a\phantom{\rule{1em}{0ex}}\text{and}\phantom{\rule{1em}{0ex}}{x}^{2}\equiv a\left(\text{mod}p\right)hassolution.\right),\left(-1,\phantom{\rule{1em}{0ex}}\text{if}\phantom{\rule{1em}{0ex}}pdoes\mathrm{¬}÷a\phantom{\rule{1em}{0ex}}\text{and}\phantom{\rule{1em}{0ex}}{x}^{2}\equiv 1\left(\text{mod}p\right)hasnosolution.\right)$
Hence,$\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)where,a\equiv b\left(\text{mod}p\right)$...(1)
The Legendre symbol can be evaluated by,
$\left(\frac{a}{p}\right)={a}^{\frac{p-1}{2}}\left(\text{mod}p\right)$...(2)
Here,
The congruence is ${x}^{2}\equiv 1\left(\text{mod}105\right)$
a=1 and p =105
The prime factorization of p is,
$p=105=3×5×7$
Thus,
$\left(\frac{1}{105}\right)=\left(\frac{1}{3}\right)\left(\frac{1}{5}\right)\left(\frac{1}{7}\right)$
$\left(\frac{1}{3}\right)={1}^{\frac{3-1}{2}}\left(\text{mod}3\right)$ (from using formula 2)
$\left(\frac{1}{3}\right)={1}^{\frac{2}{2}}\left(\text{mod}3\right)$
$\left(\frac{1}{3}\right)=1\left(\text{mod}3\right)$
Now,
$\left(\frac{1}{5}\right)={1}^{\frac{5-1}{2}}\left(\text{mod}5\right)$ (from using formula 2)
$\left(\frac{1}{5}\right)={1}^{\frac{4}{2}}\left(\text{mod}5\right)$
$\left(\frac{1}{5}\right)=1\left(\text{mod}5\right)$
Now,
$\left(\frac{1}{7}\right)={1}^{\frac{7-1}{2}}\left(\text{mod}7\right)$
$\left(\frac{1}{7}\right)={1}^{\frac{6}{2}}\left(\text{mod}7\right)$
$\left(\frac{1}{7}\right)=1\left(\text{mod}7\right)$
From above,