Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can somebody give some help why this is correct?

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

share|cite|improve this question

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.

share|cite|improve this 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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.