Number Theory Syllabus

State the basic arithmetic properties of congruences (addition and multiplication).

If $a \equiv b \pmod m$ and $c \equiv d \pmod m$, then $a+c \equiv b+d \pmod m$, $a-c \equiv b-d \pmod m$, and $ac \equiv bd \pmod m$. Also $a^n \equiv b^n \pmod m$ for $n \geq 1$.

State the cancellation rule for congruences.

If $ac \equiv bc \pmod m$, then $a \equiv b \pmod{\frac{m}{\gcd(c,m)}}$. In particular, if $\gcd(c,m)=1$ then $a \equiv b \pmod m$.

State Fermat's Little Theorem.

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

State Euler's theorem (generalization of Fermat's Little Theorem).

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

State Wilson's theorem.

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

State the Chinese Remainder Theorem (CRT).

If $m_1,\dots,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$.

Give the CRT construction formula for two congruences $x\equiv a_1 \pmod{m_1}$, $x\equiv a_2 \pmod{m_2}$.

With $M=m_1m_2$, $M_i=M/m_i$, and $y_i \equiv M_i^{-1}\pmod{m_i}$, the solution is $$x \equiv a_1 M_1 y_1 + a_2 M_2 y_2 \pmod{M}.$$

Solve using CRT: $x \equiv 2 \pmod 3$ and $x \equiv 3 \pmod 5$.

Numbers $\equiv 3 \pmod 5$ are $3,8,13,\dots$; the first also $\equiv 2 \pmod 3$ is $8$. So $$x \equiv 8 \pmod{15}.$$

When does the linear congruence $ax \equiv b \pmod m$ have a solution, and how many?

Let $d=\gcd(a,m)$. It has a solution iff $d \mid b$. When solvable, there are exactly $d$ solutions modulo $m$.

How do you solve $ax \equiv b \pmod m$ when $\gcd(a,m)=1$?

Multiply both sides by the modular inverse $a^{-1}$: $x \equiv a^{-1} b \pmod m$. The inverse $a^{-1}$ is found via the Extended Euclidean Algorithm.

What is a modular multiplicative inverse of $a$ modulo $m$, and when does it exist?

It is an integer $a^{-1}$ with $a\,a^{-1} \equiv 1 \pmod m$. It exists if and only if $\gcd(a,m)=1$.

How is a system of linear congruences with non-coprime moduli handled?

A pair $x\equiv a_1\pmod{m_1}$, $x\equiv a_2\pmod{m_2}$ is consistent iff $\gcd(m_1,m_2) \mid (a_1-a_2)$; the combined solution is unique modulo $\operatorname{lcm}(m_1,m_2)$. Solve pairwise, merging step by step.

Name two common applications of congruences.

Examples: computing check digits (ISBN, UPC), hashing, cyclic scheduling / calendar (day-of-week) calculations, RSA and other public-key cryptography, and fast modular exponentiation.

How does modular arithmetic give a check-digit like ISBN-10?

For ISBN-10 digits $d_1,\dots,d_{10}$, validity requires $$\sum_{i=1}^{10} i\,d_i \equiv 0 \pmod{11},$$ where $d_{10}$ may be the symbol $X$ representing $10$.

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

$\varphi(n)$ counts the integers in $\{1,2,\dots,n\}$ that are relatively prime to $n$ (i.e. $\gcd(k,n)=1$).

Give the formula for $\varphi(n)$ from 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).$$

What is $\varphi(p)$ and $\varphi(p^k)$ for a prime $p$?

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

Is Euler's totient function multiplicative? State the property.

Yes, $\varphi$ is multiplicative: if $\gcd(m,n)=1$ then $\varphi(mn)=\varphi(m)\varphi(n)$.

State the divisor-sum identity for Euler's totient: $\sum_{d\mid n}\varphi(d)=?$

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

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

$\mu(1)=1$; $\mu(n)=(-1)^k$ if $n$ is a product of $k$ distinct primes (squarefree); and $\mu(n)=0$ if $n$ is divisible by the square of any prime.

State the key summation property $\sum_{d\mid n}\mu(d)$.

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

State the Möbius inversion formula.

If $f(n)=\sum_{d\mid n} g(d)$ for all $n$, then $$g(n)=\sum_{d\mid n}\mu(d)\,f\!\left(\frac{n}{d}\right).$$

Define the divisor function $d(n)$ (also written $\tau(n)$).

$d(n)$ is the number of positive divisors of $n$: $d(n)=\sum_{d\mid n}1$.

Give the formula for $d(n)$ in terms of the prime factorization.

If $n=p_1^{a_1}\cdots p_k^{a_k}$, then $$d(n)=(a_1+1)(a_2+1)\cdots(a_k+1).$$

Define the sigma function $\sigma(n)$ (sum of divisors).

$\sigma(n)=\sum_{d\mid n} d$ is the sum of all positive divisors of $n$.

Give the formula for $\sigma(n)$ from the prime factorization.

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

Define a perfect number and give the two smallest examples.

A perfect number equals the sum of its proper divisors, i.e. $\sigma(n)=2n$. The two smallest are $6$ ($=1+2+3$) and $28$ ($=1+2+4+7+14$).

State the Euclid–Euler theorem on even perfect numbers.

An even number is perfect iff it has the form $$n = 2^{p-1}\left(2^p-1\right)$$ where $2^p-1$ is a Mersenne prime. (No odd perfect number is known.)

Define amicable numbers and give the classic smallest pair.

Two distinct numbers $m,n$ are amicable if each equals the sum of the other's proper divisors: $s(m)=n$ and $s(n)=m$, where $s(k)=\sigma(k)-k$. The smallest pair is $(220, 284)$.

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

It has integer solutions iff $\gcd(a,b) \mid c$. If so, there are infinitely many solutions.

Give the general solution of $ax+by=c$ once one solution $(x_0,y_0)$ is known.

With $d=\gcd(a,b)$, all solutions are $$x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t,\qquad t\in\mathbb{Z}.$$

What is Pell's equation, and what is its trivial solution?

Pell's equation is $$x^2 - D y^2 = 1,$$ where $D$ is a positive non-square integer. The trivial solution is $(x,y)=(1,0)$.

How are all solutions of Pell's equation generated from the fundamental solution?

If $(x_1,y_1)$ is the fundamental (smallest nontrivial) solution, then all positive solutions $(x_n,y_n)$ come from $$x_n + y_n\sqrt{D} = \left(x_1 + y_1\sqrt{D}\right)^{n}.$$