Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

3.3 Congruences

One of the most basic and useful notions in number theory is modular arithmetic, or congruences.

Definition

Let $a, b, n$ $a, b, n$ be integers with $n \neq 0 .$ $n \neq 0 .$ We say that

\begin{matrix} a \equiv b & (\mod n) \end{matrix}

$\begin{matrix} a \equiv b & (\mod n) \end{matrix}$

(read: $a$ $a$ is congruent to $b$ $b$ mod $n$ $n$ ) if $a - b$ $a - b$ is a multiple (positive or negative or zero) of $n .$ $n .$

Another formulation is that $a \equiv b (\mod n)$ $a \equiv b (\mod n)$ if $a$ $a$ and $b$ $b$ differ by a multiple of $n .$ $n .$ This can be rewritten as $a = b + n k$ $a = b + n k$ for some integer $k$ $k$ (positive or negative).

Example

\begin{matrix} \begin{matrix} 32 \equiv 7 & (\mod 5), \end{matrix} & \begin{matrix} - 12 \equiv 37 & (\mod 7), \end{matrix} & \begin{matrix} 17 \equiv 17 & (\mod 13) . \end{matrix} \end{matrix}

$\begin{matrix} \begin{matrix} 32 \equiv 7 & (\mod 5), \end{matrix} & \begin{matrix} - 12 \equiv 37 & (\mod 7), \end{matrix} & \begin{matrix} 17 \equiv 17 & (\mod 13) . \end{matrix} \end{matrix}$

Note: Many computer programs regard $17 (mod 10)$ $17 (mod 10)$ as equal to the number 7, namely, the remainder obtained when 17 is divided by 10 (often written as $17 % 10 = 7$ $17 % 10 = 7$ ). The notion of congruence we use is closely related. We have that two numbers are congruent mod $n$ $n$ if they yield the same remainders when divided by $n .$ $n .$ For example, $17 \equiv 37 (mod 10)$ $17 \equiv 37 (mod 10)$ because $17 % 10$ $17 % 10$ and $37 % 10$ $37 % 10$ are equal.

Congruence behaves very much like equality. In fact, the notation for congruence was intentionally chosen to resemble the notation for equality.

Proposition

Let $a, b, c, n$ $a, b, c, n$ be integers with $n \neq 0 .$ $n \neq 0 .$

$a \equiv 0 (mod n)$ $a \equiv 0 (mod n)$ if and only if $n | a .$ $n | a .$
$a \equiv a (mod n) .$ $a \equiv a (mod n) .$
$a \equiv b (mod n)$ $a \equiv b (mod n)$ if and only if $b \equiv a (mod n) .$ $b \equiv a (mod n) .$
If $a \equiv b$ $a \equiv b$ and $b \equiv c (mod n),$ $b \equiv c (mod n),$ then $a \equiv c (mod n) .$ $a \equiv c (mod n) .$

Proof. In (1), $a \equiv 0 (mod n)$ $a \equiv 0 (mod n)$ means that $a = a - 0$ $a = a - 0$ is a multiple of $n,$ $n,$ which is the same as $n | a .$ $n | a .$ In (2), we have $a - a = 0 \cdot n,$ $a - a = 0 \cdot n,$ so $a \equiv a (mod n) .$ $a \equiv a (mod n) .$ In (3), if $a \equiv b (mod n),$ $a \equiv b (mod n),$ write $a - b = n k .$ $a - b = n k .$ Then $b - a = n (- k),$ $b - a = n (- k),$ so $b \equiv a (mod n) .$ $b \equiv a (mod n) .$ Reversing the roles of $a$ $a$ and $b$ $b$ gives the reverse implication. For (4), write $a = b + n k$ $a = b + n k$ and $b = c + n ℓ .$ $b = c + n ℓ .$ Then $a - c = n (k + ℓ),$ $a - c = n (k + ℓ),$ so $a \equiv c (mod n) .$ $a \equiv c (mod n) .$

