Foundations, part 12

Relevant wiki: Euler's Theorem

$\begin{aligned} 128^{100} & \equiv 128^{\color{#3D99F6}100 \bmod \phi(153)} \text{ (mod 153)} & \small \color{#3D99F6} \text{Since }\gcd(128, 153)=1 \text{, Euler's theorem applies.} \\ & \equiv 128^{\color{#3D99F6}100 \bmod 96} \text{ (mod 153)} & \small \color{#3D99F6} \text{Euler's totient function }\phi(153)=96 \\ & \equiv 128^{\color{#3D99F6}4} \text{ (mod 153)} \\ & \equiv (153-25)^4 \text{ (mod 153)} \\ & \equiv 25^4 \text{ (mod 153)} \\ & \equiv 625^2 \text{ (mod 153)} \\ & \equiv (4\times 153 + 13)^2 \text{ (mod 153)} \\ & \equiv 13^2 \text{ (mod 153)} \\ & \equiv 169 \text{ (mod 153)} \\ & \equiv \boxed{16} \text{ (mod 153)} \end{aligned}$

Relevant wiki: Euler's Theorem

$\begin{aligned} 128^{100} \bmod{153} &= 128^{100 \ {\color{#3D99F6} \bmod{ \phi (153)}}} \bmod{153} & \small {\color{#3D99F6} \text{gcd } (128,153) =1 ,\text{ hence we can apply Euler's theorem}} \\ &= 128^{100 \ \bmod{96}} \bmod{153} & \small {\color{#3D99F6} \text{As } \phi (153) = 96 } \\ &= 128^4 \bmod{153} \\ &= 16384^2 \bmod{153} \\ &= {(16371-13)}^2 \bmod{153} & \small {\color{#3D99F6} 16371 \text{ is divisible by } 153} \\ &= 13^2 \bmod{153} \\ &= \boxed{16} \end{aligned}$