Mathematics Number Theory Syllabus

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).$$

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}.$$

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$.

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$).

State the Euclid–Euler theorem connecting perfect numbers and Mersenne primes.

An even number is perfect if and only if it has the form $2^{p-1}(2^{p}-1)$ where $2^{p}-1$ is a (Mersenne) prime.

How many primes are there, and how is this proven?

There are infinitely many primes. Euclid's proof: if $p_{1}, \ldots, p_{k}$ were all primes, then $N = p_{1}\cdots p_{k} + 1$ is divisible by none of them, so it has a new prime factor — a contradiction.

State the Prime Number Theorem.

The prime-counting function $\pi(x)$ satisfies $$\pi(x) \sim \frac{x}{\ln x} \quad \text{as } x \to \infty,$$ meaning $\lim_{x\to\infty} \frac{\pi(x)\ln x}{x} = 1$.

What is the Sieve of Eratosthenes used for?

Finding all primes up to $n$. List $2$ to $n$; repeatedly take the next unmarked number as prime and cross out all its multiples. Remaining unmarked numbers are prime.

When testing whether $n$ is prime by trial division, up to what bound must you check divisors?

Only up to $\sqrt{n}$. If $n$ has no prime factor $\leq \sqrt{n}$, then $n$ is prime, since any factor pair $n = ab$ has at least one factor $\leq \sqrt{n}$.

Define a quadratic residue modulo $p$.

An integer $a$ with $\gcd(a,p)=1$ is a quadratic residue mod $p$ if $x^{2} \equiv a \pmod{p}$ has a solution; otherwise it is a quadratic non-residue.

Define the Legendre symbol $\left(\frac{a}{p}\right)$.

For odd prime $p$: $\left(\frac{a}{p}\right) = 0$ if $p \mid a$; $= 1$ if $a$ is a quadratic residue mod $p$; $= -1$ if $a$ is a non-residue.

State Euler's Criterion for quadratic residues.

For an odd prime $p$ and $p \nmid a$: $$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}.$$

State the Law of Quadratic Reciprocity.

For distinct odd primes $p, q$: $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.$$

What is the divisibility rule for 3 (and 9)?

An integer is divisible by $3$ (resp. $9$) if and only if the sum of its decimal digits is divisible by $3$ (resp. $9$). This follows from $10 \equiv 1 \pmod{9}$.

What is the divisibility rule for 11?

An integer is divisible by $11$ if and only if the alternating sum of its digits is divisible by $11$, since $10 \equiv -1 \pmod{11}$.

Define a multiplicative function in number theory.

An arithmetic function $f$ with $f(1)=1$ such that $f(mn) = f(m)f(n)$ whenever $\gcd(m,n)=1$. Examples: $\varphi$, $d(n)$, $\sigma(n)$, the Möbius function $\mu$.

Define the Möbius function $\mu(n)$.

$\mu(1)=1$; $\mu(n)=(-1)^{k}$ if $n$ is a product of $k$ distinct primes (squarefree); $\mu(n)=0$ if $n$ has a squared prime factor.

State the divisor-sum identity for the Möbius function.

$$\sum_{d \mid n} \mu(d) = \begin{cases} 1 & n = 1 \\ 0 & n > 1 \end{cases}$$

State the divisor-sum identity for Euler's totient.

$$\sum_{d \mid n} \varphi(d) = n.$$

What is the order of an element $a$ modulo $n$?

The smallest positive integer $k$ such that $a^{k} \equiv 1 \pmod{n}$ (requires $\gcd(a,n)=1$). The order always divides $\varphi(n)$.

What is a primitive root modulo $n$?

An integer $g$ with $\gcd(g,n)=1$ whose order modulo $n$ equals $\varphi(n)$; its powers generate all units mod $n$. Primitive roots exist exactly for $n = 1,2,4,p^{k},2p^{k}$ ($p$ odd prime).

What is a Diophantine equation?

A polynomial equation in which only integer (or rational) solutions are sought. Example: the linear Diophantine equation $ax + by = c$.

When does the linear Diophantine equation $ax + by = c$ have integer solutions?

It has solutions if and only if $\gcd(a,b) \mid c$. If $(x_{0}, y_{0})$ is one solution, all solutions are $x = x_{0} + \frac{b}{d}t$, $y = y_{0} - \frac{a}{d}t$ with $d=\gcd(a,b)$, $t \in \mathbb{Z}$.

What characterizes a Pythagorean triple, and what is the primitive parametrization?

Positive integers with $a^{2}+b^{2}=c^{2}$. Primitive triples are $a=m^{2}-n^{2}$, $b=2mn$, $c=m^{2}+n^{2}$ with $m>n>0$, $\gcd(m,n)=1$, and $m,n$ of opposite parity.

State Fermat's Last Theorem.

For any integer $n > 2$, the equation $$x^{n} + y^{n} = z^{n}$$ has no solution in positive integers $x, y, z$. Proven by Andrew Wiles (1994).

What is the difference between a composite number and a prime?

A prime $p>1$ has exactly two positive divisors ($1$ and $p$). A composite number $n>1$ has at least three positive divisors, i.e. a divisor other than $1$ and $n$. Note: $1$ is neither prime nor composite.

How does fast modular exponentiation (square-and-multiply) compute $a^{e} \bmod m$?

Write $e$ in binary; repeatedly square $a$ modulo $m$, and multiply into the result for each binary $1$ in $e$. This runs in $O(\log e)$ multiplications instead of $e$.

What is the contrapositive use of Fermat's Little Theorem in primality testing?

If $a^{n-1} \not\equiv 1 \pmod{n}$ for some $a$ with $\gcd(a,n)=1$, then $n$ is composite (a Fermat witness). The converse fails: Carmichael numbers pass the test for all coprime $a$ yet are composite.

Define a Carmichael number.

A composite number $n$ such that $a^{n-1} \equiv 1 \pmod{n}$ for every integer $a$ coprime to $n$. The smallest is $561 = 3 \cdot 11 \cdot 17$.

Compare quadratic residues vs. non-residues modulo an odd prime $p$: how many of each are there?

Among the $p-1$ nonzero residues mod $p$, exactly $\frac{p-1}{2}$ are quadratic residues and $\frac{p-1}{2}$ are non-residues. The product of two residues or two non-residues is a residue; residue times non-residue is a non-residue.