NTIC Notation

Appendix C Notation

This is a quick guide to possibly unfamiliar notation. Page numbers or references usually refer to the first appearance of a notation with that meaning, occasionally to a definition.

Symbol	Description	Location
$\mathbb{Z}$	(ring of) integers	Definition 1.0.1
$\mathbb{N}$	counting numbers (starting at zero)	Definition 1.0.1
$a\mid b$	$a$ is a divisor of $b$	Definition 1.2.5
$\gcd(a,b)$	greatest common divisor of $a$ and $b$	Definition 2.2.1
$\lfloor x\rfloor$	greatest integer (floor) function	Definition 3.3.3
$a \equiv b \text{ (mod }n)$	$a$ is congruent to $b$ modulo $n$	Definition 4.1.1
$[a]$	the equivalence class of $a$ modulo some fixed $n$	Definition 4.4.1
$a^{-1}$	multiplicative inverse of a number modulo some fixed $n$	Definition 5.3.4
$\prod_{i=1}^n p_i$	product of unspecified, possible identical, primes	Theorem 6.3.2
$\prod p$	short form for product of primes	Example 6.3.3
$\prod q$	alternate short form for product of primes	Example 6.3.3
$\prod_{i=1}^n p_i^{e_i}$	product of unspecified distinct prime power	Example 6.3.4
$\prod p^e$	short form for product of prime powers	Example 6.3.4
$p^k\parallel n$	for $p$ prime, $p^k\mid n$ but $p^{k+1}$ does not divide $n$	Definition 6.4.5
$n!$	$n$ factorial	Definition 6.4.6
$\mathbb{Z}_n$	(ring of) integers modulo $n$	Definition 8.1.1
$A\setminus \{a\}$	the set of all elements in $A$ except $a\in A$	Example 8.3.4
$\|G\|$	order of a group $G$	Definition 8.3.8
$\|x\|$	order of a group element $x\in G$	Definition 8.3.10
$U_n$	group of units modulo $n$	Definition 9.1.2
$\phi(n)$	order of the group of units of $n$ (Euler function)	Definition 9.2.1
$\varphi(n)$	alternate notation for Euler $\phi$ function	Definition 9.2.1
$F_n$	Fermat number $2^{2^n}+1$	Definition 12.1.1
$M_n$	Mersenne number $2^n-1$	Definition 12.1.6
$r_2(n)$	number of different ways to write $n$ as a sum of two squares	Exercise 13.7.7
$\mathbb{Z}[i]$	Gaussian integers $\{a+bi\mid a,b\in\mathbb{Z}\}$	Definition 14.1.2
$\mathbb{C}$	complex numbers	Definition 14.1.2
$r_k(n)$	number of different ways to write $n$ as a sum of $k$ perfect squares	Example 14.2.3
$QR$	abbreviation for ‘quadratic residue’	Definition 16.3.1
$Q_p$	group of quadratic residues of $p$	Definition 16.4.2
$\left(\frac{a}{p}\right)$	Legendre symbol, for $p$ an odd prime	Definition 16.6.1
$aE$	multiples of positive even numbers less than $p$ by $a$	Definition 17.2.2
$\overline{aE}$	set of nonnegative remainders of elements of $aE$ modulo $p$	Definition 17.2.2
$r_{a,e}$	remainder modulo $p$ of the element $ae$ of $aE$	Definition 17.2.2
$\left(\frac{a}{n}\right)$	Jacobi symbol, $n$ odd	Definition 17.4.9
$R$	sum $\sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{qe}{p}\right\rfloor$ in proof of quadratic reciprocity	Paragraph
$\mu$	sum $\sum_{f=1}^{(p-1)/2}\left\lfloor\frac{qf}{p}\right\rfloor$ in proof of quadratic reciprocity	Paragraph
$r(n)$	alternate notation for $r_2(n)$	Definition 18.2.1
$\sigma_k(n)$	sum of $k$ th powers of divisors of $n$	Definition 19.1.1
$\tau(n)$	number of (positive) divisors of $n$	Remark 19.1.2
$\sigma(n)$	sum of (positive) divisors of $n$	Remark 19.1.2
$u(n)$	unit function	Definition 19.2.9
$N(n)$	identity function	Definition 19.2.9
$\sigma^{-1}(n)$	abundancy index of $n$	Fact 19.4.11
$O(g(x))$	‘Big Oh’ notation that a function is less in absolute value than $Cg(x)\text{,}$ for some constant $C$	Definition 20.1.2
$\log(n)$	natural (base $e$ ) logarithm	Definition 20.3.3
$\gamma$	Euler-Mascheroni gamma constant, limit of difference between the harmonic series and natural logarithm	Definition 20.3.10
$\Gamma$	Gamma function factorial extension	Remark 20.3.11
$\pi(x)$	prime counting function	Definition 21.0.1
$\phi(n,a)$	number of integers coprime to first $a$ primes	Definition 21.1.7
$p_a$	the $a$ th prime	Definition 21.1.7
$Li(x)$	logarithmic integral $\int_2^x \frac{dt}{\log(t)}$	Definition 21.2.2
$\Theta(x)$	Chebyshev theta function	Definition 21.4.3
$a(n)$	prime number indicator function	Definition 21.4.7
$p\#$	primorial (product of primes up to $p$ )	Definition 22.2.7
$C_2$	twin prime constant	Remark 22.3.6
$\mu(n)$	Moebius function of $n$	Definition 23.1.1
$f \star g$	Dirichlet product of arithmetic functions $f$ and $g$	Definition 23.2.3
$I(n)$	Dirichlet product identity function	Definition 23.3.1
$\omega(n)$	number of unique prime divisors of $n$	Definition 23.3.3
$\nu(n)$	alternate notation for $\omega(n)$	Definition 23.3.3
$\lambda(n)$	Liouville's function	Definition 23.3.4
$\zeta(s)$	Riemann zeta function	Definition 24.2.1
$J(x)$	auxiliary function in Riemann explicit formula	Definition 25.4.2