Number Theory

• \[ \gcd(a,b) := \max\{d \mid d|a \land d|b\} \]
• \[ \gcd(a,0) = \gcd(0,a) := |a| \]
  • \(0\) divided by any number has remainder \(0\).

• It is commutative: \(\gcd(a,b) = \gcd(b,a)\).
• It is associative: \(\gcd(a, \gcd(b,c)) = \gcd(\gcd(a,b), c)\)
  • \(\gcd(a,b,c)\) is well defined.
• It is multiplicative for coprimes: \(\gcd(a_1a_2, b) = \gcd(a_1, b)\gcd(a_2,b)\) if \(a_1\) and \(a_2\) are relatively prime.
• \[ \def\gcd{\operatorname{gcd}} \gcd(a,b) = \gcd(a, b - a) \]
• \[ \gcd(a,b){\operatorname{lcm(a,b)}} = |ab| \]

It can be calculated from the greatest common divisor with \[ \operatorname{lcm}(a, b) = \frac{|ab|}{\operatorname{gcd}(a,b)}. \]

• 21, 49, 1001 method removes the factor of 10 each time, shifting the remainder.
• while it is not the case for 98 method and modulo method.

A totative of a positive integer \( n \) is a coprime \( k \) of \( n \), such that \( 0< k \le n \).

• For a complex number \(z\), \[ \sigma_z(n) := \sum_{d|n}d^z \]

• It is multiplicative: If two integer \(a, b\) are coprime, \(\sigma_z(ab) = \sigma_z(a)\sigma_z(b)\).
• \[ \sigma_z(n) = \prod_{i=1}^r\sum_{j=1}^{a_i}p_i^{jz} \]
  • where \(n=\prod_{i=1}^rp_i^{a_i}\) is the prime factorization.

• How to Find VERY BIG Prime Numbers? - YouTube

• The perfect number is the stable point of the Aliquot sequence.

• Repeating aliquot sequence of period 2.

• Has repeating aliquot sequence of period 3 or greater.

• A number that converges to the perfect number, along an Aliquot sequence.

• \[ s(n) := \sum_{d|n, d\neq n} d \]
• In terms of the divisor function \( s(n) = \sigma_1(n) - n \).

• Starting with a positive integer \(k\), the next term is the sum of proper divisors of the previous term.

Set of disjoint nonempty subsets of a set that covers the set.

• Every equivalence relation on a set defines a partition of the set

Or norm, \( \| P \| \)

The length of the longest subset.

• \[ \left[\vphantom{1}n \atop k\right] \]

• \[ \left\{\vphantom{1}n \atop k\right\} \]

• Number of partitions of a set.
• It is different from the integer partition in that each element is distinct from another.

The number of ways to divide a set into disjoint subsets of size two.

\[ \mathrm{PairPartition}(n) = \begin{cases} n!! & \text{if $n$ is even,}\\ 0 & \text{if $n$ is odd.} \end{cases} \]

• For two integers \(a,b\) with greatest common divisor \(d\), there exists integers \(x,y\) such that:
  • \[ ax+by = d \]
• Moreover, the integers of the form \(az+bt\) are exactly the multiples of \(d\).

• For a prime \(p\), and a positive integer \(a < p\), there exists an integer \(b\) such that:
  • \[ pq + ba = 1. \]
• Furthermore, by taking modulo \(p\), it follows that:
  • \[ ba \equiv 1 \pmod{p} \implies [b]\cdot [a] = [1] \]

• For all \( a\in\mathbb{Z} \) and primes \(p\), \( p\mid a^p-a \).
• Equivalently \[ a^{p-1}\equiv 1 \pmod{p}. \]

• pseudoprimes

• \[ a^{\varphi(n)} \equiv 1\pmod{n} \] where \(n\) and \(a\) are coprime and \(\varphi(n)\) is the Euler's totient function.

• If the remainders of an integer \(n\), when divided by pairwise coprime integers, are known, The remainder of \(n\), when divided by the products of the divisors, is uniquely determined.
• Equivalently, the map \[ x\mod{\left(\prod n_i\right)} \mapsto (x\mod {n_1},\dots,x\mod{n_k}) \] defines a ring isomorphism \[ \mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}. \]

• Fisrt appear in 孫子算經 from the third century, although it does not contain the proof nor the algorithm.

• The number of coprimes of a positive integer \(n\) up to \(n\). Aka totative. It includes \(1\).
  • An integer is not coprime of itself, except 1.

