Modulo Arithmetic/Examples/Residue of 2^512 Modulo 5

From ProofWiki
Jump to navigation Jump to search

Example of Modulo Arithmetic

The least positive residue of $2^{512} \pmod 5$ is $1$.


Proof

\(\ds 2^4\) \(\equiv\) \(\ds 1\) \(\ds \pmod 5\) as $2^4 = 16 = 3 \times 5 + 1$
\(\ds \leadsto \ \ \) \(\ds \paren {2^4}^{128}\) \(\equiv\) \(\ds 1^{128}\) \(\ds \pmod 5\) Congruence of Powers
\(\ds \leadsto \ \ \) \(\ds 2^{512}\) \(\equiv\) \(\ds 1\) \(\ds \pmod 5\)


Hence the result.

$\blacksquare$


Sources