Usually, we have $n > 0$ $n > 0$ and we work with the integers mod $n,$ $n,$ denoted $Z_{n} .$ $Z_{n} .$ These may be regarded as the set ${0, 1, 2, \dots, n - 1},$ ${0, 1, 2, \dots, n - 1},$ with addition, subtraction, and multiplication mod $n .$ $n .$ If $a$ $a$ is any integer, we may divide $a$ $a$ by $n$ $n$ and obtain a remainder in this set:

a = n q + r with 0 \leq r < n .

$a = n q + r with 0 \leq r < n .$

(This is just division with remainder; $q$ $q$ is the quotient and $r$ $r$ is the remainder.) Then $a \equiv r (mod n),$ $a \equiv r (mod n),$ so every number $a$ $a$ is congruent mod $n$ $n$ to some integer $r$ $r$ with $0 \leq r < n .$ $0 \leq r < n .$

Proposition

Let $a, b, c, d, n$ $a, b, c, d, n$ be integers with $n \neq 0,$ $n \neq 0,$ and suppose $a \equiv b (mod n)$ $a \equiv b (mod n)$ and $c \equiv d (mod n) .$ $c \equiv d (mod n) .$ Then

a + c \equiv b + d, a - c \equiv b - d, a c \equiv b d (mod n) .

$a + c \equiv b + d, a - c \equiv b - d, a c \equiv b d (mod n) .$

Proof. Write $a = b + n k$ $a = b + n k$ and $c = d + n ℓ,$ $c = d + n ℓ,$ for integers $k$ $k$ and $ℓ .$ $ℓ .$ Then $a + c = b + d + n (k + ℓ),$ $a + c = b + d + n (k + ℓ),$ so $a + c \equiv b + d (mod n) .$ $a + c \equiv b + d (mod n) .$ The proof that $a - c \equiv b - d$ $a - c \equiv b - d$ is similar. For multiplication, we have $a c = b d + n (d k + b ℓ + n k ℓ),$ $a c = b d + n (d k + b ℓ + n k ℓ),$ so $a c \equiv b d .$ $a c \equiv b d .$

The proposition says you can perform the usual arithmetic operations of addition, subtraction, and multiplication with congruences. You must be careful, however, when trying to perform division, as we’ll see.

If we take two numbers and want to multiply them modulo $n,$ $n,$ we start by multiplying them as integers. If the product is less than $n,$ $n,$ we stop. If the product is larger than $n - 1,$ $n - 1,$ we divide by $n$ $n$ and take the remainder. Addition and subtraction are done similarly. For example, the integers modulo $6$ $6$ have the following addition table:

A table shows 6 rows and 6 columns for addition mod 6.

3.3-1 Full Alternative Text

A table for multiplication mod 6 is

A table shows 6 rows and 6 columns for multiplication mod 6.

3.3-2 Full Alternative Text

Example

Here is an example of how we can do algebra mod $n .$ $n .$ Consider the following problem: Solve $x + 7 \equiv 3 (mod 17) .$ $x + 7 \equiv 3 (mod 17) .$

SOLUTION

x \equiv 3 - 7 \equiv - 4 \equiv 13 (mod 17) .

$x \equiv 3 - 7 \equiv - 4 \equiv 13 (mod 17) .$

There is nothing wrong with negative answers, but usually we write the final answer as an integer from 0 to $n - 1$ $n - 1$ when we are working mod $n .$ $n .$

3.3.1 Division

Division is much trickier mod $n$ $n$ than it is with rational numbers. The general rule is that you can divide by $a (mod n)$ $a (mod n)$ when $gcd (a, n) = 1 .$ $gcd (a, n) = 1 .$

Proposition

Let $a, b, c, n$ $a, b, c, n$ be integers with $n \neq 0$ $n \neq 0$ and with $gcd (a, n) = 1 .$ $gcd (a, n) = 1 .$ If $a b \equiv a c (mod n),$ $a b \equiv a c (mod n),$ then $b \equiv c (mod n) .$ $b \equiv c (mod n) .$ In other words, if $a$ $a$ and $n$ $n$ are relatively prime, we can divide both sides of the congruence by $a .$ $a .$

Proof Since $gcd (a, n) = 1,$ $gcd (a, n) = 1,$ there exist integers $x, y$ $x, y$ such that $a x + n y = 1 .$ $a x + n y = 1 .$ Multiply by $b - c$ $b - c$ to obtain

