Elegant way to prove congruence

Question

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.

Answer 1

It's easy mental arithmetic to compute $2^{\large 47}$ mod $31$ & $29$ then lift it to $31\cdot 29$ by CRT.

$\!\!\bmod \color{#c00}{31}\!:\ \ \,2^{\large 5}\equiv 1\,\Rightarrow\,2^{\large 47}\equiv 2^{\large 2}\equiv\color{#c00} 4$

$\!\!\bmod 29\!:\,\ 2^{\large 28}\!\equiv 1\,\Rightarrow\,2^{\large 47}\equiv 2^{\large -9}\equiv 1/(-10)\equiv 30/(-10)\equiv -3$

thus $\ {-}3\equiv 2^{\large 47}\equiv \color{#c00}{4\!+\!31}k\equiv 4\!+\!2k\iff 2k\equiv -7\equiv 22\iff\color{#0a0}{k\equiv 11\pmod{\!29}}$

Therefore: $\,2^{\large 47} = 4+31\color{#0a0}k = 4+31(\color{#0a0}{11\!+\!29}n) = 345 + 31(29n)$

Answer 2

As suggested in the comments, evaluate $2^{47}$ mod $29$ and $31$. For $31$ we quickly get $4$ mod $31$.

For mod $29$, note that $2^5\equiv3$ so $2^{15}\equiv(-2)$ and $2^{45}\equiv(-8)$ so finally $2^{47}\equiv(-3)$.

From here we do a quick CRT to finish off the problem (assuming you know how to do it; the gist is essentially the Euclidean Algorithm, modified slightly).

Answer 3

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.