Modular arithmetic/Intermediate

Given integers $a$ , $b$ , and $n$ , with $n > 0$ , we say that $a$ is congruent to $b$ modulo $n$ , or $a \equiv b$ (mod $n$ ), if the difference ${a - b}$ is divisible by $n$ .

For a given positive integer $n$ , the relation $a \equiv b$ (mod $n$ ) is an equivalence relation on the set of integers. This relation gives rise to an algebraic structure called the integers modulo $n$ (usually known as "the integers mod $n$ ," or $\mathbb{Z}_n$ for short). This structure gives us a useful tool for solving a wide range of number-theoretic problems, including finding solutions to Diophantine equations, testing whether certain large numbers are prime, and even some problems in cryptology.

Arithmetic Modulo n

Useful Facts

Consider four integers ${a},{b},{c},{d}$ and a positive integer ${m}$ such that $a\equiv b\pmod {m}$ and $c\equiv d\pmod {m}$ . In modular arithmetic, the following identities hold:

Addition: $a+c\equiv b+d\pmod {m}$ .
Subtraction: $a-c\equiv b-d\pmod {m}$ .
Multiplication: $ac\equiv bd\pmod {m}$ .
Division: $\frac{a}{e}\equiv \frac{b}{e}\pmod {\frac{m}{\gcd(m,e)}}$ , where $e$ is a positive integer that divides ${a}$ and $b$ .
Exponentiation: $a^e\equiv b^e\pmod {m}$ where $e$ is a positive integer.

For examples, see Introduction to modular arithmetic.

Miscellany

The binary operation "mod"

Related to the concept of congruence, mod $n$ is the binary operation $a$ mod $n$ , which is used often in computer programming.

Recall that, by the Division Algorithm, given any two integers $a$ and $n$ , with $n > 0$ , we can find integers $q$ and $r$ , with $0 \leq r < n$ , such that $a = nq + r$ . The number $q$ is called the quotient, and the number $r$ is called the remainder. The operation $a$ mod $n$ returns the value of the remainder $r$ . For example:

$15$ mod $6 = 3$ , since $15 = 6 \cdot 2 + 3$ .

$35$ mod $7 = 0$ , since $35 = 7 \cdot 5 + 0$ .

$-10$ mod $8 = 6$ , since $-10 = 8 \cdot -2 + 6$ .

Observe that if $a$ mod $n = r$ , then we also have $a \equiv r$ (mod $n$ ).

An example exercise with modular arithmetic:

Problem:

Let

$D=d_1d_2d_3d_4d_5d_6d_7d_8d_9$

be a nine-digit positive integer (each digit not necessarily distinct). Consider

$E=e_1e_2e_3e_4e_5e_6e_7e_8e_9$ ,

another nine-digit positive integer with the property that each digit ei when substituted for di makes the modified D divisible by 7. Let

$F=f_1f_2f_3f_4f_5f_6f_7f_8f_9$ be a third nine-digit positive integer with the same relation to E as E has to D.

Prove that every $di - fi$ is divisible by 7.

Solution:

Any positive integer $D=d_1d_2d_3d_4d_5d_6d_7d_8d_9$ can be expressed $(10^8)d_1+(10^7)d_2+...(10^0)d_9$ .

Since 10=3 mod 7, and since it holds that if a=b mod c then $a^n=b^n$ mod c, then D can be expressed much more simply mod 7; that is, $D= 2d1 +3d2 +1d3 -2d4 -3d5 -d6 +2d7 +3d8 +d9$ = x mod 7.

Each number in E must make the modified D equal 0 mod 7, so for each $d_i$ , $e_i = \frac{x+7k}{c}-d_i$ , where c is the coefficient of $d_i$ and k is an element of {-2,-1,0,1,2}. The patient reader should feel free to verify that this makes D = 0 mod 7.

In terms of $d_i$ terms, then, we find each $c_ie_i = x - c_id_i + 7k$ .

Then $E= 2e_1 +3e_2 +1e_3 -2e_4 -3e_5 -e_6 +2e_7 +3e_8 +e_9$ mod 7 can be expressed $E= (x-2d_1)+(x-3d_2)+(x-d_3)+...+(x-d_9) = (9x)-D$ mod 7 = (9x)- x = 8x = x mod 7. (note that the 7s, which do not change the mod value, have been eliminated).

Each number in F must make the modified E equal 0 mod 7, so for each $e_i$ , $f_i = \frac{x+7k_2}{c_i} -e_i = \frac{x+7k_2}{c_i} - (\frac{x+7k_1}{c_i} -d_i)$ .

By design and selection of k, all $(f_i)$ are integers, and $d_i - f_i$ is always an integer because it is the difference of two integers.

$d_i - f_i = \frac{7k_2-7k_1}{c_i}$

$c_i$ is a member of the set {1, 2, 3}. Since no $c_i$ divides 7, 7 may be factored and $7\frac{k_2-k_1}{c_i} = d_i - f_i$ is the product of two integers.

Let $A=\frac{k_2-k_1}{c_i}$ then $d_i - f_i =$ 7A mod 7 = 0 mod 7 for all $(d_i,f_i)$ , QED.

Page

Toolbox

Search

Modular arithmetic/Intermediate

Contents

Arithmetic Modulo n

Useful Facts

Miscellany

The binary operation "mod"