Any shortcut for congruence modulo arithmetic.

Question

I am doing simple question on congruence modulo arithmetic, and wondered if there is a shortcut for computing the same for below:

$9322 + 8321 \equiv ... \pmod{95}$

Answer 1

Reduce first: $$9322 = 9500-178=9500-190+12 \equiv 12 \pmod{95}$$ $$8321 = 9500 - 1179 = 9500-950-229 = 9500-950-190-39 \equiv -39 \pmod{95}$$ Therefore $$9322+8321 \equiv 12-39 = -27 \equiv 95-27 = 68 \pmod{95}.$$

Alternate method for the above problem (also added in edit) Note that $1000\equiv 50 \pmod{95}$, and $100\equiv 5 \pmod{95}$, so $$9322+8321= (9+8)1000+(3+3)100+22+21 \equiv 17\cdot 50 + 6\cdot 5 + 43 \equiv 50 + 8\cdot 100 + 73 \equiv 50+40+73 \equiv 95-5 + 73 \equiv 68.$$

Edit: Based on your comments on the other answer, it seems like your question is more along the lines of: What are useful tricks for reducing large numbers to a number between $0$ and $n-1$ mod $n$ quickly?

In that case: I've demonstrated a general technique above, where you look at nice "round" multiples of your modulus, and repeatedly add/subtract them to reduce.

Relatedly, if you want to simplify a number $A$ mod $n$, and its easier to simplify modulo a multiple of $n$, $kn$, you can first simplify mod $kn$, then simplify the smaller number mod $n$. I'll demonstrate this below.

There are also several special techniques for certain numbers that take advantage of the fact that we express our numbers in base 10.

If $A=\sum_{i=0}^m a_i 10^i$ is the base 10 expression of a number (i.e. $a_i$ is the digit in the $10^i$s place), then there are a few nice moduluses (moduli?), $n$.

Case 1: $n=10^{m_0}$

In this case reduction mod $n$ is truncatation to $m_0$ digits, since for $i\ge m_0$, $a_i10^i$ is divisible by $n$. Therefore $$A\equiv \sum_{i=0}^{m_0-1} a_i10^i \pmod{10^{m_0}}.$$ As an example, $13434758 \equiv 758\pmod{10^3}$.

Case 2: $n=9$

In this case, $10\equiv 1$, so $$A= \sum_{i=0}^{m}a_i10^i \equiv \sum_{i=0}^m a_i \pmod{9},$$ i.e. $A$ is equivalent to the sum of its digits mod 9. This allows quick reductions, e.g. $13434758 \equiv 1+3+4+3+4+7+5+8 = 35 \equiv 3+5=8 \pmod{9}$.

Case 3: $n=11$

In this case, $10 \equiv -1$, so $$A= \sum_{i=0}^{m}a_i10^i \equiv \sum_{i=0}^m a_i(-1)^i \pmod{11},$$ i.e. $A$ is equivalent to the alternating sum of its digits mod 9. This also allows quick reductions, e.g. $13434758 \equiv -1+3-4+3-4+7-5+8 = 7 \pmod{11}$.

Example for $n=2^{10}=1024$ using case 1.

Suppose we want to reduce 1345922378472845723948573434758 mod 1024. Since $2^{10}\mid 10^{10}$, we can first truncate the number until we're left with 10 digits to get $$1345922378472845723948573434758\equiv 8573434758 \pmod{1024},$$ then at that point, one could use long division or something to figure out the exact result. The point is you can save yourself a lot of work by first truncating using the fact that $2^{10}\mid 10^{10}$.

Answer 2

You can perform the division algorithm on $9322+8321=17643$ to get $17643=185\cdot 95+68$. Therefore $68$ is your final answer.

Answer 3

You could use the fact that $100 \equiv 5 \pmod{95}.$ Therefore $10000 = 100^2 \equiv 5^2 \equiv 25 \pmod{95},$ and \begin{align} 9322 + 8321 &= 17643 \\ &= 10000 + 76 \times 100 + 43 \\ &\equiv 25 + 76 \times 5 + 43 \pmod{95} \\ &= 448 \\ &= 4 \times 100 + 48 \\ &\equiv 4 \times 5 + 48 \pmod{95} \\ &= 68. \end{align}