3 * (4^50 + 4^50) + (20^48) = 2 (mod 41)
You asked:
Evaluate the congruence relation statement $3 \cdot \left({4}^{50} + {4}^{50}\right) + {20}^{48} \equiv 2 \pmod{41}$.
MathBot Answer:
This congruence relation statement is true.
Two expressions $a$ and $b$ are congruent modulo $n$ if $a - b$ is a multiple of $n$.
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 $4^{50} \pmod{41}$ to $1 \pmod{41}$.
Express $50$ as its unique binary representation
$110010$
or by the sum of powers of two
$2+16+32$,
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{41}}$ | $\textbf{P}$ | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| $1$ | $0$ | ${4}^{1}$ | $4$ | $\equiv$ | $4$ | $\pmod{41}$ | ||||
| $2$ | $1$ | ${4}^{2}$ | $4^{2}$ | $\equiv$ | $16$ | $\pmod{41}$ | $1 \cdot 16$ | $\equiv$ | $16$ | $\pmod{41}$ |
| $3$ | $0$ | ${4}^{4}$ | $16^{2}$ | $\equiv$ | $10$ | $\pmod{41}$ | ||||
| $4$ | $0$ | ${4}^{8}$ | $10^{2}$ | $\equiv$ | $18$ | $\pmod{41}$ | ||||
| $5$ | $1$ | ${4}^{16}$ | $18^{2}$ | $\equiv$ | $37$ | $\pmod{41}$ | $16 \cdot 37$ | $\equiv$ | $18$ | $\pmod{41}$ |
| $6$ | $1$ | ${4}^{32}$ | $37^{2}$ | $\equiv$ | $16$ | $\pmod{41}$ | $18 \cdot 16$ | $\equiv$ | $1$ | $\pmod{41}$ |
After successive multiplication, $P = 1$, so $4^{50} \equiv 1 \pmod{41}$.
Simplify $20^{48} \pmod{41}$ to $37 \pmod{41}$.
Express $48$ as its unique binary representation
$110000$
or by the sum of powers of two
$16+32$,
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{41}}$ | $\textbf{P}$ | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| $1$ | $0$ | ${20}^{1}$ | $20$ | $\equiv$ | $20$ | $\pmod{41}$ | ||||
| $2$ | $0$ | ${20}^{2}$ | $20^{2}$ | $\equiv$ | $31$ | $\pmod{41}$ | ||||
| $3$ | $0$ | ${20}^{4}$ | $31^{2}$ | $\equiv$ | $18$ | $\pmod{41}$ | ||||
| $4$ | $0$ | ${20}^{8}$ | $18^{2}$ | $\equiv$ | $37$ | $\pmod{41}$ | ||||
| $5$ | $1$ | ${20}^{16}$ | $37^{2}$ | $\equiv$ | $16$ | $\pmod{41}$ | $1 \cdot 16$ | $\equiv$ | $16$ | $\pmod{41}$ |
| $6$ | $1$ | ${20}^{32}$ | $16^{2}$ | $\equiv$ | $10$ | $\pmod{41}$ | $16 \cdot 10$ | $\equiv$ | $37$ | $\pmod{41}$ |
After successive multiplication, $P = 37$, so $20^{48} \equiv 37 \pmod{41}$.
After simplifying all powers, we are left with $3 \cdot \left(1 + 1\right) + 37 \equiv 2 \pmod{41}$.
Evaluating both sides: $3 \cdot \left(1 + 1\right) + 37 \equiv 2 \pmod{41} \mapsto 43 \equiv 2 \pmod{41}$
$43 - 2 = 41$, which is a multiple of $41$, so the congruence relation statement is true.
This is because dividing $41$ by $41$ produces $1$ with a remainder of $0$.