(a b - a c) x + n (b - c) y = b - c .

$(a b - a c) x + n (b - c) y = b - c .$

Since $a b - a c$ $a b - a c$ is a multiple of $n,$ $n,$ by assumption, and $n (b - c) y$ $n (b - c) y$ is also a multiple of $n,$ $n,$ we find that $b - c$ $b - c$ is a multiple of $n .$ $n .$ This means that $b \equiv c (mod n) .$ $b \equiv c (mod n) .$

Example

Solve: $2 x + 7 \equiv 3 (mod 17) .$ $2 x + 7 \equiv 3 (mod 17) .$

SOLUTION

$2 x \equiv 3 - 7 \equiv - 4, so x \equiv - 2 \equiv 15 (mod 17) .$ $2 x \equiv 3 - 7 \equiv - 4, so x \equiv - 2 \equiv 15 (mod 17) .$ The division by 2 is allowed since $gcd (2, 17) = 1 .$ $gcd (2, 17) = 1 .$

Example

Solve: $5 x + 6 \equiv 13 (mod 11) .$ $5 x + 6 \equiv 13 (mod 11) .$

SOLUTION

$5 x \equiv 7 (mod 11) .$ $5 x \equiv 7 (mod 11) .$ Now what do we do? We want to divide by 5, but what does 7/5 mean mod 11? Note that $7 \equiv 18 \equiv 29 \equiv 40 \equiv \dots (mod 11) .$ $7 \equiv 18 \equiv 29 \equiv 40 \equiv \dots (mod 11) .$ So $5 x \equiv 7$ $5 x \equiv 7$ is the same as $5 x \equiv 40 .$ $5 x \equiv 40 .$ Now we can divide by 5 and obtain $x \equiv 8 (mod 11)$ $x \equiv 8 (mod 11)$ as the answer. Note that $7 \equiv 8 \cdot 5 (mod 11),$ $7 \equiv 8 \cdot 5 (mod 11),$ so 8 acts like 7/5.

The last example can be done another way. Since $5 \cdot 9 \equiv 1 (mod 11),$ $5 \cdot 9 \equiv 1 (mod 11),$ we see that 9 is the multiplicative inverse of $5 (mod 11) .$ $5 (mod 11) .$ Therefore, dividing by 5 can be accomplished by multiplying by 9. If we want to solve $5 x \equiv 7 (mod 11),$ $5 x \equiv 7 (mod 11),$ we multiply both sides by 9 and obtain

x \equiv 45 x \equiv 63 \equiv 8 (mod 11) .

$x \equiv 45 x \equiv 63 \equiv 8 (mod 11) .$

Proposition

Suppose $gcd (a, n) = 1 .$ $gcd (a, n) = 1 .$ Let $s$ $s$ and $t$ $t$ be integers such that $a s + n t = 1$ $a s + n t = 1$ (they can be found using the extended Euclidean algorithm). Then $a s \equiv 1 (mod n),$ $a s \equiv 1 (mod n),$ so $s$ $s$ is the multiplicative inverse for $a (mod n) .$ $a (mod n) .$

Proof. Since $a s - 1 = - n t,$ $a s - 1 = - n t,$ we see that $a s - 1$ $a s - 1$ is a multiple of $n .$ $n .$

Notation: We let $a^{- 1}$ $a^{- 1}$ denote this $s,$ $s,$ so $a^{- 1}$ $a^{- 1}$ satisfies $a^{- 1} a \equiv 1 (mod n) .$ $a^{- 1} a \equiv 1 (mod n) .$

The extended Euclidean algorithm is fairly efficient for computing the multiplicative inverse of $a$ $a$ by the method stated in the proposition.

Example

Solve $11111 x \equiv 4 (mod 12345) .$ $11111 x \equiv 4 (mod 12345) .$

SOLUTION

In Section 3.2, from the calculation of $gcd (12345, 11111)$ $gcd (12345, 11111)$ we obtained

1 = 12345 \cdot (- 2224) + 11111 \cdot 2471.

$1 = 12345 \cdot (- 2224) + 11111 \cdot 2471.$

This says that

