Number theory

Number theory is a branch of mathematics that studies the properties of the integers.

In number theory, variables are restricted to represent integers only. For example, this equation:

{ab = 12}

has an infinite number of solutions if {a} and {b} are allowed to represent any two real numbers. But if they’re restricted to representing positive integers only, then it has only three solutions (ignoring different orderings):

\begin{array}{ll} 1 \times 12 &\hspace-5pt = 12 \cr 2 \times 6 &\hspace-5pt = 12 \cr 3 \times 4 &\hspace-5pt = 12 \cr \end{array}

In this chapter, when we talk about a number, we’ll always assume that it’s an integer.

Index

Divisibility

We define divisibility as follows:

If this equation:

[[ {{a} \over {b}} = c ]]

has a solution for integers {a,} {b,} and {c,} then we say that:

{a} is divisible by {b}

or

{b} divides {a}

We notate “{b} divides {a}” as:

{b|a}

The variable {b} is not allowed to be {0,} but {a} and {c} can be {0.}

Notice that {b|0} is always true for every allowable value of {b,} because [[ {{0} \over {b}} = 0. ]]

Likewise, {0} is considered to be a multiple of every integer, because {0b = 0} for all integers {b.}

In talking about the divisibility of numbers, we always assume they’re integers. (If the variables are allowed to represent real numbers or rational numbers, then every number would be “divisible” by every other number except {0,} making the concept of “divisibility” trivial.)

Tests for divisibility

In this section, we list some quick tests for divisibility. Here, we assume that the number {n} is written in base {10}:

{2|n}	—	the last digit is even: {0,} {2,} {4,} {6,} or {8}
{3|n}	—	the sum of all the digits is divisible by {3}
{4|n}	—	the number formed by the last two digits is divisible by {4}
{5|n}	—	the last digit is {0} or {5}
{6|n}	—	the sum of all the digits is divisible by {3} and the last digit is even
{8|n}	—	the number formed by the last three digits is divisible by {8}
{9|n}	—	the sum of all the digits is divisible by {9}
{10|n}	—	the last digit is {0}
{12|n}	—	the number formed by the last two digits is divisible by {4,} and the sum of all the digits is divisible by {3}

When you test for divisibility by summing the digits of a number, you’re allowed to repeat the summing process iteratively until you get a single digit result.

For example, if you sum the digits of {9578,} you get {29.} You can then sum the digits of {29} to get {11,} and finally, you can sum the digits of {11} to get {2.}

If you repeat this process until you get a single digit, the result is called the digital root. The digital root of {0} is {0,} and the digital root of all other integers is between {1} and {9.}

Let’s prove the divisibility test for {9|n.} Here, we assume that {n} has the three digits {a,} {b,} and {c,} and that the sum of those three digits is a multiple of {9}:

{n}	{\ = 100a + 10b + c}		(given)
{9k}	{\ = a + b + c}		(given, for some integer {k})
{n - 9k}	{\ = 99a + 9b}		(subtract the second equation from the first)
{n}	{\ = 99a + 9b + 9k}		(add {9k} to both sides)
{n}	{\ = 9(11a + b + k)}		(factor {9} out from the right side)

The last equation shows that {n} equals {9} times some integer, therefore, {9|n.}

When applying test for divisibility, it’s helpful to remember these rules:

If {a|b} and {a|c} then {a|(b+c)}

If {a|b} and {a|c} then {a|(b-c)}

If {a|b} and {a|c} then {a|(bc)}

If {a|b} then {a|(nb)} for all integers {n}

For example, {15|645} because it’s easy to see that {15|600} and {15|45,} therefore {15|(600+45).}

Parity

Parity applies only to integers. If a number is not an integer, it cannot be classified as either even or odd.

Notice the following:

• An even integer can always be written as {2k} for some integer {k.}
• An odd integer can always be written as {2k + 1} for some integer {k.}

Here are the parity rules for addition, subtraction, and multiplication:

Rule						Example
even		{\pm } even		{=} even		{0 + 0 = 0}
even		{\pm } odd		{=} odd		{0 + 1 = 1}
odd		{\pm } odd		{=} even		{1 + 1 = 2}
even		{\times} even		{=} even		{0 \times 0 = 0}
even		{\times} odd		{=} even		{0 \times 1 = 0}
odd		{\times} odd		{=} odd		{1 \times 1 = 1}

To remember these rules, simply use {0} and {1} as the representatives of even and odd, respectively:

Exercises (part 1)

1. Is the number {n = 11{,}088} divisible by {12} ? Answer
   • The sum of the digits is {18,} which is divisible by {3,} so {3|n.}
   • The last two digits are a multiple of {4,} so {4|n.}
   • Both {3|n} and {4|n} are true, so {12|n.}

