cardinality = number of elements in set = số lượng phần tử trong tập hợp

relatively prime: Two integers are relatively prime if they share no common positive factors (divisors) except 1 (gcd(x,y) = 1)

Euler's totient function, also known as phi-function ϕ(n), counts the number of integers between 1 and n inclusive, which are coprime to n. Two numbers are coprime if their greatest common divisor equals 1 (1 is considered to be coprime to any number).

The following properties of Euler totient function are sufficient to calculate it for any number:

• If p is a prime number, then $gcd(p,q)=1$ for all $1≤q<p$. Therefore we have:

  $$ ϕ(p)=p−1 $$

• If p is a prime number and $k \ge1$. Which gives us:

  $$ ϕ(p^k)=p^k−p^{k-1} $$

• If a and bb are relatively prime, then:

  $$ ϕ(ab)=ϕ(a)⋅ϕ(b) $$