Congruence Structures and Arithmetic Functions

While basic number theory introduces the division algorithm and prime numbers, advanced number theory focuses on the underlying algebraic structures of congruences and the analytic properties of arithmetic functions. In this lesson, we explore the set of integers modulo $n$ as a ring and the multiplicative groups that emerge from it.

The Ring of Integers Modulo $n$

The set of congruence classes modulo $n$, denoted $\mathbb{Z}/n\mathbb{Z}$ or ${\mathbb{Z}}_n$, forms a commutative ring under addition and multiplication.

• Addition: $[a{]}_n+[b{]}_n=[a+b{]}_n$
• Multiplication: $[a{]}_n\cdot [b{]}_n=[ab{]}_n$

The ring $\mathbb{Z}/n\mathbb{Z}$ is a field if and only if $n$ is a prime number $p$. In this case, every non-zero element has a multiplicative inverse, and we denote the field as ${\mathbb{F}}_p$ or $GF(p)$.

The Multiplicative Group $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$

The set of elements in $\mathbb{Z}/n\mathbb{Z}$ that are relatively prime to $n$ forms a group under multiplication, denoted $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ or $U(n)$. The order of this group is given by Euler’s totient function $\varphi (n)$.

Primitive Roots

An element $g\in (\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ is a primitive root modulo $n$ if the order of $g$ is exactly $\varphi (n)$. This means $g$ generates the entire multiplicative group: $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }=\{g^1,g^2,\dots ,g^{\varphi (n)}\}$ Gauss proved that $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ has a primitive root if and only if $n=2,4,p^k,\text{ or }2p^k$ for an odd prime $p$.

Discrete Logarithms

If $g$ is a primitive root modulo $p$, then for any $a\in (\mathbb{Z}/p\mathbb{Z}{)}^{\times }$, there exists a unique $x\in \{0,1,\dots ,p-2\}$ such that $g^x\equiv a(\mathrm{mod}p)$. The value $x$ is called the discrete logarithm of $a$ to the base $g$. Unlike the logarithm in $\mathbb{R}$, the discrete logarithm is computationally difficult to compute, forming the basis for the Diffie-Hellman key exchange.

Arithmetic Functions and Dirichlet Convolution

An arithmetic function is a function $f:{\mathbb{Z}}^{+}\to \mathbb{C}$.

Multiplicative Functions

A function $f$ is multiplicative if $f(mn)=f(m)f(n)$ whenever $\gcd (m,n)=1$. Examples:

• $\varphi (n)$: Euler’s totient function.
• $\mu (n)$: The Mobius function.
• ${\sigma }_k(n)$: The sum of the $k$-th powers of the divisors of $n$.

Dirichlet Convolution

The Dirichlet convolution of two arithmetic functions $f$ and $g$ is defined as: $(f\ast g)(n)={\sum }_{d|n}f(d)g(n/d)$ This operation is associative, commutative, and has an identity function $ϵ(n)$ (where $ϵ(1)=1$ and $ϵ(n)=0$ for $n>1$).

Mobius Inversion Formula

If $g(n)={\sum }_{d|n}f(d)$, then $f(n)={\sum }_{d|n}g(d)\mu (n/d)$. In terms of convolution, if $g=f\ast 1$ (where $1(n)=1$ for all $n$), then $f=g\ast \mu$. This allows us to recover a function from its summatory function.

Perfect Numbers and Mersenne Primes

A positive integer $n$ is perfect if the sum of its proper divisors equals $n$, or ${\sigma }_1(n)=2n$.

• Euclid-Euler Theorem: An even number $n$ is perfect if and only if it is of the form $2^{p-1}(2^p-1)$, where $2^p-1$ is a Mersenne prime.
• Open Problem: Does there exist an odd perfect number? To date, none have been found, and it is known that none exist below $10^{1500}$.

Quadratic Residues and the Jacobi Symbol

While the Legendre symbol $\left(\frac{a}{p}\right)$ is defined only for prime $p$, the Jacobi Symbol $\left(\frac{a}{n}\right)$ generalizes it to any odd composite $n=p_1^{e_1}\dots p_k^{e_k}$: $\left(\frac{a}{n}\right)={\left(\frac{a}{p_1}\right)}^{e_1}\dots {\left(\frac{a}{p_k}\right)}^{e_k}$ Note that $\left(\frac{a}{n}\right)=1$ does not guarantee that $a$ is a quadratic residue modulo $n$, but $\left(\frac{a}{n}\right)=-1$ does guarantee it is a non-residue.

Order and Structure: A Comparative View

Python: Primitive Roots and Order

import math

def get_order(a, n):
    if math.gcd(a, n) != 1: return None
    for k in range(1, n):
        if pow(a, k, n) == 1:
            return k
    return None

def is_primitive_root(g, n):
    phi = sum(1 for i in range(1, n) if math.gcd(i, n) == 1)
    return get_order(g, n) == phi

Exercise