Xjyuk

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 $143times 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.

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

$!!bmod color#c0031!: ,2^large 5equiv 1,Rightarrow,2^large 47equiv 2^large 2equivcolor#c00 4$

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

thus $ -3equiv 2^large 47equiv color#c004!+!31kequiv 4!+!2kiff 2kequiv -7equiv 22iffcolor#0a0kequiv 11pmod!29$

Therefore: $,2^large 47 = 4+31color#0a0k = 4+31(color#0a011!+!29n) = 345 + 31(29n)$

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 $big2^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 pmod899$

$qquad bullet quad 2^2^5 = 808^2 = 652864 equiv 190 pmod899$

Finally, multiply the appropriate values together and reduce modulo $899$ and you're done. Clearly, this is not the most expedient approach in this specific case—just look at Bill Dubuque's answer (+1). But marvel at how few computations there are relative to the naive approach!

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^5equiv3$ so $2^15equiv(-2)$ and $2^45equiv(-8)$ so finally $2^47equiv(-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).