Elementary and Analytic Number Theory

Number theory, historically termed “Higher Arithmetic,” serves as the cornerstone of mathematical abstraction, exploring the properties of the set of integers $\mathbb{Z}$. While its foundations are elementary, its deep connections to complex analysis, abstract algebra, and cryptography make it one of the most vibrant fields of modern mathematics.

Divisibility and the Euclidean Algorithm

The core of number theory begins with the concept of divisibility. For $a,b\in \mathbb{Z}$, we say $b$ divides $a$ (written $b\mid a$) if there exists an integer $k$ such that $a=bk$.

The Division Algorithm

Technically a theorem rather than an algorithm, it states that for any $a\in \mathbb{Z}$ and $b\in {\mathbb{Z}}^{+}$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that: $a=bq+r,0\le r<b$

Greatest Common Divisor (GCD)

The GCD of $a$ and $b$, denoted $\gcd (a,b)$, is the largest positive integer $d$ such that $d\mid a$ and $d\mid b$. Two numbers are coprime or relatively prime if $\gcd (a,b)=1$.

The Euclidean Algorithm

To compute $\gcd (a,b)$, we exploit the invariant $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$.

1. Let $r_0=a$ and $r_1=b$.
2. Compute $r_{i-1}=q_i{r}_i+r_{i+1}$ until $r_{n+1}=r_{n-1}\mathrm{mod}{r}_n=0$.
3. The last non-zero remainder $r_n$ is the $\gcd (a,b)$.

Bézout’s Identity and the Extended Euclidean Algorithm

For any $a,b\in \mathbb{Z}$, there exist $x,y\in \mathbb{Z}$ such that: $ax+by=\gcd (a,b)$ This is fundamental for finding modular inverses. If $\gcd (a,n)=1$, then $ax\equiv 1(\mathrm{mod}n)$ has a solution, where $x$ is the multiplicative inverse of $a$ modulo $n$.

Primes and the Fundamental Theorem of Arithmetic

A prime number is an integer $p>1$ whose only positive divisors are $1$ and $p$. If $n>1$ is not prime, it is composite.

The Fundamental Theorem of Arithmetic

Every integer $n>1$ can be uniquely represented as a product of prime numbers: $n=p_1^{a_1}{p}_2^{a_2}\dots p_k^{a_k}$ where $p_1<p_2<\cdots <p_k$ are primes and $a_i\in {\mathbb{Z}}^{+}$.

Distribution of Primes

Euclid proved that there are infinitely many primes by contradiction: if there were a finite set $\{p_1,\dots ,p_n\}$, then $Q=(p_1\dots p_n)+1$ would have a prime factor not in the set. The Prime Number Theorem (PNT) provides the asymptotic density: $\pi (x)\sim \frac{x}{\ln x}$ where $\pi (x)$ is the prime-counting function.

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” when reaching a certain value, the modulus $n$.

Congruence Relation

We say $a\equiv b(\mathrm{mod}n)$ if $n\mid (a-b)$. This is an equivalence relation that partitions $\mathbb{Z}$ into $n$ equivalence classes, often denoted $\mathbb{Z}/n\mathbb{Z}$.

Fermat’s Little Theorem

If $p$ is prime and $a$ is an integer such that $p\nmid a$, then: $a^{p-1}\equiv 1(\mathrm{mod}p)$ Generalizing this, we use the Euler Totient Function $\varphi (n)$, which counts the integers $k$ such that $1\le k\le n$ and $\gcd (k,n)=1$.

Euler’s Theorem

For any $a,n$ such that $\gcd (a,n)=1$: $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

Chinese Remainder Theorem (CRT)

If $m_1,m_2,\dots ,m_k$ are pairwise relatively prime, then the system of simultaneous congruences: $x\equiv a_i(\mathrm{mod}{m}_i)$ has a unique solution modulo $M=m_1{m}_2\dots m_k$.

Multiplicative Functions and Mobius Inversion

A function $f:{\mathbb{Z}}^{+}\to \mathbb{C}$ is multiplicative if $f(mn)=f(m)f(n)$ for all $m,n$ with $\gcd (m,n)=1$.

1. Sum of Divisors: $\sigma (n)={\sum }_{d|n}d$.
2. Number of Divisors: $\tau (n)={\sum }_{d|n}1$.
3. Mobius Function: $\mu (n)$, used for the Mobius Inversion Formula.
   • $\mu (n)=1$ if $n=1$.
   • $\mu (n)=(-1{)}^k$ if $n$ is the product of $k$ distinct primes.
   • $\mu (n)=0$ if $n$ has a squared prime factor.

Quadratic Reciprocity

One of the deepest results in elementary number theory is the Law of Quadratic Reciprocity. It describes whether a prime $p$ is a quadratic residue modulo another prime $q$. The Legendre Symbol $\left(\frac{a}{p}\right)$ is defined as:

• $1$ if $a$ is a quadratic residue modulo $p$ ($x^2\equiv a(\mathrm{mod}p)$ has a solution).
• $-1$ if $a$ is a quadratic non-residue.
• $0$ if $p\mid a$.

The law states for odd primes $p,q$: $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}$

Cryptographic Applications: RSA

The RSA algorithm is the most ubiquitous application of number theory in computing. It relies on the computational difficulty of the Integer Factorization Problem.

RSA Key Generation

1. Choose two large distinct primes $p$ and $q$.
2. Compute $n=pq$ and $\varphi (n)=(p-1)(q-1)$.
3. Choose an integer $e$ such that $1<e<\varphi (n)$ and $\gcd (e,\varphi (n))=1$ (usually $e=65537$).
4. Compute $d$ as the modular multiplicative inverse of $e(\mathrm{mod}\varphi (n))$ using the Extended Euclidean Algorithm: $de\equiv 1(\mathrm{mod}\varphi (n))$.
5. Public Key is $(n,e)$; Private Key is $(n,d)$.

Encryption and Decryption

• Encryption: For message $m$, $c=m^e(\mathrm{mod}n)$.
• Decryption: $m=c^d(\mathrm{mod}n)$. The correctness follows from Euler’s Theorem, ensuring $(m^e{)}^d=m^{ed}=m^{k\varphi (n)+1}\equiv m(\mathrm{mod}n)$.

Primality Testing

In cryptography, we must find large primes. Deterministic tests like the Sieve of Eratosthenes are $O(n)$ and too slow.

• Miller-Rabin Test: A probabilistic test based on strong pseudoprimes and Fermat’s Little Theorem. It is very efficient and widely used.
• AKS Test: The first deterministic polynomial-time algorithm to determine if a number is prime, discovered in 2002.

Computational Perspective: Extended Euclidean Algorithm

def extended_gcd(a, b):
    \"\"\"
    Returns (gcd, x, y) such that ax + by = gcd.
    This implements Bezout's Identity.
    \"\"\"
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

# Finding the modular inverse of a mod n
def mod_inverse(a, n):
    gcd, x, y = extended_gcd(a, n)
    if gcd != 1:
        raise ValueError("Modular inverse does not exist")
    else:
        return x % n

Advanced Topics: The Riemann Zeta Function

The distribution of primes is inextricably linked to the Riemann Zeta Function: $\zeta (s)={\sum }_{n=1}^{\infty }\frac{1}{n^s}={\prod }_{p\text{ prime}}\frac{1}{1-p^{-s}}$ The Riemann Hypothesis, which states all non-trivial zeros of $\zeta (s)$ have real part $1/2$, remains the most significant unsolved problem in mathematics, directly impacting our refined understanding of prime distribution.

Exercise