2. Is it true that the product of any {3} consecutive integers (such as {14 \mathord{\times} 15 \mathord{\times} 16}) is always a multiple of {6}? If so, explain why. If not, find a counterexample. Answer
   • Suppose the numbers are {n,} {n \mathord{+} 1,} and {n \mathord{+} 2.}
   • Every {2}nd number is even, so either {n} and {n \mathord{+} 2} are even, or {n \mathord{+} 1} is even.
   • Every {3}rd number is a multiple of {3}, so either {n,} {n \mathord{+} 1,} or {n \mathord{+} 2} must be.
   • From above, the product {n(n \mathord{+} 1)(n \mathord{+} 2)} contains both {2} and {3} as factors.
   • Therefore, the product contains {2 \mathord{\times} 3 = 6} as a factor.

3. If an even number is divided by an odd number, is it possible for the result to be an odd integer? If so, find an example. If not, explain why. Answer
   • We’re solving the equation: [[ {{\text{even}} \over {\text{odd}}_{\large{1}}} = \text{odd}_{\large{2}} ]]
   • If we multiply both sides by {\text{odd}_{\large{1}}}, we get: {\ {\text{even} = \text{odd}_{\large{1}}\times \text{odd}_{\large{2}}}}
   • The resulting equation violates the parity rule for mulitplication, because { \text{odd} \times \text{odd} = \text{odd}. }
   • Therefore, the division has no solution.

4. If {n} is an integer, is it possible for {n^{\large 2} + 3n + 1} to be even?
   If so, find one such value of {n.} If not, explain why. Answer
   • We know that {n^{\large 2}} has the same parity as {n.}
   • We know that {3n} has the same parity as {n.}
   • The first two terms in the expression have the same parity, so they have an even sum.
   • Adding {1} to that even sum makes the final result odd.
   • Therefore, the expression is odd for all values of {n.}

5. Is the sum of all the odd numbers between {0} and {50} even or odd? Answer
   • We’re summing all the odd numbers between {1} and {49,} inclusive.
   • The {n}th positive odd number is {2n-1.}
   • If we solve {2n-1 = 49} for {n,} we find that the {25}th odd number is {49.}
   • Therefore, we are adding {25} odd numbers together.
   • The sum of {3} odd numbers is odd, the sum of {5} odd numbers is odd, etc.
   • So, in general, the sum of an odd number of odd numbers is odd.
   • And, specifically, the sum of {25} odd numbers is odd.

Prime numbers

Unique prime factorization

A number can be factored several different ways. For example, we can factor {36} as {(1 \times 36),} {(2 \times 18),} {(3 \times 12),} {(4 \times 9),} and {(6 \times 6).}

However, if we restrict the factors to being prime numbers, then we can only factor {36} one way: {(2 \times 2 \times 3 \times 3),} if we ignore different orderings of the factors.

In general, we can say that:

Every positive integer can be expressed as a product
of prime numbers, and the factorization is unique,
ignoring different orderings.

This is called the unique prime factorization theorem,
or the fundamental theorem of arithmetic.

Here’s a table of the first few prime factorizations:

{1 }		(no prime factorization)
{2 }	{ \ = \ }	{2}
{3 }	{ \ = \ }	{3}
{4 }	{ \ = \ }	{2 \times 2}
{5 }	{ \ = \ }	{5}
{6 }	{ \ = \ }	{2 \times 3}
{7 }	{ \ = \ }	{7}
{8 }	{ \ = \ }	{2 \times 2 \times 2}
{9 }	{ \ = \ }	{3 \times 3}
{10}	{ \ = \ }	{2 \times 5}
{11}	{ \ = \ }	{11}
{12}	{ \ = \ }	{2 \times 2 \times 3}
{13}	{ \ = \ }	{13}
{14}	{ \ = \ }	{2 \times 7}
{15}	{ \ = \ }	{3 \times 5}
{16}	{ \ = \ }	{2 \times 2 \times 2 \times 2}
{17}	{ \ = \ }	{17}
{18}	{ \ = \ }	{2 \times 2 \times 3}
{19}	{ \ = \ }	{19}
{20}	{ \ = \ }	{2 \times 2 \times 5}

The unique prime factorization theorem is a fundamentally important result in number theory. The importance of this theorem explains two things:

• It explains why {1} is not a prime number. For example, we wouldn’t want the number {6} to be factored into “primes” as both {(2 \times 3)} and {(1 \times 2 \times 3),} because the factorization would no longer be unique.

• It explains why no negative number is prime. For example, we wouldn’t want the number {6} to be factored into “primes” as both {(2 \times 3)} and {(-2 \times -3),} because the factorization would no longer be unique.