• It is multiplicative: \( \varphi(m)\varphi(n) = \varphi(mn) \), if \(m\) and \(n\) are relatively prime.
• \( \varphi(p^k) = p^{k-1}(p-1) \), since it counts all the number below \( p^k \) that is not a multiple of \(p\).

• \[ \varphi(n) = n\prod_{p\mid n}\left(1-\frac{1}{p}\right) \]
  • where \(p\) is prime.
• Equivalently, \[ \varphi(n) = \prod_{i=1}^rp_i^{k_i-1}(p_i-1) = p_1^{k_1-1}(p_1{-}1)\,p_2^{k_2-1}(p_2{-}1)\cdots p_r^{k_r-1}(p_r{-}1) \]
  • where \( n = \prod_{i=1}^r p_i^{k_i} \) is the prime factorization of \(n\).

• \[ \sum_{d|n}\varphi(d) = n \]
• \( \varphi(d) \) with \( d|n \) counts the number of generator of \( C_d \) that is a subgroup of \( C_n \). Since every element of \( C_n \) generate a cyclic subgroup of \( C_n \), they sum to the same number. (\( C_n \) being the \( \mathbb{Z}/n\mathbb{Z} \)).
• Applying the Möbius inversion formula,
  • \[ \varphi(n) = \sum_{d|n}\mu(d)\frac{n}{d} \]

• \[ \sum_{\begin{smallmatrix}1\le k\le n\\[.2em] \gcd(k,n)=1\end{smallmatrix}}\gcd(k-1,n) = \varphi(n)d(n) \]
  • where \( d(n) \) is the number of divisor of \(n\).
  • equivalently, the divisor function \( \sigma_0(n) \).

• The smallest positive integer \(m\) such that \[ a^m \equiv 1\pmod{n} \] for every integer \(a\) that is coprime to \(n\).

• \[ \lambda(n) = \begin{cases} \varphi(n)&\text{if $n$ is 1, 2, 4 or an odd prime power,}\\ \frac{1}{2}\varphi(n)&\text{if $n=2^r, r\ge 3$,}\\ \operatorname{lcm}\left(\lambda(n_1), \lambda(n_2),\dots,\lambda(n_k)\right)&\text{if $n=n_1n_2\dots n_k$ where $n_1,n_2,\dots,n_k$ are powers of distinct primes.} \end{cases} \]
• \(\varphi(n)\) is the Euler's totient function.

• \(D\colon \mathbb{N}\to \mathbb{N}\)
• \(D(p) = 1, p\text{ prime}\)
• \(D(mn) = D(m)n+ mD(n)\)
  • Leibniz Rule

• \(D(0) = D(1) = 0\)
• \(D(p^n) = np^{n-1}, p\text{ prime}\)
• \(D\) is not additive, unlike the differentiation.

• \[ \frac{\partial x}{\partial p} = n_p\frac{x}{p}. \]
• \[ D = \sum_{p\ \text{prime}}\frac{\partial}{\partial p}. \]
• \[ D(x) = x\sum_{p\ \text{prime}}\frac{n_p}{p}. \]
• where \(n_p\) can be interpreted as the p-adic valuation \(\nu_p(x)\).

• Way of writing \(n\) as a sum of positive integers, without distinguishing different orders.

• \(p(n)\)
• Partition function \(p(n)\) is the number of partitions of a non-negative integer \(n\).

• \[ \sum_{n=0}^\infty p(n)q^n = \prod_{j=1}^\infty \sum_{i=0}^\infty q^{ji} = \prod_{j=1}^\infty \frac{1}{1-q^j} \]
  • Reciprocal of the generating function is the Euler function
• Ramanujan noticed:
  • \(5\mid p(5k + 4)\), \(7\mid p(7k+5)\), \(11\mid p(11k+6)\)
• \[ p(n) \sim \frac{1}{4n\sqrt{3}}\exp\left(\pi\sqrt{\frac{2n}{3}}\right) \]

• Ferrers Diagram

• The order is also taken into account, unlike partitions.
• Positive integer has \(2^{n-1}\) distinct compositions.

• \[ \left( \frac{a}{p} \right) := \begin{cases} 1 & \text{if $n^2 \equiv a \mod{p}$ for some integer $n$} \\ 0 & \text{if $a \equiv 0 \mod{p}$} \\ -1 & \text{otherwise} \end{cases} \]

For two distinct odd prime numbers \( p \) and \( q \), \[ \left( \frac{p}{q} \right)\left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}. \]

Set up cards in the \( p\times q \) rectangular grid.

