Mathematics Number Theory Syllabus

Number Theory syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Number Theory in Mathematics, not a summary of it.

1. 1

   Prime Numbers

   overview

   Examined as a single unit within Number Theory — no further topic split in the official outline.

2. 2

   Divisibility

   overview

   Examined as a single unit within Number Theory — no further topic split in the official outline.

3. 3

   Modular Arithmetic

   overview

   Examined as a single unit within Number Theory — no further topic split in the official outline.

4. 4

   Diophantine Equations

   overview

   Examined as a single unit within Number Theory — no further topic split in the official outline.

5. 5

   Congruences

   overview

   Examined as a single unit within Number Theory — no further topic split in the official outline.

6. 6

   Number Theoretic Functions

   overview

   Examined as a single unit within Number Theory — no further topic split in the official outline.

7. 7

   Quadratic Residues

   overview

   Examined as a single unit within Number Theory — no further topic split in the official outline.

8. 8

   Continued Fractions

   overview

   Examined as a single unit within Number Theory — no further topic split in the official outline.

9. 9

   Elliptic Curves

   overview

   Examined as a single unit within Number Theory — no further topic split in the official outline.

Number Theory flashcards for Mathematics

24 of 50 cards from the Number Theory deck — real questions with worked answers.

1. What is the Fundamental Theorem of Arithmetic?

   Every integer $n > 1$ can be written uniquely (up to ordering) as a product of primes: $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}$, where the $p_{i}$ are distinct primes and $a_{i} \geq 1$.

2. Define what it means for an integer $a$ to divide an integer $b$.

   $a \mid b$ means there exists an integer $k$ such that $b = a \cdot k$ (with $a \neq 0$). We say $a$ is a divisor of $b$ and $b$ is a multiple of $a$.

3. What is a prime number?

   An integer $p > 1$ whose only positive divisors are $1$ and $p$ itself. The smallest prime is $2$, the only even prime.

4. State the Division Algorithm for integers.

   For integers $a$ and $b$ with $b > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = bq + r$ where $0 \leq r < b$.

5. Define the greatest common divisor $\gcd(a,b)$.

   The largest positive integer $d$ such that $d \mid a$ and $d \mid b$. Equivalently, it is the smallest positive integer expressible as $ax + by$ for integers $x, y$.

6. What is Bézout's Identity?

   For integers $a$ and $b$ (not both zero), there exist integers $x$ and $y$ such that $ax + by = \gcd(a,b)$.

7. How are $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$ related?

   $$\gcd(a,b) \cdot \operatorname{lcm}(a,b) = |a \cdot b|$$ so $\operatorname{lcm}(a,b) = \dfrac{|ab|}{\gcd(a,b)}$.

8. Describe the Euclidean Algorithm for computing $\gcd(a,b)$.

   Repeatedly replace $(a,b)$ with $(b, a \bmod b)$ until the remainder is $0$. The last nonzero remainder is $\gcd(a,b)$. It relies on $\gcd(a,b) = \gcd(b, a \bmod b)$.

9. What does it mean for $a$ to be congruent to $b$ modulo $m$?

   $a \equiv b \pmod{m}$ means $m \mid (a - b)$, i.e. $a$ and $b$ leave the same remainder when divided by $m$.

10. When are two integers said to be coprime (relatively prime)?

    When $\gcd(a,b) = 1$, i.e. they share no common prime factor.

11. State Fermat's Little Theorem.

    If $p$ is prime and $p \nmid a$, then $$a^{p-1} \equiv 1 \pmod{p}.$$ Equivalently, $a^{p} \equiv a \pmod{p}$ for all integers $a$.

12. State Euler's Theorem.

    If $\gcd(a, n) = 1$, then $$a^{\varphi(n)} \equiv 1 \pmod{n},$$ where $\varphi$ is Euler's totient function.

13. Define Euler's totient function $\varphi(n)$.

    $\varphi(n)$ counts the positive integers up to $n$ that are coprime to $n$. For example, $\varphi(9) = 6$ since $1,2,4,5,7,8$ are coprime to $9$.

14. Give the formula for $\varphi(n)$ in terms of the prime factorization of $n$.

    If $n = p_{1}^{a_{1}} \cdots p_{k}^{a_{k}}$, then $$\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_{i}}\right).$$

15. What is $\varphi(p)$ for a prime $p$, and $\varphi(p^{k})$ for a prime power?

    $\varphi(p) = p - 1$ and $\varphi(p^{k}) = p^{k} - p^{k-1} = p^{k-1}(p-1)$.

16. State Wilson's Theorem.

    An integer $p > 1$ is prime if and only if $$(p-1)! \equiv -1 \pmod{p}.$$

17. State the Chinese Remainder Theorem (CRT).

    If $m_{1}, m_{2}, \ldots, m_{k}$ are pairwise coprime, then the system $x \equiv a_{i} \pmod{m_{i}}$ has a unique solution modulo $M = m_{1} m_{2} \cdots m_{k}$.

18. When does the linear congruence $ax \equiv b \pmod{m}$ have a solution?

    It has a solution if and only if $\gcd(a,m) \mid b$. If so, there are exactly $\gcd(a,m)$ solutions modulo $m$.

19. Define the multiplicative inverse of $a$ modulo $m$ and state when it exists.

    An integer $a^{-1}$ with $a \cdot a^{-1} \equiv 1 \pmod{m}$. It exists if and only if $\gcd(a,m) = 1$, and can be found via the Extended Euclidean Algorithm.

20. How do you compute a modular inverse using the Extended Euclidean Algorithm?

    Find integers $x, y$ with $ax + my = \gcd(a,m) = 1$. Then $x \bmod m$ is the inverse $a^{-1} \pmod{m}$, since $ax \equiv 1 \pmod{m}$.

21. State the formula for the number of positive divisors of $n$.

    If $n = p_{1}^{a_{1}} \cdots p_{k}^{a_{k}}$, then the divisor count is $$d(n) = \prod_{i=1}^{k} (a_{i} + 1).$$

22. State the formula for the sum of positive divisors $\sigma(n)$.

    If $n = p_{1}^{a_{1}} \cdots p_{k}^{a_{k}}$, then $$\sigma(n) = \prod_{i=1}^{k} \frac{p_{i}^{a_{i}+1} - 1}{p_{i} - 1}.$$

23. What is a perfect number?

    A positive integer $n$ equal to the sum of its proper divisors, i.e. $\sigma(n) = 2n$. Examples: $6 = 1+2+3$ and $28 = 1+2+4+7+14$.

24. What is a Mersenne prime?

    A prime of the form $M_{p} = 2^{p} - 1$, where $p$ itself must be prime. Examples: $3, 7, 31, 127$ (for $p = 2,3,5,7$).

See more Number Theory flashcards →

Planning Number Theory for Mathematics

Number Theory (Mathematics) FAQ