Elegant way to prove congruence

elementary-number-theorymodular arithmeticnumber theory

I'm stuck with the last question of this exercise

1) First question asks to solve the linear diophantine

$$143x-840y=1$$

based on the remark $143\times 47 – 840 \times 8 = 1$ (done)

2) second question asks to prove that if a natural $n$ is coprime with $899$, then

$$n^{840} \equiv 1 \mod 899 $$ (done using Fermat's little theorem on $31$ and $29$ knowing that $899 = 31 \times 29$)

3) This last question asks to determine an integer between $100$ and $1000$ such that

$$n^{143} \equiv 2 \mod 899$$

I proved the problem reduces to determining the remainder of $2^{47}$ when divided by $899$ wolframalpha says it's $345$ but I still can't see any elegant way to prove it.

Thanks.

Best Answer

Problem: We want to find the $x$ in range $0 \leq x \leq 898$ such that $2^{47} \equiv x \pmod{899}$.

Here's a relatively fast method for general problems like these called square-and-multiply:

We can write $47 = 2^5 + 2^3 + 2^2 + 2^1 + 2^0. \ $ Therefore, $2^{47} = 2^{2^5} \cdot 2^{2^3} \cdot 2^{2^2} \cdot 2^{2} \cdot 2. \ $ And now we can compute these values $\big\{2^{2^k} \big\}_{k=0}^5$ via iterative squaring (and reducing modulo $899$ when necessary):

$\qquad \bullet \ \quad 2^2 \ = \ 4$

$\qquad \bullet \ \quad 2^{2^2} = \ 4^2 = \ 16$

$\qquad \bullet \ \quad 2^{2^3} \ = \ (16)^2 \ = \ 256$

$\qquad \bullet \ \quad 2^{2^4} \ = \ 256^2 \ = \ 65536 \ \equiv \ 808 \pmod{899}$

$\qquad \bullet \ \quad 2^{2^5} \ = \ 808^2 \ = \ 652864 \ \equiv \ 190 \pmod{899}$

Multiply the appropriate values together, reduce modulo $899$, and you're done(!!). Clearly, this is not the most computationally efficient approach in this specific case—see Bill Dubuque's answer (+1). But marvel at just how few computations there are relative to the naïve approach!

In general, if the exponent consists of $n$ bits when written in base-$2$, then—if I'm not mistaken—one needs to perform a maximum of $2n-3$ multiplications when using square-and-multiply (plus modulo reductions, if desired). Thus, the number of multiplications required grows logarithmically with the size of the exponent, whereas the number of multiplications required for naïve exponentiation grows linearly.