Math Problem Solver

There is a unique solution for $x$ in the congruence relation $x \equiv {2786}^{2} \pmod{12}$: $\textcolor{#228B22}{x = 4}$

First, simplify any powers with an integer base, and a positive integer exponent using the binary exponentiation method.

---

Binary Exponentiation Method

Each positive integer has a unique binary representation, that can also be expressed as a sum of powers of two.

A power $b^e$ with an integer base $b$ and a positive integer exponent $e$ can be rewritten according to the identity ${b}^{e_1 + e_2 + \ldots} = {b}^{e_1} \cdot b^{e_2} \cdot \ldots$, where $e_1 + e_2 + \ldots= e$.

Instead of computing one very large power, we can compute the product of several smaller powers.

We can also take advantage of another identity $x \cdot y \pmod n = x \pmod n \cdot y \pmod n$ to reduce the magnitude of the smaller powers before computing their product.

Using a base product of $P = 1$ (the identity element for multiplication and the result of the base case $b^0$), we successively multiply $P$ with the result of each power whose exponent appears in the sum of powers of two, taking its modulus.

We use a sum of powers of two because the next power can easily be acquired by squaring the previous result and taking its modulus.

---

Simplify $2786^{2} \pmod{12}$ to $4 \pmod{12}$.

Express $2$ as its unique binary representation $10$ or by the sum of powers of two $2$,
then compute the base to the power of each of those smaller numbers and take their product.

After successive multiplication, $P = 4$, so $2786^{2} \equiv 4 \pmod{12}$.

---

After simplifying all powers, we are left with $x \equiv 4 \pmod{12}$.

---