\begin{matrix} 11111 \cdot 2471 \equiv 1 & (mod 12345) . \end{matrix}

$\begin{matrix} 11111 \cdot 2471 \equiv 1 & (mod 12345) . \end{matrix}$

Multiplying both sides of the original congruence by 2471 yields

\begin{matrix} x \equiv 9884 & (mod 12345) . \end{matrix}

$\begin{matrix} x \equiv 9884 & (mod 12345) . \end{matrix}$

In practice, this means that if we are working mod 12345 and we encounter the fraction 4/11111, we can replace it with 9884. This might seem a little strange, but think about what 4/11111 means. It’s simply a symbol to represent a quantity that, when multiplied by 11111, yields 4. When we are working mod 12345, the number 9884 also has this property since $11111 \times 9884 \equiv 4 (mod 12345) .$ $11111 \times 9884 \equiv 4 (mod 12345) .$

Let’s summarize some of the discussion:

Finding

a^{- 1} (mod n)

$a^{- 1} (mod n)$

Use the extended Euclidean algorithm to find integers $s$ $s$ and $t$ $t$ such that $a s + n t = 1 .$ $a s + n t = 1 .$
$a^{- 1} \equiv s (mod n) .$ $a^{- 1} \equiv s (mod n) .$

Solving

$a x \equiv c (mod n)$ $a x \equiv c (mod n)$ when $gcd (a, n) = 1$ $gcd (a, n) = 1$

(Equivalently, you could be working mod $n$ $n$ and encounter a fraction $c / a$ $c / a$ with $gcd (a, n) = 1 .$ $gcd (a, n) = 1 .$ )

Use the extended Euclidean algorithm to find integers $s$ $s$ and $t$ $t$ such that $a s + n t = 1 .$ $a s + n t = 1 .$
The solution is $x \equiv c s (mod n)$ $x \equiv c s (mod n)$ (equivalently, replace the fraction $c / a$ $c / a$ with $c s (mod n)$ $c s (mod n)$ ).

What if

\gcd (a, n) > 1 ?

$\gcd (a, n) > 1 ?$

Occasionally we will need to solve congruences of the form $a x \equiv b (mod n)$ $a x \equiv b (mod n)$ when $\gcd (a, n) = d > 1.$ $\gcd (a, n) = d > 1.$ The procedure is as follows:

If $d$ $d$ does not divide $b,$ $b,$ there is no solution.
Assume $d | b .$ $d | b .$ Consider the new congruence

$\begin{matrix} (a / d) x \equiv b / d & (mod n / d) . \end{matrix}$ $\begin{matrix} (a / d) x \equiv b / d & (mod n / d) . \end{matrix}$

Note that $a / d, b / d, n / d$ $a / d, b / d, n / d$ are integers and $gcd (a / d, n / d) = 1 .$ $gcd (a / d, n / d) = 1 .$ Solve this congruence by the above procedure to obtain a solution $x_{0} .$ $x_{0} .$
The solutions of the original congruence $a x \equiv b (mod n)$ $a x \equiv b (mod n)$ are

$x_{0}, x_{0} + (n / d), x_{0} + 2 (n / d), \dots, x_{0} + (d - 1) (n / d) (mod n) .$ $x_{0}, x_{0} + (n / d), x_{0} + 2 (n / d), \dots, x_{0} + (d - 1) (n / d) (mod n) .$

Example

Solve $12 x \equiv 21 (mod 39) .$ $12 x \equiv 21 (mod 39) .$

SOLUTION

$gcd (12, 39) = 3,$ $gcd (12, 39) = 3,$ which divides 21. Divide by 3 to obtain the new congruence $4 x \equiv 7 (mod 13) .$ $4 x \equiv 7 (mod 13) .$ A solution $x_{0} = 5$ $x_{0} = 5$ can be obtained by trying a few numbers, or by using the extended Euclidean algorithm. The solutions to the original congruence are $x \equiv 5, 18, 31 (mod 39) .$ $x \equiv 5, 18, 31 (mod 39) .$

The preceding congruences contained $x$ $x$ to the first power. However, nonlinear congruences are also useful. In several places in this book, we will meet equations of the form

\begin{matrix} x^{2} \equiv a & (mod n) . \end{matrix}

