# Help understanding modular congruence issue

Can somebody give some help why this is correct?

$28^{145} \equiv 2 \mod 13$

-

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:

$\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.

-
Can I just write (28)^144≡2 (mod 13) as (28)^144≡1 (mod 13) ? no? – Øyvind Aug 5 '11 at 18:47
I think I have to study some links given at the article at wikipedia, cause I don't see it as clearly :) – Øyvind Aug 5 '11 at 19:08
In your "Can I just write" you did not explicitly say how you get from $(28)^{144}\equiv 1 \pmod{13}$ to your answer. Admittedly, the missing last step is quite easy, but a fussy grader may decide your argument has a gap. – André Nicolas Aug 5 '11 at 21:39

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.

-

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.

-