View source for User:Aravind V R/sandbox1/Number/Notes

==Congruences==
===Chinese remainder theorem===

Let {{math|[''a''<sup>−1</sup>]<sub>''b''</sub>}} denote the [[Modular multiplicative inverse|multiplicative inverse]] of {{math|''a'' (mod ''b'')}}, that is, {{math|''a'' [''a''<sup>−1</sup>]<sub>''b''</sub> ≡ 1 (mod ''b'')}}. 
With {{math|1=''N'' = ''n''<sub>1</sub>''n''<sub>2</sub>...''n<sub>k</sub>''}}, define {{math|1=''N<sub>j</sub>'' := {{sfrac|''N''|''n<sub>j</sub>''}} }} for {{math|1=''j'' = 1, ..., ''k''}}. Then 

:<math>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},</math>

satisfies the congrugences {{math|''x'' ≡ ''a<sub>i</sub>'' (mod ''n<sub>i</sub>'')}} for all {{math|1=''i'' = 1, ..., ''k''}} .

===Fermat's little theorem===
[[Fermat's little theorem]] states that if {{mvar|p}} is a [[prime number]], then for any [[integer]] {{mvar|a}}, the number {{math|''a''<sup> ''p''</sup> &minus; ''a''}} is an integer multiple of {{mvar|p}}.  In the notation of [[modular arithmetic]], this is expressed as
:<math>a^p \equiv a \pmod p.</math>
For example, if {{mvar|a}} = 2 and {{mvar|p}} = 7, 2<sup>7</sup> = 128, and 128&nbsp;&minus;&nbsp;2 = 7 × 18 is an integer multiple of 7.
If {{mvar|a}} is not divisible by {{mvar|p}}, Fermat's little theorem is equivalent to the statement that {{math|''a''<sup> ''p'' &minus; 1</sup> &minus; 1}} is an integer multiple of {{mvar|p}}, or in symbols
:<math>a^{p-1} \equiv 1 \pmod p.</math>

====Carmichael number==== 
[[Carmichael number]] is a [[composite number]] <math>n</math> which satisfies the [[modular arithmetic]] congruence relation:
:<math>b^{n-1}\equiv 1\pmod{n}</math>
for all integers   <math>1<b<n</math> which are [[relatively prime]] to <math>n</math>.

:'''Theorem''' ([[Alwin Korselt|A. Korselt]] 1899): A positive composite integer <math>n</math> is a Carmichael number if and only if <math>n</math> is [[square-free integer|square-free]], and for all [[prime divisor]]s <math>p</math> of <math>n</math>, it is true that <math>p - 1 \mid n - 1</math>.

===Hensel's lemma===
Let <math>f(x)</math> 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
:<math>f(r) \equiv 0 \pmod{p^k}</math> and <math>f'(r) \not\equiv 0 \pmod{p}</math>
then there exists an integer ''s'' such that
:<math>f(s) \equiv 0 \pmod{p^{k+m}}</math> and <math>r \equiv s \pmod{p^{k}}.</math>
Furthermore, this ''s'' is unique modulo ''p''<sup>''k''+m</sup>, and can be computed explicitly as
:<math>s = r + tp^k</math> where <math>t = - \frac{f(r)}{p^k} \cdot (f'(r)^{-1}).</math>

==Arithmetic functions==
===Euler's totient function===
Euler's totient function (or Euler's phi function), denoted as {{math|φ(''n'')}} or {{math|ϕ(''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
:<math>
\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right),
</math>
where the product is over the distinct [[prime number]]s dividing n.

===Möbius function===
For any positive [[integer]] ''n'', define  ''μ''(''n'') as the sum of the [[Root_of_unity#General definition|primitive {{mvar|n}}-th roots of unity]]. It has values in <nowiki>{</nowiki>{{num/neg|1}}, {{num|0}}, {{num|1}}} depending on the [[integer factorization|factorization]] of ''n'' into [[prime factor]]s:

* ''μ''(''n'') =  1 if ''n'' is a [[square-free integer|square-free]] positive integer with an [[even and odd numbers|even]] number of prime factors.
* ''μ''(''n'') = &minus;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 {{math|Λ(''n'')}}, is defined as

:<math>\Lambda(n) = \begin{cases} \log p & \text{if }n=p^k \text{ for some prime } p \text{ and integer } k \ge 1, \\ 0 & \text{otherwise.} \end{cases}</math>

===Chebyshev function===
The [[Chebyshev function]] is either of two related functions.  The '''first Chebyshev function''' ''&thetasym;''(''x'') or ''&theta;''(''x'') is given by

:<math>\vartheta(x)=\sum_{p\le x} \log p</math>

with the sum extending over all [[prime number]]s ''p'' that are less than or equal to  ''x''.

The '''second Chebyshev function''' ''&psi;''(''x'') is defined similarly, with the sum extending over all prime powers not exceeding&nbsp;''x'':

:<math> \psi(x) = \sum_{p^k\le x}\log p=\sum_{n \leq x} \Lambda(n) = \sum_{p\le x}\lfloor\log_p x\rfloor\log p, </math>

where <math>\Lambda</math> is the [[von Mangoldt function]]. 

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

:<math>\psi(x)=\sum_{p\le x} k \log p</math>

where ''k'' is the unique integer such that ''p''<sup>''k''</sup>&nbsp;≤&nbsp;''x'' and ''x''&nbsp;<&nbsp;''p''<sup>''k''+1</sup>.

===Liouville function===
The Liouville function, denoted by λ(''n'') and named after [[Joseph Liouville]], is an important [[function (mathematics)|function]] in [[number theory]].

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

:<math>\lambda(n) = (-1)^{\Omega(n)},\,\! </math>

where [[Big Omega function|&Omega;(''n'')]] is the number of [[prime number|prime]] [[divisor|factors]] of ''n''.

===Dirichlet convolution===
If ''f'' and ''g'' are two arithmetic functions (i.e. functions from the positive [[integer]]s to the [[complex number]]s), one defines a new arithmetic function {{nowrap|''f'' ∗ ''g''}}, the ''Dirichlet convolution'' of ''f'' and ''g'', by

:<math>
\begin{align}
(f*g)(n) 
&= \sum_{d\,\mid \,n} f(d)g\left(\frac{n}{d}\right) \\
&= \sum_{ab\,=\,n}f(a)g(b)
\end{align}
</math>

where the sum extends over all positive [[divisor]]s ''d'' of&nbsp;''n'', or equivalently over all distinct pairs {{nowrap|(''a'', ''b'')}} of positive integers whose product is ''n''.

====Dirichlet inverse====
Inverse exists if <math>f(1) \neq 0</math>
{| border="1"
! Arithmetic function !! Dirichlet inverse
|-
| Constant function equal to 1 || [[Möbius function]] ''μ''
|-
| <math>n^{\alpha}</math> || <math>\mu(n) \,n^\alpha</math>
|-
| [[Liouville's function]] ''λ'' || Absolute value of Möbius function {{abs|''μ''}}
|}

===Möbius inversion formula===
The classic version states that if ''g'' and ''f'' are [[arithmetic function]]s satisfying
: <math>g(n)=\sum_{d\,\mid \,n}f(d)\quad\text{for every integer }n\ge 1</math>
then
:<math>f(n)=\sum_{d\,\mid\, n}\mu(d)g(n/d)\quad\text{for every integer }n\ge 1</math>
where μ is the [[Möbius function]]

In the language of [[Dirichlet convolution]]s, the first formula may be written as
:<math>g=f*1</math>
where ''*'' denotes the Dirichlet convolution, and ''1'' is the [[constant function]] <math>1(n)=1</math>. The second formula is then written as
:<math>f=\mu * g.</math>

==Quadratic residue==
An [[integer]] ''q'' is called a '''quadratic residue''' [[modulo operation|modulo]] ''n'' if it is [[Congruence relation|congruent]] to a [[Square number|perfect square]] modulo ''n''; i.e., if there exists an integer ''x'' such that:

:<math>x^2\equiv q \pmod{n}.</math>

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]] [[modular arithmetic|modulo]] a [[prime number|prime]]. Precisely,
Let ''p'' be an [[odd number|odd]] prime and ''a''  an integer [[coprime]] to ''p''. Then<ref>Gauss, DA, Art. 106</ref>
:<math>
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}
</math>

Euler's criterion can be concisely reformulated using the [[Legendre symbol]]:<ref>Hardy & Wright, thm. 83</ref>
:<math>
\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p.
</math>

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

:<math>\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}</math>

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

:<math> \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\}. </math>

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]]