Modulo arithmetic with large numbers

Question

I'm in high school and writing a paper on the mathematics behind RSA encryption. I now have come to the point where I have to solve: $50^{61} \pmod{77}$ Then, as on https://math.berkeley.edu/~kpmann/encryption.pdf page#5, I found the binary expansion: $61 = 32 + 16 + 8 + 4 + 1$

Using binary expansion of $61$: $50^{61} = 50^{32+16+8+4+1}$ Using basic exponent rule: $50^{61} = 50^{32} \times 50^{16} \times 50^8 \times 50^4 \times 50^1$

.. Now I don't know how to continue. In the link I sent, if you go to page 5, they continue but the explanation is a bit confusing to me (bearing in mind their example uses different numbers to mine:

"Now since we only care about the result ($\mod{943}$), we can calculate all the parts of the product ($\mod{943}$). By repeated squaring of $545$, we can get all the exponents that are powers of $2$."

How do I do my calculations then?

Answer 1

Repeated squaring: $$50^2=2500=32\cdot77+36,$$ so $$50^2\equiv36.\tag{1}$$ Squaring both sides of (1), $$50^4=(50^2)^2\equiv36^2=1296=16\cdot77+64,$$ so $$50^4\equiv64.\tag{2}$$ Squaring both sides of (2), $$50^8\equiv(50^4)^2\equiv(64)^2=4096=53\cdot77+15.\tag{3}$$ Squaring both sides of (3), $$50^{16}\equiv\cdots$$

Answer 2

As $77=7\cdot11$ where $(7,11)=1$

$50\equiv1\pmod7\implies50^n\equiv1$ for any integer $n$

$(50,11)=1\implies 50^{11-1}\equiv1\pmod{11}$ using Fermat's Little Theorem

and as $60\equiv0\pmod{10},50^{60}\equiv50^0\equiv1\pmod{11}$

So, $50^{60}-1$ is divisible by $7,11$ hence by lcm$(7,11)$