Help understanding modular congruence issue Can somebody give some help why this is correct?
$28^{145} \equiv 2 \mod 13$
 A: Use Fermat's Little Theorem to see : $$(28)^{12} \equiv 1 \ \bigl(\text{mod} \ 13 \bigr)$$ $$ \Longrightarrow (28)^{144} \equiv 1 \ \bigl(\text{mod} \ 13 \bigr)$$
Take a look here as well:


*

*http://en.wikipedia.org/wiki/Modular_arithmetic#Congruence_relation
$\textbf{Added.}$ The finishing step would be: Since $28 \equiv 2 \ \bigl(\text{mod} \ 13\bigr)$ and $(28)^{144} \equiv 1 \bigl(\text{mod}\ 13\bigr)$ and now multiply both of these to get your answer.
A: Notice that, $\:$ mod $13:\ \ 2^{145}\equiv 2\ \iff 2^{144}\equiv 1\:$ follows by scaling the equation by $\rm\ 2^{-1}\equiv 7\:.$
Hence it suffices to find a factor $\rm\:n\:$ of $\rm\:144= n\:k\:$ such that $\rm\:2^{\:n}\equiv 1\pmod{13}\ $ since this implies $\rm\:2^{144}\equiv (2^n)^k\equiv 1^k\equiv 1\pmod{13}\:.\:$ If you are aware of Fermat's Little Theorem, then it implies that $\rm\:n = 12\:$ works. Otherwise, note that the powers of $\:2\:$ are $\rm\ 2,\:4,-5,\:3,\:6,-1,\ \ldots\pmod{13}\:.\ $ So $\rm\:2^6\equiv -1\ \Rightarrow\ 2^{12}\equiv (-1)^2\equiv 1\pmod{13}\:.\:$ Since $\rm\:n = 12\:$  divides $144\:,\:$ the proof is complete.
A: Well, $28 \equiv 2$, and you could do modular exponentiation (which is super short, because $2^4 > 13$, and so it loops really quickly).
Alternatively, you could just literally do $2^{145}$ and find the remainder upon division by 13 (I think it's something like a 43 digit number or so).
Fermat's Little Theorem will guarantee that $28^{12} \equiv 1$, which also shortens calculations very quickly.
