x = $2786^{280}$mod 281
You asked:
Solve the linear congruence $x \equiv {2786}^{280} \pmod{281}$.
MathBot Answer:
There is a unique solution for $x$ in the congruence relation $x \equiv {2786}^{280} \pmod{281}$: $\textcolor{#228B22}{x = 1}$
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^{280} \pmod{281}$ to $1 \pmod{281}$.
Express $280$ as its unique binary representation
$100011000$
or by the sum of powers of two
$8+16+256$,
then compute the base to the power of each of those smaller numbers and take their product.
| $\textbf{Step}$ | $\textbf{Bit}$ | $\textbf{Power}$ | $\textbf{Power} \mathbf{\pmod{281}}$ | $\textbf{P}$ | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| $1$ | $0$ | ${2786}^{1}$ | $2786$ | $\equiv$ | $257$ | $\pmod{281}$ | ||||
| $2$ | $0$ | ${2786}^{2}$ | $257^{2}$ | $\equiv$ | $14$ | $\pmod{281}$ | ||||
| $3$ | $0$ | ${2786}^{4}$ | $14^{2}$ | $\equiv$ | $196$ | $\pmod{281}$ | ||||
| $4$ | $1$ | ${2786}^{8}$ | $196^{2}$ | $\equiv$ | $200$ | $\pmod{281}$ | $1 \cdot 200$ | $\equiv$ | $200$ | $\pmod{281}$ |
| $5$ | $1$ | ${2786}^{16}$ | $200^{2}$ | $\equiv$ | $98$ | $\pmod{281}$ | $200 \cdot 98$ | $\equiv$ | $211$ | $\pmod{281}$ |
| $6$ | $0$ | ${2786}^{32}$ | $98^{2}$ | $\equiv$ | $50$ | $\pmod{281}$ | ||||
| $7$ | $0$ | ${2786}^{64}$ | $50^{2}$ | $\equiv$ | $252$ | $\pmod{281}$ | ||||
| $8$ | $0$ | ${2786}^{128}$ | $252^{2}$ | $\equiv$ | $279$ | $\pmod{281}$ | ||||
| $9$ | $1$ | ${2786}^{256}$ | $279^{2}$ | $\equiv$ | $4$ | $\pmod{281}$ | $211 \cdot 4$ | $\equiv$ | $1$ | $\pmod{281}$ |
After successive multiplication, $P = 1$, so $2786^{280} \equiv 1 \pmod{281}$.
After simplifying all powers, we are left with $x \equiv 1 \pmod{281}$.