We exclude all integers less than {2} from the set of prime numbers, so that prime factorizations can always be unique.

Unique prime factorization: a useful application

We can use the unique prime factorization theorem to prove that {\sqrt{2}} is irrational.

1. First, assume that {\sqrt{2}} is rational. This means that the following equation must have a solution for some pair of integers {a} and {b}:

   [[ \sqrt{2} = {{a} \over {b}} ]]

2. Square of both sides of the equation, and then multiply both sides by {b^{\large 2}}:

   [[ 2 = {{a^{\large 2}} \over {b^{\large 2}}} ]]

   [[ 2 b^{\large 2} = a^{\large 2} ]]

3. Observe that if a number is a perfect square (like {a^{\large 2}} and {b^{\large 2}}), then it must have an even number of prime factors.

   For example, {30} has {3} prime factors: {(2 \times 3 \times 5),} so it has an odd number of prime factors. If we square it, we obtain {900 = (2 \times 2 \times 3 \times 3 \times 5 \times 5).} Every prime factor in {900} appears twice, so the number of prime factors {(6)} is even.

   Every perfect square {n^{\large 2}} can be constructed in this way, by “doubling up” the prime factors of {n.} Therefore, every perfect square must have an even number of prime factors.

4. Looking again at the equation from step 2:

   [[ 2 b^{\large 2} = a^{\large 2} ]]

   we can observe the following:

   • The number of prime factors on the right side of the equation is even, because it’s a perfect square.
   • The number of prime factors on the left side of the equation is odd, because it consists of an even number of factors (from {b^{{\large 2}}}) along with one additional factor: {2.}

5. No number can be both even and odd, so in this equation:

   [[ 2 b^{\large 2} = a^{\large 2} ]]

   the number of prime factors on the left side must be different than the number of prime factors on the right side.

6. {2 b^{\large 2}} and {a^{\large 2}} have a different number of prime factors, so, by the unique prime factorization theorem, we know that {2 b^{\large 2}} and {a^{\large 2}} must be different numbers. Therefore, the equation is false for all values of {a} and {b.}

7. Since the equation is always false, our initial assumption in step 1 must also be false:
   There is no integer solution for [[ \sqrt{2} = {\vphantom{1}{a} \over {b}}, ]] and therefore {\sqrt{2}} is irrational.

This proof can easily be extended to show that the square root of every prime number is irrational.

GCD and LCM

For example, {\text{gcd}(12,15) = 3,} because {3} is the largest number that divides both {12} and {15.}

For example, {\text{lcm}(6,9) = 18,} because {18} is the smallest number that’s a multiple of both {6} and {9.}

Every positive integer can be uniquely described as the product of the powers of all the prime numbers. Here are some examples:

{\phantom{0}48 = 2^{\raise 3pt \Large{4}} \cdot 3^{\raise 3pt \Large{1}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{0}} \cdot 11^{\raise 3pt \Large{0}} \cdots \ } (continuing without end)

{126 = 2^{\raise 3pt \Large{1}} \cdot 3^{\raise 3pt \Large{2}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{1}} \cdot 11^{\raise 3pt \Large{0}} \cdots \ } (continuing without end)

{\phantom{00}1 = 2^{\raise 3pt \Large{0}} \cdot 3^{\raise 3pt \Large{0}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{0}} \cdot 11^{\raise 3pt \Large{0}} \cdots \ } (continuing without end)

If we multiply {48} and {126} together, we add the exponents of each prime factor together:

{48 \times 126 \ \ = \ \ 2^{\raise 3pt \Large{(4\mathord{+}1})} \cdot 3^{\raise 3pt \Large{(1\mathord{+}2)}} \cdot 5^{\raise 3pt \Large{(0\mathord{+}0)}} \cdot 7^{\raise 3pt \Large{(0\mathord{+}1)}} \cdot 11^{\raise 3pt \Large{(0\mathord{+}0)}} \cdots}

{6048 \ \ = \ \ 2^{\raise 3pt \Large{5}} \cdot 3^{\raise 3pt \Large{3}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{1}} \cdot 11^{\raise 3pt \Large{0}} \cdots}

The methods for determining the {\text{gcd}} and the {\text{lcm}} are very similar. Using {48} and {126} as an example:

1. To find the greatest common divisor of {48} and {126,} first express both of them as a product of primes:

   {\phantom{0}48 = 2^{\raise 3pt \Large{4}} \cdot 3^{\raise 3pt \Large{1}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{0}} \cdot 11^{\raise 3pt \Large{0}} \cdots \ } (continuing without end)

   {126 = 2^{\raise 3pt \Large{1}} \cdot 3^{\raise 3pt \Large{2}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{1}} \cdot 11^{\raise 3pt \Large{0}} \cdots \ } (continuing without end)

   then select the smallest power of each prime factor that appears in either number:

   {\phantom{126 = , } 2^{\raise 3pt \Large{1}} \cdot 3^{\raise 3pt \Large{1}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{0}} \cdot 11^{\raise 3pt \Large{0}} \cdots \ }

   and multiply them to obtain the result:

   {\text{gcd}(48, 126) \ = \ 2^{\raise 3pt \Large{1}} \cdot 3^{\raise 3pt \Large{1}} \ = \ 6}

2. To find the least common multiple of {46} and {126,} first express both of them as a product of primes:

   {\phantom{0}48 = 2^{\raise 3pt \Large{4}} \cdot 3^{\raise 3pt \Large{1}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{0}} \cdot 11^{\raise 3pt \Large{0}} \cdots \ } (continuing without end)

   {126 = 2^{\raise 3pt \Large{1}} \cdot 3^{\raise 3pt \Large{2}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{1}} \cdot 11^{\raise 3pt \Large{0}} \cdots \ } (continuing without end)

   then select the largest power of each prime factor that appears in either number:

   {\phantom{126 = , } 2^{\raise 3pt \Large{4}} \cdot 3^{\raise 3pt \Large{2}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{1}} \cdot 11^{\raise 3pt \Large{0}} \cdots \ }

   and multiply them to obtain the result:

   {\text{lcm}(48, 126) \ = \ 2^{\raise 3pt \Large{4}} \cdot 3^{\raise 3pt \Large{2}} \cdot 7^{\raise 3pt \Large{1}} \ = \ 1008}

The {\mathbf{\text{gcd}}} and {\mathbf{\text{lcm}}} are related by this equation:

{ \text{gcd}(a, b) \times \text{lcm}(a, b) = |ab| }

This allows you to easily calculate the {\mathbf{\text{gcd}}} from the {\mathbf{\text{lcm}},} or vice-versa.

If {a} or {b} are negative, replace them with {|a|} or {|b|} when calculating the {\mathbf{\text{gcd}}} and the {\mathbf{\text{lcm}}.}

We treat {0} as a special case, because {0} cannot be expressed as a product of primes:

{\text{gcd}(a, 0) = |a|}
{\text{lcm}(a, 0) = 0}

GCD of large numbers

If you’re calculating the {\mathbf{\text{gcd}}} of large numbers, you can use the following rule to calculate it faster:

{\text{gcd}(a, b) = \text{gcd}(a - b, \, b)}

where {a} is the larger of the two numbers.

For example, you can simplify {\text{gcd}(105, 70)} by replacing {105} with {105-70,} to get {\text{gcd}(35, 70).} Once you do that, it becomes easier to see that the {\text{gcd}} is {35.}

For extra speed, you can subtract a multiple of {b,} like this:

{\text{gcd}(a, b) = \text{gcd}(a - nb, \, b)}   for any {n > 0}

For example, you can simplify {\text{gcd}(1216, 40)} by subtracting the largest multiple of {40} that you can from {1216} without going negative. In this case, we can subtract {1200} from {1216,} allowing us to simplify it to {\text{gcd}(16, 40),} which makes it easier to see that the {\text{gcd}} is {8.}

Relatively prime

For example, these two integers are relatively prime:

{220 = 2^{\raise 3pt \Large{2}} \cdot 3^{\raise 3pt \Large{0}} \cdot 5^{\raise 3pt \Large{1}} \cdot 7^{\raise 3pt \Large{0}} \cdot 11^{\raise 3pt \Large{1}} \cdots \ }

{\phantom{0}63 = 2^{\raise 3pt \Large{0}} \cdot 3^{\raise 3pt \Large{2}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{1}} \cdot 11^{\raise 3pt \Large{0}} \cdots \ }

Notice that for each prime number on the right sides of the equations, at least one of its two exponents is {0.}

If you reduce a rational number to lowest terms, its numerator and denominator become relatively prime. That’s because you cancel out all the factors that are common to both the numerator and denominator, leaving only the factors that are not common.

The number {1} is relatively prime to all positive integers.

Exercises (part 2)

1. What is the prime factorization of {48{,}000} ? Answer
   • {48{,}000 = (6 \mathord{\times} 8) \times (10 \mathord{\times} 10 \mathord{\times} 10) }
   • {48{,}000 = ((2 \mathord{\times} 3) \mathord{\times} (2 \mathord{\times} 2 \mathord{\times} 2)) \times ((2 \mathord{\times} 5) \mathord{\times} (2 \mathord{\times} 5) \mathord{\times} (2 \mathord{\times} 5)) }
   • {48{,}000 = 2^{\raise 3pt \Large{7}} \cdot 3^{\raise 3pt \Large{1}} \cdot 5^{\raise 3pt \Large{3}} \ }

2. Are {224} and {105} relatively prime? Answer
   • {224 = 2^{\raise 3pt \Large{5}} \cdot 3^{\raise 3pt \Large{0}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{1}} \cdots \ }
   • {105 = 2^{\raise 3pt \Large{0}} \cdot 3^{\raise 3pt \Large{1}} \cdot 5^{\raise 3pt \Large{1}} \cdot 7^{\raise 3pt \Large{1}} \cdots \ }
   • {\text{gcd}(224,105) = 2^{\raise 3pt \Large{0}} \cdot 3^{\raise 3pt \Large{0}} \cdot 5^{\raise 3pt \Large{0}} \cdot 7^{\raise 3pt \Large{1}} \cdots \ }
   • {\text{gcd}(224,105) = 7 }
   • Answer: no, they have a factor of {7} in common.

   A faster approach is to find the largest multiple of {105} that’s less than {224} (which is {210}), and then subtract {224 - 210} to get {14,} which simplifies it to {\text{gcd}(14,105).} Now, you only need to investigate whether {105} is divisible by {14,} {7,} {2,} or {1,} and choose the greatest divisor of those four possibilities.

3. What is the least common multiple of {180} and {72} ? Answer
   • {180 = 2^{\raise 3pt \Large{2}} \cdot 3^{\raise 3pt \Large{2}} \cdot 5^{\raise 3pt \Large{1}} \cdots \ }
   • {\phantom{0}72 = 2^{\raise 3pt \Large{3}} \cdot 3^{\raise 3pt \Large{2}} \cdot 5^{\raise 3pt \Large{0}} \cdots \ }
   • {\text{lcm}(180,72) = 2^{\raise 3pt \Large{3}} \cdot 3^{\raise 3pt \Large{2}} \cdot 5^{\raise 3pt \Large{1}} \cdots \ }
   • {\text{lcm}(180,72) = 360 }

Congruence

When performing arithmetic, it’s sometimes interesting to focus on only the last digit of the numbers.

For example, if we look at the table of {5}th powers, we see an interesting pattern in the last digit of each number:

{ \begin{array}{llr} 0^{\large 5} &\hspace-5pt = &\hspace-5pt 0 \\[-3pt] 1^{\large 5} &\hspace-5pt = &\hspace-5pt 1 \\[-3pt] 2^{\large 5} &\hspace-5pt = &\hspace-5pt 32 \\[-3pt] 3^{\large 5} &\hspace-5pt = &\hspace-5pt 243 \\[-3pt] 4^{\large 5} &\hspace-5pt = &\hspace-5pt 1{,}024 \\[-3pt] 5^{\large 5} &\hspace-5pt = &\hspace-5pt 3{,}125 \\[-3pt] 6^{\large 5} &\hspace-5pt = &\hspace-5pt 7{,}776 \\[-3pt] 7^{\large 5} &\hspace-5pt = &\hspace-5pt 16{,}807 \\[-3pt] 8^{\large 5} &\hspace-5pt = &\hspace-5pt 32{,}768 \\[-3pt] 9^{\large 5} &\hspace-5pt = &\hspace-5pt 59{,}049 \\[-3pt] 10^{\large 5} &\hspace-5pt = &\hspace-5pt 100{,}000 \\[-3pt] 11^{\large 5} &\hspace-5pt = &\hspace-5pt 161{,}051 \\[-3pt] 12^{\large 5} &\hspace-5pt = &\hspace-5pt 248{,}832 \\[-3pt] 13^{\large 5} &\hspace-5pt = &\hspace-5pt 371{,}293 \\[-3pt] 14^{\large 5} &\hspace-5pt = &\hspace-5pt 537{,}824 \\[-3pt] 15^{\large 5} &\hspace-5pt = &\hspace-5pt 759{,}375 \\[-3pt] \end{array} }

The last digit of {n^{\large 5}} is always the same as the last digit of {n.} We can express this result using congruence notation:

{n^{\large 5} \equiv n \ (\text{mod } 10) }

This is pronounced “{n^{\large 5}} is congruent to {n} modulo {10}”. It means that {n^{\large 5} - n} is always a multiple of {10.}

In general:

For three integers {a,} {b,} and {m}:

If {a-b} is a multiple of {m,} then we can say:

“{a} is congruent to {b} modulo {m}”.

and we write it like this:

{a \equiv b \ (\text{mod } m) }

We restrict {m} to being a positive integer.

For example, we can say:

{67 \equiv 27 \ (\text{mod } 10) }

because {67 - 27} is a multiple of {10.} It’s equivalent to saying:

{10 | (67 - 27)}

The symbol {\text{“}\mathord{\equiv}\text{”}} is the congruent symbol. It’s not the equal sign, and it does not imply equality. However, we’ll see in a later section that it does share some of the same properties that equality has. When using the {\text{“}\mathord{\equiv}\text{”}} symbol, the {\text{“} \hspace-2pt \ (\text{mod } m) \text{”}} notation at the end is required. The number {m} is called the modulus.

Euclidean division

Euclidean division is integer division that produces both a quotient and a remainder. Specifically:

In Euclidean division, we perform the division [[ {a} \over {m} ]] by producing a quotient {q} and a remainder {r,} such that:

{a = qm + r}

All four variables {a,} {m,} {q,} and {r} are integers, with the following two restrictions:

{m \ne 0}
{0 \le r \lt |m|}

The remainder {r} is always chosen to be the smallest number that’s not negative. This is true even when the numerator or denominator are negative.

For example, if [[ {a \over m} = {{-1} \over {3}}, ]] it produces a quotient of {q = -1} with a remainder of {r = 2.}

Notice that this result satisfies both requirements: {\ a = qm + r \ } and {\ 0 \le r \lt |m|.}

If you selected any other quotient besides {q = -1,} the resulting remainder {r} would violate the requirement that {0 \le r \lt |m|.}

Consider this congruence again:

{a \equiv b \ (\text{mod } m)}

It means:

“{a - b} is a multiple of {m.}”

But you can also interpret it this way:

“The remainder of [[a \over m]] equals the remainder of [[b \over m]].”

For example, in this congruence:

{67 \equiv 27 \ (\text{mod } 10) }

Floor

If you want division to produce only the quotient {(q),} and ignore the remainder, then you can use this notation:

[[ \left \lfloor {{a} \over {m}} \right \rfloor = q ]]

For example, we can say:

[[ \left \lfloor {{17} \over {3}} \right \rfloor = 5 ]]   (the remainder {2} is ignored)

The notation [[ {\large \left \lfloor {\normalsize x} \right \rfloor } ]] is called “the floor of {x}”, and is used to obtain the greatest integer that’s less than or equal to {x.}

If you want to round a real number {x} to the nearest integer, then use [[ {\large \left \lfloor {\normalsize x + 0.5} \right \rfloor }. ]]

Using {\mathbf{\text{mod}}} as an operator

Most calculators and computer programming languages do not support the congruence notation. However, most of them do support the use of {\mathbf{\text{mod}}} as an arithmetic operator.

The {\mathbf{\text{mod}}} operator produces the remainder after Euclidean division. Here are some examples:

{ 8 \text{ mod } 3 = 2}	(because {8} divided by {3} is {2} with a remainder of {2})
{ 7 \text{ mod } 3 = 1}	(because {7} divided by {3} is {2} with a remainder of {1})
{ 6 \text{ mod } 3 = 0}	(because {6} divided by {3} is {2} with a remainder of {0})
{ 5 \text{ mod } 3 = 2}	(because {5} divided by {3} is {1} with a remainder of {2})
{ 4 \text{ mod } 3 = 1}	(because {4} divided by {3} is {1} with a remainder of {1})

The {\mathbf{\text{mod}}} operator allows us to use equations instead of congruences. For example, we can take this congruence:

{ 8 \equiv 5 \ (\text{mod } 3) }

and write it equivalently as:

{ 8 \text{ mod } 3 \ = \ 5 \text{ mod } 3 }

An application of the {\mathbf{\text{mod}}} operator

Notice that for every integer {n}:

{|n| \text{ mod } 10\phantom{0}\phantom{0} }	produces the last digit of {n}
{|n| \text{ mod } 100\phantom{0} }	produces the last two digits of {n}
{|n| \text{ mod } 1000 }	produces the last three digits of {n}
etc.

Using {|n| \text{ mod } 10,} you can extract any individual digit of an integer {n,} like this:

{|n| \text{ mod } 10}	produces the last digit of {n}
[[ \left \lfloor {|n| \over {10}} \right \rfloor \text{ mod } 10 ]]	produces the second-to-last digit of {n}
[[ \left \lfloor {|n| \over {100}} \right \rfloor \text{ mod } 10 ]]	produces the third-to-last digit of {n}
[[ \left \lfloor {|n| \over {1000}} \right \rfloor \text{ mod } 10 ]]	produces the fourth-to-last digit of {n}
etc.

Exercises (part 3)

