Evaluate all the square roots of 4 mod 77.

Question

I have an exam coming up an this will be one style of question can anyone please walk me through how it is done? Sorry I am just totally confused and do not how to start

Evaluate all the square roots of 4 mod 77, Using the Chinese Remainder Theorem

Answer 1

We have to solve $$x^2-4=(x-2)(x+2)\equiv 0\ (\ mod\ 77\ )$$

The solutions $2$ and $75$ are easy to determine (One of the factors is $0$ or $77$). Another solution is given by $x-2=7$ and $x+2=11$ because this happens to have a solution ($x=9$ satisfies both equations). Then $68$ must also be a solution because of $68\equiv -9\ (\ mod\ 77\ )$.

The $4$ solutions with $0\le x<77$ are therefore $2,9,68$ and $75$. No more solution exist because $77$ is the product of two dinstint primes.

Using the Chinese Remainder Theorem we have the following cases

$x\equiv 2\ (\ mod\ 7\ )$ and $x\equiv 2\ (\ mod\ 11\ )$

$x\equiv 2\ (\ mod\ 7\ )$ and $x\equiv -2\ (\ mod\ 11\ )$

$x\equiv -2\ (\ mod\ 7\ )$ and $x\equiv 2\ (\ mod\ 11\ )$

$x\equiv -2\ (\ mod\ 7\ )$ and $x\equiv -2\ (\ mod\ 11\ )$

leading to the solutions I already mentioned.

Note that

$$x=56a+22b\ modulo\ 77$$ solves the equation system

$$x\equiv a\ (\ mod\ 11\ )$$

$$x\equiv b\ (\ mod\ 7\ )$$

Using that $a\equiv b\ (\ mod\ n\ )$ is equivalent to $n|a-b$, we have the following cases :

• 1) 7|x-2 and 11|x+2 implying 77|x^2-4=(x-2)(x+2)

• 2) 11|x-2 and 7|x+2 implying 77|x^2-4=(x-2)(x+2)

• 3) 77|x-2

• 4) 77|x+2

Answer 2

In the case that $n^2\equiv 4\pmod{77}$ that implies that $n^2\equiv 4\pmod{11}$ and $n^2\equiv 4\pmod{7}$

As each of these are prime, they form a field and there is a unique multiplicative and additive inverse for each.

$n^2\equiv 4\pmod{11}\Rightarrow \begin{cases}n\equiv 2\pmod{11}\\~~~\text{or}\\n\equiv 9\pmod{11}\end{cases}$

Also,

$n^2\equiv 4\pmod{7}\Rightarrow \begin{cases}n\equiv 2\pmod{7}\\~~~\text{or}\\n\equiv 5\pmod{7}\end{cases}$

For each choice, you will find a unique result modulo $77$ for $n$ by the Chinese Remainder Theorem.

For example, $n\equiv 2\pmod{11}$ and $n\equiv 2\pmod{7}$ implies that $n\equiv 2\pmod{77}$ while $n\equiv 9\pmod{11}$ and $n\equiv 5\pmod{7}$ implies that $n\equiv 75\pmod{77}$