Find the value of $777^{1234} \pmod {1111}$

Question

I'm having trouble solving this modulus question with irregular and large numbers. After using Euler's Theorem, I managed to simplify the question to

$$777^{234} \pmod {1111}$$ Indeed,

$1111 = 11 * 101$, and therefore

$\phi(1111) = (11 - 1)(101 - 1) = 1000$.

However I have no idea how to continue from here. Any help is appreciated. Thanks.

Answer 1

$777\equiv 7\pmod {11}; 7^{10}\equiv1\pmod{11}$; so $777^{234}\equiv7^4\pmod{11}$ and finally $777^{234}\equiv3\pmod {11}$

$777\equiv70\pmod {101}$; $70^5\equiv 6\pmod{101}$; $(70^5)^{40}\equiv1\pmod{101}$...

Hope this helps you get to the end.

Answer 2

HINT.- One has $1111=11\cdot101 \\777\equiv7\pmod{11}\equiv{70}\pmod{101}\\\\1234=2\cdot617\\ 617=56\cdot11+1=6\cdot101+11$ Consequently we have $$777^{1234}\equiv7^{2(56\cdot11+1)}\equiv49^{56\cdot11}\cdot49\equiv49^2\pmod{11}\equiv5^2\pmod{11}\\777^{1234}\equiv7^{2(6\cdot101+11)}\equiv49\cdot49^{11}\equiv49^{12}\equiv88\pmod{101}$$ So you have $$x\equiv3\pmod{11}\\x\equiv88\pmod{101}$$ Apply now chinese theorem.