User:Aravind V R/sandbox1/Number/Notes

Congruences

Chinese remainder theorem

Let [a⁻¹]_b denote the multiplicative inverse of a (mod b), that is, a [a⁻¹]_b ≡ 1 (mod b). With N = n₁n₂...n_k, define N_j := ⁠N/n_j⁠ for j = 1, ..., k. Then

$x:=\sum _{i}a_{i}N_{i}\left[\left(N_{i}\right)^{-1}\right]_{n_{i}}=a_{1}N_{1}\left[\left(N_{1}\right)^{-1}\right]_{n_{1}}+a_{2}N_{2}\left[\left(N_{2}\right)^{-1}\right]_{n_{2}}+\cdots +a_{k}N_{k}\left[\left(N_{k}\right)^{-1}\right]_{n_{k}},$

satisfies the congrugences x ≡ a_i (mod n_i) for all i = 1, ..., k .

Fermat's little theorem

Fermat's little theorem states that if p is a prime number, then for any integer a, the number a ^p − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as

$a^{p}\equiv a{\pmod {p}}.$

For example, if a = 2 and p = 7, 2⁷ = 128, and 128 − 2 = 7 × 18 is an integer multiple of 7. If a is not divisible by p, Fermat's little theorem is equivalent to the statement that a ^{p − 1} − 1 is an integer multiple of p, or in symbols

$a^{p-1}\equiv 1{\pmod {p}}.$

Carmichael number

Carmichael number is a composite number $n$ which satisfies the modular arithmetic congruence relation:

$b^{n-1}\equiv 1{\pmod {n}}$

for all integers $1<b<n$ which are relatively prime to $n$.

Theorem (A. Korselt 1899): A positive composite integer $n$ is a Carmichael number if and only if $n$ is square-free, and for all prime divisors $p$ of $n$, it is true that $p-1\mid n-1$.

Hensel's lemma

Let $f(x)$ be a polynomial with integer (or p-adic integer) coefficients, and let m,k be positive integers such that m ≤ k. If r is an integer such that

$f(r)\equiv 0{\pmod {p^{k}}}$ and $f'(r)\not \equiv 0{\pmod {p}}$

then there exists an integer s such that

$f(s)\equiv 0{\pmod {p^{k+m}}}$ and $r\equiv s{\pmod {p^{k}}}.$

Furthermore, this s is unique modulo p^k+m, and can be computed explicitly as

$s=r+tp^{k}$ where $t=-{\frac {f(r)}{p^{k}}}\cdot (f'(r)^{-1}).$

Arithmetic functions

Euler's totient function

Euler's totient function (or Euler's phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n. The function φ(n) is multiplicative.

Euler's product formula

It states

$\varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),$

where the product is over the distinct prime numbers dividing n.

Möbius function

For any positive integer n, define μ(n) as the sum of the primitive n-th roots of unity. It has values in {−1, 0, 1} depending on the factorization of n into prime factors:

• μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
• μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
• μ(n) = 0 if n has a squared prime factor.

Von Mangoldt function

The von Mangoldt function, denoted by Λ(n), is defined as

$\Lambda (n)={\begin{cases}\log p&{\text{if }}n=p^{k}{\text{ for some prime }}p{\text{ and integer }}k\geq 1,\\0&{\text{otherwise.}}\end{cases}}$

Chebyshev function

The Chebyshev function is either of two related functions. The first Chebyshev function ϑ(x) or θ(x) is given by

$\vartheta (x)=\sum _{p\leq x}\log p$

with the sum extending over all prime numbers p that are less than or equal to x.

The second Chebyshev function ψ(x) is defined similarly, with the sum extending over all prime powers not exceeding x:

$\psi (x)=\sum _{p^{k}\leq x}\log p=\sum _{n\leq x}\Lambda (n)=\sum _{p\leq x}\lfloor \log _{p}x\rfloor \log p,$

where $\Lambda$ is the von Mangoldt function.

The second Chebyshev function can be seen to be related to the first by writing it as

$\psi (x)=\sum _{p\leq x}k\log p$

where k is the unique integer such that p^k ≤ x and x < p^k+1.

Liouville function

The Liouville function, denoted by λ(n) and named after Joseph Liouville, is an important function in number theory.

If n is a positive integer, then λ(n) is defined as:

$\lambda (n)=(-1)^{\Omega (n)},\,\!$

where Ω(n) is the number of prime factors of n.

Dirichlet convolution

If f and g are two arithmetic functions (i.e. functions from the positive integers to the complex numbers), one defines a new arithmetic function f ∗ g, the Dirichlet convolution of f and g, by

${\begin{aligned}(f*g)(n)&=\sum _{d\,\mid \,n}f(d)g\left({\frac {n}{d}}\right)\\&=\sum _{ab\,=\,n}f(a)g(b)\end{aligned}}$

where the sum extends over all positive divisors d of n, or equivalently over all distinct pairs (a, b) of positive integers whose product is n.

Dirichlet inverse

Inverse exists if $f(1)\neq 0$

Arithmetic function	Dirichlet inverse
Constant function equal to 1	Möbius function μ
$n^{\alpha }$	$\mu (n)\,n^{\alpha }$
Liouville's function λ	Absolute value of Möbius function |μ|

Möbius inversion formula

The classic version states that if g and f are arithmetic functions satisfying

$g(n)=\sum _{d\,\mid \,n}f(d)\quad {\text{for every integer }}n\geq 1$

then

$f(n)=\sum _{d\,\mid \,n}\mu (d)g(n/d)\quad {\text{for every integer }}n\geq 1$

where μ is the Möbius function

In the language of Dirichlet convolutions, the first formula may be written as

$g=f*1$

where * denotes the Dirichlet convolution, and 1 is the constant function $1(n)=1$. The second formula is then written as

$f=\mu *g.$

Quadratic residue

An integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:

$x^{2}\equiv q{\pmod {n}}.$

Otherwise, q is called a quadratic nonresidue modulo n.

Euler's criterion

Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely, Let p be an odd prime and a an integer coprime to p. Then

$a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ if there is an integer }}x{\text{ such that }}a\equiv x^{2}{\pmod {p}}\\-1{\pmod {p}}&{\text{ if there is no such integer.}}\end{cases}}$

Euler's criterion can be concisely reformulated using the Legendre symbol:

$\left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}{\pmod {p}}.$

Legendre symbol

The Legendre symbol is a function of a and p defined as

$\left({\frac {a}{p}}\right)={\begin{cases}1&{\text{ if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{ if }}a{\text{ is a quadratic non-residue modulo }}p,\\0&{\text{ if }}a\equiv 0{\pmod {p}}.\end{cases}}$

Legendre's original definition was by means of the explicit formula

$\left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}\quad {\text{ and }}\quad \left({\frac {a}{p}}\right)\in \{-1,0,1\}.$

By Euler's criterion, which had been discovered earlier and was known to Legendre, these two definitions are equivalent.

Other

Dirichlet's theorem on arithmetic progressions