4
$\begingroup$

As the title says, I'm looking to find all solutions to $$x^2 \equiv 4 \pmod{91}$$ and I am not exactly sure how to proceed.

The hint was that since 91 is not prime, the Chinese Remainder Theorem might be useful.

So I've started by separating into two separate congruences: $$x^2 \equiv 4 \pmod{7}$$ $$x^2 \equiv 4 \pmod{13}$$

but now I'm confused about how to apply the CRT so I'm a bit stuck, and I'd appreciate any help or hints!

$\endgroup$
4
  • $\begingroup$ are you able to use the law of quadratic reciprocity? $\endgroup$
    – AnotherPerson
    Nov 4, 2015 at 8:28
  • 3
    $\begingroup$ Since both 13 and 7 are prime, and 4 is a square, why don't you try subtracting that 4 over to the side of x^2 and factoring? $\endgroup$
    – AnotherPerson
    Nov 4, 2015 at 8:34
  • 2
    $\begingroup$ Note that $x^2 \equiv 4$ (mod$7$) implies $x \equiv 2$ or $x \equiv 5$ mod$7$. AND $x^2 \equiv 4$ (mod$13$) implies $x \equiv 2$ or $x \equiv 11$ mod$13$. $\endgroup$
    – Nizar
    Nov 4, 2015 at 8:37
  • $\begingroup$ Thanks for the hints, I've got it now! But out of curiosity, @SirJective how could the law of quadratic reciprocity be used here? $\endgroup$
    – catherine
    Nov 4, 2015 at 9:12

2 Answers 2

Reset to default
3
$\begingroup$

We begin with your system of equations: $$\begin{cases} x^2 \equiv 4 \pmod{7} \\ x^2 \equiv 4 \pmod{13} \end{cases}$$

Then, solving each congruence, we obtain the system: $$\begin{cases} x \equiv \pm 2 \pmod{7} \\ x \equiv \pm 2 \pmod{13} \end{cases}$$

We therefore have four systems of linear congruences, each with a unique solution by the Chinese Remainder Theorem:

$$\begin{cases} x \equiv 2 \pmod{7} \\ x \equiv 2 \pmod{13} \end{cases} \tag{1}$$

$$\begin{cases} x \equiv 2 \pmod{7} \\ x \equiv - 2 \pmod{13} \end{cases} \tag{2}$$

$$\begin{cases} x \equiv - 2 \pmod{7} \\ x \equiv 2 \pmod{13} \end{cases} \tag{3}$$

$$\begin{cases} x \equiv - 2 \pmod{7} \\ x \equiv -2 \pmod{13} \end{cases} \tag{4}$$

These four solutions will be distinct modulo $91$, it remains to find them!

$\endgroup$
1
  • 1
    $\begingroup$ Very clear and helpful, thank you! $\endgroup$
    – catherine
    Nov 4, 2015 at 8:59
1
$\begingroup$

By the Chinese remainder theorem you get an isomorphism between those two rings :

$$\psi:\frac{\mathbb{Z}}{91\mathbb{Z}}\rightarrow \frac{\mathbb{Z}}{7\mathbb{Z}}\times \frac{\mathbb{Z}}{13\mathbb{Z}} $$

$$x\mapsto (x\text{ mod } 7,x\text{ mod } 13) $$

it means that to solve $4=s^2$ mod $91$ you only need to solve $\psi(4)=\psi(s)^2$ which in turn gives $4=s_1^2$ mod $7$ and $4=s_2^2$ mod $13$. Now we are mod some prime numbers, because we have two obvious solutions those are the only one. In other word $\psi(s)=(\epsilon_12,\epsilon_22)$ where $\epsilon_i\in\{\pm 1\}$. This give four solutions. Now you only need to find the inverse function of $\psi$ (it is a classical computation) to explicitely have the four solutions to the equation $4=s^2$ mod $91$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .