Chapter 5 — Using the Integers
Math involving the properties of integers is called number theory. Despite being a restricted class of numbers, the integers have rich and fascinating properties.
Topics in this chapter:
5.1 Divisibility
An integer $n$ is divisible by a different integer $m$ if $n$ is an integral multiple of $m$. For example, $15$ is divisible by $3$ because $15 = 5 \cdot 3$.
The numbers that divide a given integer are called its divisors. E.g. divisors of $12$: $1, 2, 3, 4, 6, 12$.
Notation: $m \mid n$ means “$m$ divides $n$.” $\;m \nmid n$ means “$m$ does not divide $n$.”
- Prime: An integer greater than 1 whose only divisors are $1$ and itself. E.g. $2, 3, 5, 7$.
- Composite: An integer that has divisors other than $1$ and itself. E.g. $4, 6, 8, 9$.
Warning: $1$ is not considered prime! It is also not composite. The primes less than 10 are $2, 3, 5, 7$.
Exercise 5-1: Write down all divisors of 20.
Exercise 5-2: Write down all primes between 11 and 20 inclusive.
Exercise 5-3: How many even primes are there?
5.2 Number Bases
Our usual number system is base 10 (decimal). The integer $7965841$ can be written as:
\[7 \times 10^6 + 9 \times 10^5 + 6 \times 10^4 + 5 \times 10^3 + 8 \times 10^2 + 4 \times 10^1 + 1 \times 10^0\]In base $b$, a number uses digits $0, 1, \ldots, b-1$, and each position represents a power of $b$.
Notation: $47_{10}$ means 47 in base 10; $47_8$ means 47 in base 8 (octal).
Converting Base $b$ → Base 10
Expand each digit times its positional power of $b$.
Example 5-1: Convert $3456_7$ to base 10.
\[3 \times 7^3 + 4 \times 7^2 + 5 \times 7^1 + 6 \times 7^0 = 1029 + 196 + 35 + 6 = 1266\]Converting Base 10 → Base $b$
Repeatedly divide by powers of $b$, recording quotients as digits.
Example 5-2: Convert $216_{10}$ to base 4.
Powers of 4: $1, 4, 16, 64, 256, \ldots$. The highest usable power is $64 = 4^3$.
- $\lfloor 216/64 \rfloor = 3$, remainder $216 - 192 = 24$
- $\lfloor 24/16 \rfloor = 1$, remainder $24 - 16 = 8$
- $\lfloor 8/4 \rfloor = 2$, remainder $8 - 8 = 0$
- Last digit: $0$
Special Bases
| Base | Name | Digits |
|---|---|---|
| 2 | Binary | $0, 1$ |
| 8 | Octal | $0$–$7$ |
| 10 | Decimal | $0$–$9$ |
| 16 | Hexadecimal | $0$–$9$, $A$–$F$ ($A=10,\ldots,F=15$) |
Example 5-3: Add $10011102$ and $11001101_2$ in binary.
Perform column-by-column addition with carrying (just like base 10):
\[\begin{array}{r} 10011102 \\ +\; 11001101_2 \\ \hline 100011011_2 \end{array}\]Check: $78 + 205 = 283$. And $100011011_2 = 256 + 16 + 8 + 2 + 1 = 283$ ✓
Exercise 5-4: Find the base 10 representations of $478$, $47_9$, and $47{16}$.
Exercise 5-5: Find the base 8, 9, and 16 representations of $47_{10}$.
Exercise 5-6: Find the base 10 equivalents of $BEEDEF_{16}$ and $A1_k$ (for some base $k$).
Exercise 5-7: How do you multiply a number by 2 in base 2?
Exercise 5-8: Practice some conversions into and out of binary.
5.3 The Last Digit
Key principle: To find the last digit of a sum or product, take the last digit of each operand, perform the operation, and take the last digit of the result. This works in any base.
Exercise 5-9: Verify: find the last digits of $34 \cdot 17$ and $34 + 17$ by (a) doing the full computation, then (b) using only last digits. Explain why it works.
Exercise 5-10: In base 10, what digits cannot be the last digit of a perfect square?
Example 5-4: Find the units digit of $7^{42} + 4^{27}$.
Solution: Powers of 7 cycle in their last digit: $7^1 \to 7$, $7^2 \to 9$, $7^3 \to 3$, $7^4 \to 1$, then repeats (period 4).
$42 = 4 \times 10 + 2$, so $7^{42}$ ends in the same digit as $7^2 = 9$.
For $4^{27}$: only the units digit of the base matters — last digit of $4^{27}$ = last digit of $4^{27}$. Since $4^1 = 4$, $4^2 = 16$, the cycle is $4, 6, 4, 6, \ldots$ (period 2). Since 27 is odd, last digit is $4$. But the base is $4$ (from $4^{27}$): we need $2^{27}$, and $2^7 = 128$ → last digit $8$. So $4^{27}$ ends in $8$.
$9 + 8 = 17$, last digit is 7.
5.4 Modular Arithmetic
Congruence: We write $a \equiv b \pmod{m}$ if $a$ and $b$ have the same remainder when divided by $m$. Equivalently, $m \mid (a - b)$.
\[12 \equiv 7 \pmod{5} \quad\text{because}\quad 12 - 7 = 5.\]All numbers congruent to $2 \pmod{5}$: $\;\ldots, -13, -8, -3, 2, 7, 12, 17, \ldots$
Negative mods: $2 \equiv -3 \pmod{5}$ since $2$ is $3$ less than the next multiple of $5$.
Example 5-5: Why does the remainder method work?
Consider $7631$ in base 7: $7631 = 3 \cdot 7^4 + 1 \cdot 7^3 + 1 \cdot 7^2 + 5 \cdot 7 + 1$. Dividing by 7, the last term is the remainder. So the last digit in base $b$ equals the remainder upon division by $b$.
Example 5-6: How many positive integers less than 100 are congruent to $3 \pmod{5}$?
Solution: The smallest is $3 = 0(5) + 3$, the largest is $98 = 19(5) + 3$. The multiplier ranges from $0$ to $19$, giving 20 numbers.
Properties of Congruences
If $a \equiv b \pmod{m}$, then for all positive integers $c$:
| Property | Statement |
|---|---|
| Addition | $a + c \equiv b + c \pmod{m}$ |
| Subtraction | $a - c \equiv b - c \pmod{m}$ |
| Multiplication by constant | $ac \equiv bc \pmod{m}$ |
| Powers | $a^c \equiv b^c \pmod{m}$ |
| Add before or after mod | $(a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m$ |
| Multiply before or after mod | $(ab) \bmod m = ((a \bmod m)(b \bmod m)) \bmod m$ |
Warning — Division does NOT generally work! $5 \equiv 10 \pmod{5}$ but dividing both sides by 5 gives $1 \equiv 2 \pmod{5}$, which is FALSE.
Example 5-7: If $a \equiv 0 \pmod{b}$, then $b \mid a$ (the remainder is 0, so $a$ is a multiple of $b$).
Exercise 5-11: Write down some numbers congruent to $3 \pmod{5}$.
Exercise 5-12: What is the largest integer less than 100 congruent to $3 \pmod{5}$?
Exercise 5-13: How many integers are between 50 and 250 inclusive that are congruent to $1 \pmod{7}$?
Exercise 5-14: Which numbers are congruent to $0 \pmod{5}$?
Exercise 5-15: Find the smallest positive integer that $123$ is congruent to mod 4. Find the smallest positive integer that $321$ is congruent to mod 7.
Exercise 5-16: Show that the square of any integer is congruent to either $0$, $1$, or $4 \pmod{8}$.
5.5 Divisibility Tricks
A number $x$ is divisible by $y$ if and only if $x \equiv 0 \pmod{y}$.
Summary of Divisibility Rules
| Divisor | Rule |
|---|---|
| 2 | Last digit is even ($0, 2, 4, 6, 8$) |
| 4 | Last two digits form a number divisible by 4 |
| 8 | Last three digits form a number divisible by 8 |
| 5 | Last digit is $0$ or $5$ |
| 10 | Last digit is $0$ |
| 3 | Sum of digits is divisible by 3 |
| 9 | Sum of digits is divisible by 9 |
| 11 | Alternating sum of digits is divisible by 11 |
| Composite $n$ | Check divisibility by each prime power factor of $n$ |
Why These Work
For 2, 4, 8: Since $10 \equiv 0 \pmod{2}$, $100 \equiv 0 \pmod{4}$, $1000 \equiv 0 \pmod{8}$, only the last 1, 2, or 3 digits matter.
For 3 and 9: Since $10 \equiv 1 \pmod{3}$ (and mod 9), every power of 10 reduces to 1, so a number is congruent to the sum of its digits.
For 11: Since $10 \equiv -1 \pmod{11}$, powers of 10 alternate between $1$ and $-1$. So a number is congruent to its alternating digit sum.
Example — Divisibility by 3: Is $7965$ divisible by 3?
$7 + 9 + 6 + 5 = 27$, and $27$ is divisible by 3. Yes! ✓
Example 5-8: How would you test for divisibility by 12?
Solution: $12 = 4 \times 3$. A number is divisible by 12 if and only if it is divisible by both 4 and 3. Test each separately using the rules above.
Exercise 5-17: Find a shortcut to test for divisibility by 5.
Exercise 5-18: Find shortcuts for 4, 8, and 20.
Exercise 5-19: Why is it easy to test divisibility by these numbers?
Exercise 5-20: Test $1717$, $3451$, and $173451$ for divisibility by 3 using the shortcut and by direct division.
Exercise 5-21: Derive the divisibility rule for 9 using $10 \equiv 1 \pmod{9}$.
Exercise 5-22: Which of $4995, 4996, 4997, 4998, 4999$ is divisible by 3 but not by 9?
Exercise 5-23: Which of $11, 111, 1111, 1716, 1761, 152637$ are divisible by 11?
Exercise 5-24: Prove that a two-digit number is divisible by 11 iff its digits are the same.
5.6 Primes
Fundamental Theorem of Arithmetic: Every integer greater than 1 has a unique prime factorization (up to the order of factors).
Examples: $15 = 3 \cdot 5$, $\quad 48 = 2^4 \cdot 3$, $\quad 123420 = 2^2 \cdot 3 \cdot 5 \cdot 11^2 \cdot 17$.
Finding Prime Factorizations
- Factor out small primes ($2, 3, 5$) using divisibility rules.
- Test for $7, 11, 13, \ldots$ by trial division.
- Key insight: If $N$ is not prime, it must have a prime factor $\leq \sqrt{N}$. So if no prime up to $\sqrt{N}$ divides $N$, then $N$ is prime.
Example 5-9: Factor $123420$.
$123420 = 10 \times 12342 = 2 \cdot 5 \cdot 12342$
$12342$ is even: $= 2 \cdot 6171$, so far $2^2 \cdot 5 \cdot 6171$.
Digit sum of $6171$: $6+1+7+1 = 15$ (div by 3, not 9): $6171 = 3 \cdot 2057$.
Alternating sum of $2057$: $2 - 0 + 5 - 7 = 0$ (div by 11): $2057 = 11 \cdot 187$.
$187$: again $1 - 8 + 7 = 0$ (div by 11): $187 = 11 \cdot 17$.
\[123420 = 2^2 \cdot 3 \cdot 5 \cdot 11^2 \cdot 17\]Example 5-10: Is $97$ prime?
$\sqrt{97} \approx 9.8$. Primes $\leq 9$: $2, 3, 5, 7$. None divides 97. So 97 is prime.
Infinitely Many Primes
Theorem (Euclid): There are infinitely many primes.
Proof (by contradiction): Suppose there are only finitely many primes $p_1, p_2, \ldots, p_n$. Consider $P = p_1 p_2 \cdots p_n + 1$. No $p_i$ divides $P$ (dividing by any $p_i$ leaves remainder 1). So $P$ has no prime factor among our list — contradiction, since every integer $> 1$ has a prime factor.
Exercise 5-25: Write down the prime factorizations of all integers from 2 to 12.
Exercise 5-26: What is the prime factorization of 256?
Exercise 5-27: Factor $141$, $1441$, and $14441$.
5.7 Common and Uncommon Factors — GCD & LCM
Greatest Common Factor (GCF / GCD)
The greatest common factor (GCF) of two numbers is the largest positive integer that divides both.
Method: Factor both numbers into primes. For each prime, take the smaller exponent.
Notation: $(m, n)$ or $\gcd(m, n)$.
Two numbers whose GCF is 1 are called relatively prime.
Example 5-11: Find $\gcd(100, 1000)$.
$100 = 2^2 \cdot 5^2$, $\;1000 = 2^3 \cdot 5^3$.
Common factors: $2^2$ and $5^2$. So $\gcd = 2^2 \cdot 5^2 = 100$.
Least Common Multiple (LCM)
The least common multiple (LCM) is the smallest positive integer divisible by both numbers.
Method: For each prime, take the larger exponent.
Notation: $[m, n]$ or $\text{lcm}(m, n)$.
Example: $84 = 2^2 \cdot 3 \cdot 7$, $\;112 = 2^4 \cdot 7$.
$\gcd(84, 112) = 2^2 \cdot 7 = 28$, $\quad \text{lcm}(84, 112) = 2^4 \cdot 3 \cdot 7 = 336$.
Key identity:
\[\gcd(m,n) \cdot \text{lcm}(m,n) = m \cdot n\]This lets you find LCM from GCF (or vice versa) without full factorization.
Example 5-12: $\text{lcm}(100, 1000)$
$100 = 2^2 \cdot 5^2$, $1000 = 2^3 \cdot 5^3$. Take the larger powers: $2^3 \cdot 5^3 = 1000$.
Example 5-13: Find $\text{lcm}(12, 54, 42)$.
$12 = 2^2 \cdot 3$, $\;54 = 2 \cdot 3^3$, $\;42 = 2 \cdot 3 \cdot 7$.
Largest powers: $2^2, 3^3, 7$. LCM $= 4 \cdot 27 \cdot 7 = 756$.
Exercise 5-28: Find $\gcd(117, 165)$, $\gcd(102, 119)$, and $\gcd(96, 36)$.
Exercise 5-29: Prove that $\gcd(a, b) \leq a$, $\gcd(a, b) \leq b$, and $\gcd(a, b) \leq a - b$ (where $a > b$).
Exercise 5-30: Find $\text{lcm}(117, 165)$, $\text{lcm}(102, 119)$, and $\text{lcm}(96, 36)$.
Exercise 5-31: Verify that $(m,n)[m,n] = mn$ for each pair in Exercise 5-30.
Exercise 5-32: Prove $(m,n)[m,n] = mn$. Use it: if the GCF of two numbers is 8 and their product is 2880, find their LCM.
Exercise 5-33: Prove that $\gcd(\ell, m, n) \cdot \text{lcm}(\ell m, mn, n\ell) = \ell m n$ for positive integers $\ell, m, n$.
Exercises & Problems
End-of-Chapter Problems
Problem 87. Find the GCF of 36, 27, and 45.
Problem 88. How many multiples of 7 are there between 100 and 200?
Problem 89. Find the units digit of $19^{93}$.
Problem 90. Find the 1275th term of the series $1, 3, 5, \ldots, 15, 1, 3, 5, \ldots, 15, 1, \ldots$ (Mandelbrot #3)
Problem 91. Find the smallest positive integer which when divided by 10 leaves remainder 9, by 9 leaves remainder 8, by 8 leaves remainder 7, …, by 2 leaves remainder 1. (AHSME 1951)
Problem 92. Find digit $A$ if $12A3B$ is divisible by both 4 and 9, and $A \neq B$. (MATHCOUNTS 1986)
Problem 93. Find the units digit of $3^{1986} - 2^{1986}$. (MATHCOUNTS 1986)
Problem 94. In how many ways can $69 be paid exactly using only $5 and $2 bills? (MATHCOUNTS 1988)
Problem 95. Find the sum of all four-digit numbers of the form $44B8$ divisible by 2, 3, 4, 6, 8, and 9. (MATHCOUNTS 1988)
Problem 96. Markers placed in rows of 4 leave 2 over; rows of 5 leave 3 over; rows of 7 leave 5 over. What is the smallest possible number of markers? (MATHCOUNTS 1984)
Problem 97. When $n$ is divided by 5, the remainder is 1. What is the remainder when $3n$ is divided by 5? (MATHCOUNTS 1991)
Problem 98. A six-digit number is formed by repeating a three-digit number (e.g. $256{,}256$). What is the largest integer that divides all such numbers? (AHSME 1951)
Problem 99. A base-2 numeral has 15 digits, all ones. When tripled and written in base 2, how many digits does it have? (MATHCOUNTS 1986)
Problem 100. What is the largest base-10 number expressible as a 3-digit base-5 number? (MATHCOUNTS 1989)
Problem 101. How many natural numbers require 3 digits in base 12 but 4 digits in base 9? (MATHCOUNTS 1989)
Problem 102. Given $9^6 = 531{,}441$, represent $531{,}440$ in base 9. (MATHCOUNTS 1990)
Problem 103. Find the smallest positive integer $> 1$ that leaves remainder 1 when divided by every single-digit integer $> 1$. (Mandelbrot #3)
Problem 104. A store sold 72 decks of cards for $$a67.9b$. Find $a + b$. (MAΘ 1991)
Problem 105. For each of $n = 84$ and $n = 88$, find the smallest integer multiple of $n$ whose base-10 representation consists entirely of 6’s and 7’s. (USAMTS 1)
Problem 106. When $n$ is written in base $b$ it is the two-digit number $AB$ where $A = b - 2$ and $B = 2$. Find the representation of $n$ in base $(b - 1)$. (MAΘ 1991)
Problem 107. If $a \neq 1$ and $\sqrt[a]{10000} = 10^a$, find $a$. (MAΘ 1990)
Problem 108. Denote by $p_k$ the $k$th prime. Show that $p_1 p_2 \cdots p_n + 1$ cannot be a perfect square. (M&IQ 1992)
Problem 109. Prove that it is impossible for three consecutive perfect squares to sum to another perfect square. (Mandelbrot #2)