# Compute $23275763^{301} \pmod 6$ without using a calculator

I am trying to solve $23275763^{301} \pmod 6$ without using a calculator. The only thing my professor said regarding calculating mod for a large number is that we only care about the last $2$ digits (in this case $63^{301} \pmod 6$, and this often works but doesn't work for this problem (I am unsure why).

How would I go about solving this without a calculator?

Note: This is our first class talking about basic modulo math. The professor hasn't showed us any theorems or techniques to solve these, so I'm meant to use the most basic methods.

• You can't always use the last two digits when working modulo 6. If you were doing things modulo 100 then you do want the last two. – Sean Roberson Nov 3 '16 at 11:05
• @Sean Robertson Thanks for your response. Some other examples where it has worked are 93398 mod 10, 43726 mod 10, 315263 + 11611028782 (mod 5), and (21523)(11861132) (mod 3), but I don't recognize a pattern for when I can use this reliably. – user1861051 Nov 3 '16 at 14:38
• @user1861051 It works when there exists $k>0$ such that $10^k$ is divisible by your modulus; in this case you can consider only the last $k$ digits to get the answer. Thus your first three examples work. Your last example should not work, if it did then it was just a coincidence. – Ian Nov 3 '16 at 17:29
• @Ian This makes perfect sense. Thank you for the explanation. – user1861051 Nov 3 '16 at 18:29

## 1 Answer

Hint: $23275763\equiv-1\pmod6$. Why? Because $23275764$ is divisible by 6: it is even and divisible by 3 (by the test for divisibility by 3).

• Remark: this required you to manipulate all of the digits. – Ian Nov 3 '16 at 10:40
• Thank you. I'll have to memorize divisibility rules as this seems like a good technique. – user1861051 Nov 3 '16 at 18:30
• @user1861051 Several of the common divisibility rules are easy to rederive on the fly using the algebraic rules for modular arithmetic. For example, "x is divisible by 3 if and only if the sum of its decimal digits is divisible by 3" is equivalent to "$10^k \equiv 1 \mod 3$" for $k=0,1,2,\dots$". – Ian Nov 4 '16 at 13:17