The parities of permutations upon these cards: \[ \operatorname{sgn}(R\mathpunct{\uparrow} D\mathpunct{\downarrow}) = \operatorname{sgn}(R\mathpunct{\uparrow} C\mathpunct{\downarrow}) \cdot \operatorname{sgn}(C\mathpunct{\uparrow} D\mathpunct{\downarrow}) \] corresponds to each term in the law: \[ \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \cdot \left( \frac{p}{q} \right). \]

The permutation \( C\mathpunct{\uparrow}D\mathpunct{\downarrow} \) has the same parity as the permutation of integers from \( 0 \) to \( q\) generated by multiplying each elements by \( p \) module \( q \).

Due to the group isomorphism \( \mathbb{Z}_q^{\times} \cong \mathbb{Z}_{q-1}^+ \) and the conservation of parity under conjugation, this permutation in turn has the same parity as the permutation of cycling by \( k \) places, where \( k \) satisfies \( r^k = p \) for an arbitrary primitive \( r \).

The parity of cyclic permutation is 1 if \( k \) is an even, and -1 if it is odd. The \( k \) is even if and only if \( p \) is a square number, therefore this value is equal to the Legendre symbol.

• \[ \mu(n) = \begin{cases} 1&\text{if $n$ is square free, and has even number of prime factors},\\ -1&\text{if $n$ is square free, and has an odd number of prime factors},\\ 0&\text{if $n$ is divisible by a square}.\\ \end{cases} \]

• \[ \sum_{n=1}^\infty \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)} \] where \(\zeta(s)\) is the Riemann zeta function.
• The inverse of the constant 1 function under Dirichlet convolution:
  • \[ 1*\mu = \epsilon \]
  • The defining property.
  • The Dirichlet convolution with Möbius function is the inverse Möbius transform.
• It follows that \(\mu(1) = 1\), and \[ \forall n\ge 2, \sum_{d\mid n}\mu(d) = 0. \] For examples,
  • \( \mu(1) = 1 \)
  • \( \mu(1) + \mu(2) = 0 \implies \mu(2) = -1\)
  • \( \mu(1) + \mu(2) + \mu(4) = 0 \implies \mu(4) = 0 \)
  • \( \mu(1) + \mu(2) + \mu(3) + \mu(6) = 0 \implies \mu(6) = 1 \)
  • \( \mu(1) + \mu(2) + \mu(3) + \mu(5) + \mu(6) + \mu(10) + \mu(15) + \mu(30) = 0 \implies \mu(30) = -1 \)

• For an arithmetic function \(f, g\),
• \[ \forall n \ge 1, g(n) = \sum_{d|n}f(d) \implies \forall n\ge 1,f(n) = \sum_{d|n}\mu(d)g\left(\frac{n}{d}\right) \]
  • In other words \(g = 1*f \implies f = \mu*g\).

• For \(f,g\colon \mathbb{N}\to \mathbb{C}\),
• \[ (f*g)(n) := \sum_{d|n} f(d)g\left(\frac{n}{d}\right) \]

An arithmetic function can be thought of as the coefficient of a series: \[ \sum_{n=1}^{\infty} f(n) n^x. \]

The Dirichlet convolution corresponds to finding the coefficients of the product of two such series: \[ \sum_{n=1}^{\infty}(f\ast g)(n) n^x = \left( \sum_{n=1}^{\infty} f(n) n^x \right) \left( \sum_{n=1}^{\infty}g(n) n^x \right). \]

• \(1*1 = \sigma_0\), \(1*\mathrm{id} = \sigma_1\)
  • where \(1\) is the constant function, \(\sigma_z\) is the divisor function
• Identity element is \(\epsilon\), with \(\epsilon(1) = 1\) and \(\forall n\neq 1, \epsilon(n) = 0\)
• Associative
• Distributive over Addition
• Commutative
• Sequences that starts with 1, forms a group under the Dirichlet convolution.

• The Dirichlet convolution with the constant function: \(1*f\).

• \[ \sum_{k=1}^n k^p = \frac{1}{p+1}\sum_{r=0}^p \binom{p+1}{r} B_r^+ n^{p+1-r} \] where \(B_r^+\) are the Bernoulli numbers.
• Using the umbral calculus,
  • \[ \sum_{k=1}^n k^p = \frac{1}{p+1}((n+B)^{p+1} - B^{p+1}) \]

• Sequence \(E_n\) of integers defined by the exponential generating function:
  • \[ \frac{1}{\cosh t} =: \sum_{n=0}^\infty \frac{E_n}{n!} t^n \]
  • Using the hyperbolic function

