How does mod multiplication work?

Question

For example, $10^{10} \equiv 4\pmod{6}$

If I used $\pmod{2}$ and $\pmod{3}$, how does the multiplication process work?

Since $10^{10} \equiv 0 \pmod{2}$ and $10^{10}\equiv 1\pmod{3}$, $$ 10^{10}\equiv (0,1) \pmod{(2,3)} $$ how do we get the value $4$ at the end? do we list out the possible values of $0\pmod{2}$ and $1\pmod{3}$? $$ 1\pmod{3} = 1, 4, 7, 10 $$ so on.

Since only $4, 10$ and so on satisfy $\pmod{2}$, only values that satisfy both criteria can be used.

In general, can we do this for $\pmod{n}$, $n$ being any integer?

Answer 1

Let me try to rephrase what you said.

Let $10^{10} \equiv a \pmod 6$, $a \in \{0, 1, 2, 3, 4, 5\}$.

As $10^{10} \equiv 0 \pmod 2$, we must have $a \equiv 0 \pmod 2$, so $a \in \{0, 2, 4\}$.

As $10^{10} \equiv 1 \pmod 3$, we must have $a \equiv 1 \pmod 3$, so $a \in \{1, 4\}$.

Therefore, $a = 4$.

This does give the correct answer as you've noticed. This works because $2, 3 \mid 6$ and $(2, 3) = 1$.

What you are doing is strongly related to the Chinese Remainder Theorem which states that if $n_1, \dots, n_k$ are pairwise coprime positive integers, then for any integers $a_1, \dots, a_k$, the system of congruences $x \equiv a_1 \pmod{n_1},\dots, x \equiv a_k\pmod{n_k}$ has a solution and it is unique modulo $n_1\dots n_k$. In particular, one way to find this solution is to use the method you used (as can be seen here).

Answer 2

For integer $n\ge0$ $$10^{n+1}-10=10(10^n-1)\equiv0\pmod{10\cdot9}$$ as $10^n-1$ is divisible by $10-1=9$

$$\implies 10^n\equiv10\pmod{90}\equiv10\pmod6$$

Answer 3

As $\displaystyle10\equiv1\pmod3, 10^n\equiv1\pmod3$ for integer $n\ge0$

As $\displaystyle a\equiv b\pmod m\implies a\cdot c\equiv b\cdot c\pmod{m\cdot c }$ where $a,b,m,c$ are integers

$\displaystyle10\cdot10^n\equiv10\pmod{3\cdot10}\equiv10\pmod6$ as $6|30$

Answer 4

This is called the "Chinese Remainder Theorem". You are given two congruent condition and you have to find the answer. I will show an example using slightly bigger numbers.

Suppose we are given $$ n \equiv 3 \mod 7, ~~\hbox{and}~~ n\equiv 5\mod 11$$

From the first we can write $$ n = 7 k + 3$$ Substituting in the second, we get $$ 7 k + 3\equiv5 \mod 11$$ or $$ 7 k \equiv2 \mod 11 \Rightarrow k \equiv (7^{-1}) 2 \mod 11$$ where the inverse is modulo $11$. One way to find $7^{-1} \mod 11$ is to use Euclid's algorithm. For small numbers it is easy to look at 7,14,21 etc. Actually since $21=-1 \mod 11$ we can stop and deduce that $$7 \cdot 3\equiv -1 \mod 11$$ or $$7 \, (-3) \equiv 1 \mod 11$$ If you prefer positive numbers, you can use $-3 \equiv 11-3 \mod 11$. Hence $$ 7^{-1} \equiv 8 \mod 11$$ Hence $$ k = 8 \cdot 2 = 16\equiv 5 \mod 11$$ Hence $k = 11 m + 5$ and finally $$ n =7 \, (11 m + 5) + 3 = 77 m + 38$$

You can easily extend this to any number of congruents.

Added in response to OP's request

We want $$n \equiv 0 \mod 2, ~~~ n \equiv 1 \mod 3$$

From second condition (OP already did it in the other order, so I want to provide a second method) $$ n = 3 k + 1$$ substituting in the first condition $$ 3 k + 1 = 0 \mod 2 \Rightarrow k + 1 = 0 \mod 2 ~~~\hbox{since $3 \equiv 1 \mod 2$}$$ So $k = -1 \mod 2$ or if you prefer positive numbers $$ k = -1 + 2 \mod 2 \Rightarrow k = 2 m + 1$$ Substituting in the formula for $n$ we have $$ n = 3 (2 m + 1) + 1 = 6m +4$$ So the possible values of $n$ are 4, 10, 16, 22, -2, -8, -14, -20 etc.

Answer 5

You have the idea for a modulus of 2 or 3.

There are lots of different methods for finding the solution for general $n$.

THE INDIRECT APPROACH

Suppose we take some number $a$, and we want $a^7 (\bmod \;n)$. Then we find the prime divisors of $n$. For example, if we want $a^7 (\bmod \;21)$, we find $a^7 (\bmod \;3)$ and $a^7 (\bmod \;7)$. Then we find which number is equivalent modulo 3 and 7.

In the case where the divisors repeat, for example, modulo $4=2^2$, we would need to find the value modulo 4. In this case, we can use the direct approach.

THE DIRECT APPROACH

There is a direct approach, where we can speed up calculations mod $n$. For example, suppose we take some number $a$, and we want $a^7 (\bmod \;n)$. The idea is that if instead of 7 we had 700 for the exponent, calculations can be done very quickly. So, We take seven and rewrite it as binary: 7 is 111 in binary, or 1*4 + 1*2 + 1*1. Then we take powers of seven. We start by calculating $a^1 (\bmod \; n)$. This gives us the modulated value of $a (\bmod \; n)$. Then we double this value and take the remainder, to get $a^2 (\bmod n)$. We double it again to get $a^4 (\bmod \; n)$, and so on. We keep doubling the value until we reach a high enough power. Then we simply multiply the previous results together. In other words, $a^7 = (a^4)(a^2)(a^1)$. So by multiplying the results together we arrive at the correct result:

$$a^7 (\bmod \; n) \equiv (a^4)(a^2)(a^1) (\bmod \; n)$$

Just to hammer the idea home, suppose we want to find $a^{13} (\bmod n)$. 13 in binary is $1*8 + 1*4 + 1*1$. So we know we want the powers 8, 4, and 1. So we take

$$a^{13} (\bmod \; n) \equiv (a^8)(a^4)(a^1) (\bmod \; n)$$

OTHER METHODS Other methods do exist, but the above two are probably the most basic.