How to find modulo using Euler theorem?

Question

I don't know how that's possible using phi, the question starts with this one:

a) Decompose 870 in prime factors and compute, ϕ(870)

I know how to resolve this, first 870 = 2*3*5*29 and ϕ(870)= 224

Now this is the question I don't know how to resolve:

b) Compute 77^225 modulo 870 [Using a)] <--- The above question

870 isn't even a prime number.

Thanks for any help.

Answer 1

Use euler's theorem. If $(a,n)=1$, then $$ a^{\varphi(n)}\equiv1\pmod{n} $$ Since $77$ and $870$ are coprime (their prime factorizations have no prime in common) $$ 77^{225} \equiv 77^{224}\times77\equiv1\times77\equiv77\pmod{870} $$