Euler's theorem

Description:

• Given $a,n\in {\mathbb{N}}^{+}$, if $a$ and $n$ are relatively prime, then $a^{\varphi (n)}\equiv 1(modn)$corollary
• If $gcd(a,n)=1$, then $a^{\varphi (n)-1}\mathrm{mod}n$ is an inverse of a modulo $n$corollary
• If $gcd(a,n)=1$, then $a^x\equiv a^{x\mathrm{mod}\varphi (n)}\mathrm{mod}n$corollary
• Let ${\mathbb{Z}}_n^{\ast }=\{k|1\le k\in {\mathbb{N}}^{+},k\le n,gcd(k,n)=1\}$. Consequently $\varphi (n)=|{\mathbb{Z}}_n^{\ast }|$
  • Set of all relative prime and 1
• If $j,k\in {\mathbb{Z}}_n^{\ast }$ then $j{\cdot }_{n}k\in {\mathbb{Z}}_n^{\ast }$lemma
  • Multiplication modulo
• For any element $k$ and subset of $S$ of ${\mathbb{Z}}_n$, let define $kS\triangleq \{k{\cdot }_{n}s|s\in S\}$
  • Example: $k=3,n=10\to k{\mathbb{Z}}_{10}^{\ast }=\{3{\cdot }_{10}1,3{\cdot }_{10}3,3{\cdot }_{10}7,3{\cdot }_{10}9\}=\{3,9,1,7\}$

Fermat’s little theorem