$\begin{matrix} x^{2} \equiv a & (mod n) . \end{matrix}$

First, consider $x^{2} \equiv 1 (mod 7) .$ $x^{2} \equiv 1 (mod 7) .$ The solutions are $x \equiv 1, 6 (mod 7),$ $x \equiv 1, 6 (mod 7),$ as we can see by trying the values $0, 1, 2, \dots, 6$ $0, 1, 2, \dots, 6$ for $x .$ $x .$ In general, when $p$ $p$ is an odd prime, $x^{2} \equiv 1 (mod p)$ $x^{2} \equiv 1 (mod p)$ has exactly the two solutions $x \equiv \pm 1 (mod p)$ $x \equiv \pm 1 (mod p)$ (see Exercise 15).

Now consider $x^{2} \equiv 1 (mod 15) .$ $x^{2} \equiv 1 (mod 15) .$ If we try the numbers $0, 1, 2, \dots, 14$ $0, 1, 2, \dots, 14$ for $x,$ $x,$ we find that $x = 1, 4, 11, 14$ $x = 1, 4, 11, 14$ are solutions. For example, $11^{2} \equiv 121 \equiv 1 (mod 15) .$ $11^{2} \equiv 121 \equiv 1 (mod 15) .$ Therefore, a quadratic congruence for a composite modulus can have more than two solutions, in contrast to the fact that a quadratic equation with real numbers, for example, can have at most two solutions. In Section 3.4, we’ll discuss this phenomenon. In Chapters 9 (factoring), 18 (flipping coins), and 19 (identification schemes), we’ll meet applications of this fact.

3.3.2 Working with Fractions

In many situations, it will be convenient to work with fractions mod $n .$ $n .$ For example, $1 / 2 (mod 12345)$ $1 / 2 (mod 12345)$ is easier to write than $6173 (mod 12345)$ $6173 (mod 12345)$ (note that $2 \times 6173 \equiv 1 (mod 12345)$ $2 \times 6173 \equiv 1 (mod 12345)$ ). The general rule is that a fraction $b / a$ $b / a$ can be used mod $n$ $n$ if $gcd (a, n) = 1 .$ $gcd (a, n) = 1 .$ Of course, it should be remembered that $b / a (mod n)$ $b / a (mod n)$ really means $a^{- 1} b (mod n),$ $a^{- 1} b (mod n),$ where $a^{- 1}$ $a^{- 1}$ denotes the integer mod $n$ $n$ that satisfies $a^{- 1} a \equiv 1 (mod n) .$ $a^{- 1} a \equiv 1 (mod n) .$ But nothing will go wrong if it is treated as a fraction.

Another way to look at this is the following. The symbol “1/2” is simply a symbol with exactly one property: If you multiply 1/2 by 2, you get 1. In all calculations involving the symbol 1/2, this is the only property that is used. When we are working mod 12345, the number 6173 also has this property, since $6173 \times 2 \equiv 1 (mod 12345) .$ $6173 \times 2 \equiv 1 (mod 12345) .$ Therefore, $1 / 2 (mod 12345)$ $1 / 2 (mod 12345)$ and $6173 (mod 12345)$ $6173 (mod 12345)$ may be used interchangeably.

Why can’t we use fractions with arbitrary denominators? Of course, we cannot use $1 / 6 (mod 6),$ $1 / 6 (mod 6),$ since that would mean dividing by $0 (mod 6) .$ $0 (mod 6) .$ But even if we try to work with $1 / 2 (mod 6),$ $1 / 2 (mod 6),$ we run into trouble. For example, $2 \equiv 8 (mod 6),$ $2 \equiv 8 (mod 6),$ but we cannot multiply both sides by 1/2, since $1 \equiv 4 (mod 6) .$ $1 \equiv 4 (mod 6) .$ The problem is that $gcd (2, 6) = 2 \neq 1 .$ $gcd (2, 6) = 2 \neq 1 .$ Since 2 is a factor of 6, we can think of dividing by 2 as “partially dividing by 0.” In any case, it is not allowed.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3.3 Congruences

Create new playlist

Sign In

Sign Up

Table of Contents for
3.3 Congruences