• Every odd Euler numbers are zero.

• The exponential generating function for the Euler polynomials is:
  • \[ \frac{2e^{xt}}{e^t - 1} = \sum_{n=0}^\infty E_n(x)\frac{t^n}{n!} \]
• It forms a close parallel to the Bernoulli polynomials

• \(E_0 = 1\)
• \(E_2 = -1\)
• \(E_4 = 5\)
• \(E_6 = -61\)

• Pell Equation, Pell-Fermat Equation

• \[ \frac{a}{b+c} + \frac{b}{c+a} + \frac{c}{a+b} = 4. \]
  • ‎Alon Amit (אלון עמית)‎'s answer to How do you find the positive integer solu…

• Farey sequence of order \(n\) is completely reduced fractions between, and including, 0 and 1, with the largest denominator being the number \(n\).

• Every fractions up to reduction can be generated by Farey sequence. The construction is \[ \frac{a}{b}\oplus \frac{c}{d}=\frac{a+c}{b+d} \] where \(\oplus\) is for the mediant.

• It is a projection of upper half of the standard lattice (lattice with base \((1,0),(0,1)\)) onto the line \(y=1\).
• This extends the Farey sequence to the entire real line, which makes Farey sequence the natural structure of \(\mathbb{R}\).

• It can generate a continued fraction representation of a real number, by counting how many consecutive left or right bubble has been pierced by the line extending from the above.
• First take the integer part of the real number for the integer part of the continued fraction. \[ [\lfloor x \rfloor;\dots,1] \]
• Count the first bubble as left bubble, and continue counting. \(L^{a_{1}}R^{a_{2}}L^{a_{3}}\dots\)

• These become the fractional part. \[ [\lfloor x \rfloor;a_{1},a_{2},\dots,1]=\lfloor x \rfloor+\dfrac{1}{a_{1}+\dfrac{1}{a_{2}+\dfrac{\ddots}{1}}} \]

  Taking the continued fraction just before some large \(a_{i}\), \([n;a_{1},a_{2},\dots,a_{i-1}]\), It becomes a particularly good Diophantine approximation of the real number with relatively small denominator, which is related to Dirichlet's approximation theorem.

• Mediant of two rational number is defined as \[ \frac{a}{b}\oplus \frac{c}{d} \equiv \frac{a+c}{b+d} \]
• Mediant can be thought of as vector addition \[ \begin{bmatrix} a \\ b \end{bmatrix} +\begin{bmatrix} c \\ d \end{bmatrix} = \begin{bmatrix} a+c \\ b+d \end{bmatrix} \] This can be translated to rational numbers by
  • taking the slope,
  • or projecting to the line \(y=1\) with respect to the origin, which is equivalent to taking the reciprocal of the slope.

• \[ \frac{a}{b} = \frac{c}{d} = k \implies \frac{a+c}{b+d} = k. \]

• Liouville-Roth Irrationality Measure, Irrationality Exponent, Approximation Exponent, Liouville-Roth Constant

• Thue-Siegel-Roth Theorem
  • Algebraic numbers cannot have many Diophantine approximations that are "very good".

• \(x\in \mathbb{R}\), for every positive integer \(n\), there exists a pair of integers \((p, q)\) with \(q>1\) such that \[ 0< \left| x - \frac{p}{q}\right| < \frac{1}{q^n}. \]

• A number that's a possibly infinite sum of possibly negative powers of prime \(p\) with coefficients less than \(p\). Only finite number of negative powers of \(p\) are allowed.
• If no negative powers are present than it's specifically called a p-adic integer.
• Completely separate number system that lies outside of real or complex numbers.
• If we establish an isomorphism between p-adic and real, we can solve problem in the p-adic realm and translate it into a real number.

• Basic lemma: There exists an injection from rational numbers to p-adic numbers.
• p-adic contains real numbers.
• 2-adic has \(\pm \sqrt{-3/2}\) but not \(\sqrt{-1}\).
• 5-adic contains complex numbers.

• valuation of the p-adic number

• Combination

• Multicombination, Multisubset, 중복조합
• \[ \left(\!\!\binom{n}{k}\!\!\right) = \binom{n+k-1}{k} \]
• Stars and bars

• Permutation by Bins
  • 같은 것이 있는 순열
  • \[ \begin{pmatrix} n\\ k_1, k_2,\dots , k_m\end{pmatrix} := \frac{n!}{k_1!k_2!\dots k_m!} \]
    • when \(\sum_i k_i \neq n\), it is defined to be 0.

