1
$\begingroup$

Can somebody give some help why this is correct?

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

3 Answers 3

10

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.

  • 0
    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.2011-08-05
3

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.

2

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.