1. What is the remainder when dividing {36{,}029} by {12} ? Answer
   • {3 \times 12 = 36}
   • {3{,}000 \times 12 = 36{,}000}
   • {3{,}002 \times 12 = 36{,}024}
   • {3{,}002 \times 12 + 5 = 36{,}029}
   • The left side in the form: {qm + r}
   • {q = 3{,}002}
   • {r = 5}

2. Using {\mathbf{\text{mod}}} as an operator, if {n \text{ mod } 2 = 1,} what type of number is {n} ? Answer
   {n} is an odd number.

3. Is it true that {37 \equiv -11 \ (\text{mod } 12) } ? Answer
   • {37 \equiv -11 \ (\text{mod } 12)}
   • {37 - (-11)} is a multiple of {12}
   • Simplifying: {48} is a multiple of {12}
   • The result is true, so the original congruence is true.

4. Is it true that {(10^{\large n} - 1) \equiv 4 \ (\text{mod } 5) } for all integers {n \ge 0} ?
   If not, find a counterexample. If so, explain why. Answer
   • {(10^{\large n} - 1) \equiv 4 \ (\text{mod } 5) }
   • {(10^{\large n} - 1) - 4} is a multiple of {5}
   • Simplifying: {(10^{\large n} - 5)} is a multiple of {5}
   • {5} divides both {10^{\large n}} and {5,} so {5} must also divide {(10^{\large n} - 5)}
   • The result is true, so the original congruence is true.

Congruence class

Here’s an example of a set of numbers that are all congruent to each other modulo {10}:

{ \lbrace \cdots, -47, -37, -27, -17, -7, \ 3, \ 13, \ 23, \ 33, \ 43, \ \cdots \rbrace }

To show this, we can pick any one of them (let’s say {3}), and see that all the others are congruent to it:

{ 23 \equiv 3 \ (\text{mod } 10) }	means that	{23 - 3} is a multiple of {10}
{ 13 \equiv 3 \ (\text{mod } 10) }	means that	{13 - 3} is a multiple of {10}
{ 3 \equiv 3 \ (\text{mod } 10) }	means that	{ 3 - 3} is a multiple of {10}
{ -7 \equiv 3 \ (\text{mod } 10) }	means that	{-7 - 3} is a multiple of {10}
{ -17 \equiv 3 \ (\text{mod } 10) }	means that	{-17 - 3} is a multiple of {10}

A set of numbers that are all congruent to each other is called a congruence class.
The set is always infinite in size.

It’s convenient to pick one of these numbers to serve as the representative of the class. The standard is to pick the smallest non-negative number as the representative, which in this case is {3.}

When {\mathbf{\text{mod}}} is used as an operator, it produces the representative. For example:

{ 23 \text{ mod } 10 = 3}

{ 13 \text{ mod } 10 = 3}

{ 3 \text{ mod } 10 = 3}

{ -7 \text{ mod } 10 = 3}

{ -17 \text{ mod } 10 = 3}

etc.

For every modulus {m}, there are {m} congruence classes. For example, here’s a list of the {5} congruence classes for modulus {5,} each labeled with its representative:

congruence class {0}:		{\lbrace \cdots, -20, -15, \mathord{-}10, -5, \ 0, \ 5, \ 10 , \ 15, \ 20, \ \cdots \rbrace}
congruence class {1}:		{\lbrace \cdots, -19, -14, \phantom{0}\mathord{-} 9, -4, \ 1, \ 6, \ 11 , \ 16, \ 21, \ \cdots \rbrace}
congruence class {2}:		{\lbrace \cdots, -18, -13, \phantom{0}\mathord{-} 8, -3, \ 2, \ 7, \ 12 , \ 17, \ 22, \ \cdots \rbrace}
congruence class {3}:		{\lbrace \cdots, -17, -12, \phantom{0}\mathord{-} 7, -2, \ 3, \ 8, \ 13 , \ 18, \ 23, \ \cdots \rbrace}
congruence class {4}:		{\lbrace \cdots, -16, -11, \phantom{0}\mathord{-} 6, -1, \ 4, \ 9, \ 14 , \ 19, \ 24, \ \cdots \rbrace}

or, more generally, for any modulus {m}:

congruence class {0}:		{\lbrace km :} for all integers {k}{\rbrace}
congruence class {1}:		{\lbrace km + 1 :} for all integers {k}{\rbrace}
congruence class {2}:		{\lbrace km + 2 :} for all integers {k}{\rbrace}
congruence class {3}:		{\lbrace km + 3 :} for all integers {k}{\rbrace}
{\cdots}
congruence class {m\mathord{-}1}:		{\lbrace km - 1 :} for all integers {k}{\rbrace}

A congruence class is sometimes called a “residue class”, and the representative of the class is sometimes called the “least residue”. The word “residue” means the remainder after division.