• 원순열

• \(a^{p}-a\) for prime number length.

• \[ \frac{1}{n}\sum_{l|\mathrm{gcd}(p, q, r)}\varphi(l)\frac{(n/l)!}{(p/l)!(q/l)!(r/l)!} \]
  • where \(\varphi\) is the Euler's totient function.
• It is derived from Burnside's lemma, by noticing that it is the quotient set of all possible permutation by the cyclic group \( C_n \).
  • The summands counts the number of fixed elements by the rotation by the multiple of \(l\) units, excluding the overlapping rotations, which is naturally accounted in the \(\varphi(l)\) which counts the number of generators of \(C_l\).
  • The factorial part only counts the permutation within \(1/l\) of the entire sequence.
  • \(l|\gcd(p,q,r) \implies l|n\)

• \(M(\alpha, n)\) is the number of distinct aperiodic necklaces of \(n\) beads chosen out of \(\alpha\) available colors.
• \[ \alpha^n = \sum_{d|n} d\cdot M(\alpha, d) \]

• General Necklace-Counting Function
• It includes the periodic ones as well.
• \[ N(\alpha, n) = \sum_{d|n}M(\alpha,d) = \frac{1}{n}\sum_{d|n}\varphi\left(\frac{n}{d}\right)\alpha^d \]
  • where \(\varphi\) is the Euler's totient function.
• The second formulation is obtained by the Burnside's lemma.

• Let \(X\) be a finite set, \(G\) be the group of permutations of \(X\), and \(Y\) be a possibly infinite weighted set with the numbers \(f_{w_i}\) of scalar- or vector-valued weight \(w_i\in \mathbb{N}_0^{k\le \infty}\) elements are given by the generating function: \[ f(t_1, t_2,\dots) = f_{(0,0,\dots)} + f_{(1,0,\dots)}t_1 + f_{(0,1,\dots)}t_2 + \cdots + f_{(1,1,\dots)}t_1t_2 + \cdots + f_{(2,0,\dots)}t_1^2 + \dots. \]
  • The exponent is the weight, and the subscript is the position of the weight.
• Let \(Z_G\) be the multivariate generating function cycle index: \[ Z_G(t_1, t_2, \dots, t_n) = \frac{1}{|G|}\sum_{g\in G}t_1^{c_1(g)}t_2^{c_2(g)}\cdots t_n^{c_n(g)} \]
  • where \(n = |X|\) and \(c_k(g)\) is the number of \(k\)-cycles of the group element \(g\) as a permutation of \(X\).
• The generating function \(F(t_1, t_2, \dots)\) of the number \(F_{w_i}\) of arrangements \(\varphi\in Y^X\) with weight \(w_i = \sum_{x\in X}w(\varphi(x))\) is given by:
  • \[ F(t_1, t_2, \dots) = Z_G(f(t_1, t_2, \dots), f(t_1^2, t_2^2, \dots), f(t_1^3, t_2^3, \dots), \dots, f(t_1^n, t_2^n, \dots)). \]

• For a group \(G\) as the permutations (often by a natural action), the cycle index is
• \[ Z(G) = \frac{1}{|G|}\sum_{g\in G}\prod_{k=1}^n a_k^{j_k(g)} \]
  • where \( j_k(g) \) is the number of cycles of \( g \) of length \( k \).
• It is well defined, since every permutation \( g \) in \(G\) has a unique decomposition into disjoint cycles: \[ \prod_{c\ \text{cycle}\in g}a_{|c|} = \prod_{k=1}^na_k^{j_k(g)} \]
  • \( |c| \) is the length of the cycle \(c\).

• The group \(G\) consists of coefficient number of elements containing the exponent number of cycles of length given by the subscript.

• For the special case, that there are \(m\) elements (colors) in \(Y\) with wight 0, \(f(t) = m\).
• \[ F(0) = Z_G(m,m,\dots,m) \]
• which simplifies to \[ |Y^X/G| = \frac{1}{|G|}\sum_{g\in G}m^{c(g)}. \]

• Parity of the number of inversions: \[ \operatorname{sgn}(\sigma) = (-1)^{N(\sigma)} \]
• The number of transpositions equivalent. Although there's many possible decompositions, the parity remains the same, which means the parity is well-defined.

• A pair of elements that are out of order with respect to the initial position.

• Describe: Describe the term
• Involution: Find the parity involution
• Exception: The exception to the parity involution will be left behind as the result of the sum.