Euler function

Euler function $\varphi$:

• Given a positive integer $n\in {\mathbb{N}}^{+}$, define $\varphi (n)$ to be the number of integers $x\in {\mathbb{N}}^{+},x\le n$ such that $gcd(x,n)=1$
  • number of integers that are relatively prime with $n$. 1 is also counted
  • $\varphi (6)=2,\varphi (7)=6$
• If the prime factor of $n$ is $n=p_1^{k_1}.p_{}^{k_2}...p_m^{k_m}$ thentheorem $\varphi (n)=n\prod _i(1-\frac{1}{p_i})={\prod }_i(p_i^{k_i}-p_i^{k_i-1})$
• If $p$ is a prime, then $\varphi (p)=p-1$. If $n=pq$ where $p\ne q$ are both primes, then $\varphi (n)=(p-1)(q-1)$corollary
  • $n$ is composite

Euler’s theorem

Primality test