Congruence properties

In this section, we’ll see that congruence modulo {m} has many of the same properties that equality does.

Basic properties:

reflexivity:	{a \equiv a \ (\text{mod } m)}
symmetry:	if {\ a \equiv b \ (\text{mod } m) \ } then { \ b \equiv a \ (\text{mod } m)}
transitivity:	if {\ a \equiv b \ (\text{mod } m) \ } and { \ b \equiv c \ (\text{mod } m) \ } then { \ a \equiv c \ (\text{mod } m)}

If {\ a \equiv b \ (\text{mod } m),\ } then:

{(a + k) ≡ (b + k) \ (\text{mod } m) }	for any integer {k}
{(a - k) ≡ (b - k) \ (\text{mod } m) }	for any integer {k}
{(ka) ≡ (kb) \ (\text{mod } m) }	for any integer {k}
{(a^{\large n} ) ≡ (b^{\large n}) \ (\text{mod } m) }	for any integer {n \ge 0}

If {\ a \equiv b \ (\text{mod } m)\ } and {\ c \equiv d \ (\text{mod } m),\ } then:

{(a + c) ≡ (b + d) \ (\text{mod } m) }

{(a - c) ≡ (b - d) \ (\text{mod } m) }

{(ac) ≡ (bd) \ (\text{mod } m) }

If {\ a \equiv b \ (\text{mod } m),\ } then these are special properties that are unique to congruence:

{a ≡ (b \pm km) \ (\text{mod } m) }	for any integer {k}
{(km) \equiv 0 \ (\text{mod } m)}	for any integer {k}

Example congruence problems

The congruence properties from the previous section can be used to solve certain types of problems quickly.

Example 1:

We can quickly find the remainder of {3^{\large 18}} divided by {5} as follows:

{3^{\large 3} = 27}	(start with a known power of {3})
{3^{\large 3} \equiv 2 \ (\text{mod } 5)}	(find the remainder of {27} divided by {5})
{3^{\large 18} \equiv 2^{\large 6} \ (\text{mod } 5)}	(take both sides to the {6}th power)
{3^{\large 18} \equiv 64 \ (\text{mod } 5)}	(simplify)
{3^{\large 18} \equiv 4 \ (\text{mod } 5)}	(find the remainder of {64} divided by {5})

The last line shows that the remainder is {4.}

Question: How would you modify this to find the remainder of {3^{\large 19}} divided by {5} ?

Example 2:

We can quickly prove that {(2^{\large 64} - 1)} is a multiple of {3} as follows:

{2 \equiv -1 \ (\text{mod } 3)}	(start with a simple congruence)
{2^{\large 64} \equiv (-1)^{\large 64} \ (\text{mod } 3)}	(take both sides to the {64}th power)
{2^{\large 64} \equiv 1 \ (\text{mod } 3)}	(the exponent is even, so {(-1)^{\large 64} = 1})
{(2^{\large 64} - 1) \equiv 0 \ (\text{mod } 3)}	(subtract {1} from both sides)

The last line shows that {(2^{\large 64} - 1)} is a multiple of {3.}

Example 3:

We can quickly find the last digit of {942^{\large 5}} as follows:

{942 ≡ 2 \ (\text{mod } 10)}	(start with a simple congruence)
{942^{\large 5} ≡ 2^{\large 5} \ (\text{mod } 10)}	(take both sides to the {5}th power)
{942^{\large 5} ≡ 32 \ (\text{mod } 10)}	(simplify)
{942^{\large 5} ≡ 2 \ (\text{mod } 10)}	(find the remainder of {32} divided by {10})

Question: How would you modify this to find the last digit of {942^{\large 20}} ?

Exercises (part 4)

1. What is the last digit of {5073^{\large 4}} ? Answer
   • {5073 \equiv 3 \ (\text{mod } 10)}
   • so:  {5073^{\large 4} \equiv 3^{\large 4} \ (\text{mod } 10)}
   • and: {3^{\large 4} \equiv 81 \equiv 1 \ (\text{mod } 10)}
   • Answer: {1}

2. If a {12}-hour analog clock shows {5{:}00,} what time will it show {249} hours later?
   The clock is unable to distinguish AM versus PM. Answer
   • {5 \equiv 5 \ (\text{mod } 12)}
   • {240 \equiv 0 \ (\text{mod } 12)}
   • {249 \equiv 9 \ (\text{mod } 12)}
   • so:  {(5 + 249) \equiv (5 + 9) \ (\text{mod } 12)}
   • and: {(5 + 249) \equiv 14 \ (\text{mod } 12)}
   • and: {(5 + 249) \equiv 2 \ (\text{mod } 12)}
   • Answer: {2{:}00}