# Elegant way to prove congruence

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.

• Elegant way to prove what, that $\, 2^{\large 47}\equiv 345\pmod{899}?\$ – Bill Dubuque May 29 at 20:50
• yes (based maybe on previous questions if they're of some use) – ahmed May 29 at 20:55
• It should be easy by CRT, i.e. compute $2^{\large 47}$ mod $29$ & $31$ then lift to their product by CRT. – Bill Dubuque May 29 at 20:56
• Note: $2^5\equiv1\pmod{31}$ – J. W. Tanner May 29 at 21:01

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)$$

• or $4\equiv2^{47}\equiv26+29k\iff-22\equiv-2k\iff k\equiv11\pmod{31}\\$ and therefore: $2^{47}=26+29k=26+29(11+31n)$ – J. W. Tanner May 29 at 21:40

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}$$

Now 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—just look at 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, when written in base-$$2$$, consists of $$n$$ bits, 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). So 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.

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).