Number Theory Reference
Number Theory and Modular Arithmetic
Elementary number theory studies integer divisibility and remainders, including arithmetic that repeats in cycles.
Solved Examples
Jump directly to a worked example by type.
Fact Table
| Idea | Meaning | Use or Check |
|---|---|---|
| Divisibility | $a\mid b$ means $b=ak$ for some integer $k$. | The divisor is not zero. |
| Prime | An integer greater than 1 with exactly two positive divisors. | The integer 1 is not prime. |
| Greatest common divisor | $\gcd(a,b)$ is the largest positive integer dividing both. | The Euclidean algorithm uses repeated remainders. |
| Congruence | $a\equiv b\pmod m$ means $a$ and $b$ have the same remainder modulo $m$. | Congruences can be added and multiplied. |
Content Formulas
Euclidean Step
$$a=bq+r\quad\Longrightarrow\quad\gcd(a,b)=\gcd(b,r)$$
Congruence
$$a\equiv b\pmod m\quad\Longleftrightarrow\quad m\mid(a-b)$$
Prime Factorization
$$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$$
In modular arithmetic, reduce a number to its remainder class before or after addition and multiplication. Keep the modulus attached to the congruence.
Classic Examples
Find a Greatest Common Divisor
Find $\gcd(252,105)$ using the Euclidean algorithm.
Solution Steps
- Divide and record the remainder.
- Repeat with the previous divisor and remainder.
- Stop when the remainder is zero.
$$252=2(105)+42$$
$$105=2(42)+21$$
$$42=2(21)+0$$
$$\gcd(252,105)=21$$
Use Clock Arithmetic
A 12-hour clock shows 11:00. What time will it show 17 hours later?
Solution Steps
- Add the hours.
- Reduce the total modulo 12, keeping 12 in place of remainder 0.
$$11+17=28$$
$$28\equiv4\pmod{12}$$
The clock will show 4:00.
Solve a Modular Equation
Solve $3x\equiv1\pmod 7$.
Solution Steps
- Find a multiplier that turns 3 into a number congruent to 1 modulo 7.
- Check the proposed residue.
$$3(5)=15\equiv1\pmod 7$$
$$x\equiv5\pmod 7$$