lean_workbook_plus_3463

(II)\nSimilar to the solution posted above for (I), we can break this up into two parts, $3^{33}+77\mod4$ and $3^{33}+77\mod25$ .\n\n $3^{33}+77\mod4 \equiv (-1)^{33}+1\mod4 \equiv -1+1\mod4 \equiv 0\mod4$ .\nUsing Euler's Totient Theorem, $3^{20}\equiv 1\mod25$ . It is easy to see that $3^3 \equiv 2\mod25$ as well.\n\nWe can now write the second equation as $(3^{20})(3^{3})^{4}(3^1)+77\mod25 \equiv (1)(2)^4(3) + 77\mod25 \equiv 48+77\mod25 \equiv 125\mod25 \equiv 0\mod25.$\n\nBecause this is congruent to 0 mod 25 and 4, it is congruent to 0 mod 100.