Summary

Mathematics Number_Theorem

Bezout Theorem

There exists two integers $x$ and $y$ s.t $ax+by==gcd(a,b)$

Wilson Theorem

For $p$ is a prime,$(p-1)! \equiv -1\pmod{p}$

Fermat little theorem

If $p$ is a prime,$a^{p-1} \equiv 1\pmod{p}$,with $p \not\mid a$

Euler's theorem

1. let $\phi(n)$ denote $|{Z}_n^*|$ ,$a^{\phi(n)} \equiv 1\pmod{n}$

2. when $p$ is a prime,$\phi(p)=p-1$

3. when $gcd(m,n)==1$,$\phi(mn)=\phi(m)\phi(n)$

Modulus Inverse

• let $p$ denote prime,then every $n \in {Z}_p^*$ have a unique inverse modulus $p$

• let $p$ be a prime,the inverse of $1$ and $p-1$ modulus $p$ is itself

• let $a,n$ be an integer and we can alway find an integer $x$ s.t $ax \equiv gcd(a,n)\pmod{n}$

• when $gcd(a,n)==1$,we can find $a$'s inverse modulus $n$

Chinese Remainder Theorem

For $n$ congruence equations:
let $M_i=\prod\limits_{i \not=j}m_j$
solution $x=\sum\limits_{i=1}^nM_i{M}_i^{-1}a_i$