Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can somebody give some help why this is correct?

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

share|improve this question
    
What have you tried? –  lhf Aug 5 '11 at 17:21
add comment

3 Answers

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.