lcm, gcd

• gcd，greatest common divisor（最大公约数）
• lcm，least common multiple（最小公倍数）

Euclid's Algorithm

Euler's totient function（phi function）

ϕ(n) 称为 Euler's totient function ，是计算一个自然数有多少个比他小的互质的自然数的个数，ϕ(12) = 4，ϕ(30) = 8

In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function. It can be defined more formally as the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.

For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, because gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since for n = 1 the only integer in the range from 1 to n is 1 itself, and gcd(1, 1) = 1.

Euler's totient function is a multiplicative function, meaning that if two numbers m and n are relatively prime, then φ(mn) = φ(m)φ(n). This function gives the order of the multiplicative group of integers modulo n (the group of units of the ring ℤ/nℤ).[6] It also plays a key role in the definition of the RSA encryption system.

Prime-counting function

Prime number Theorem

Prime number Theorem 以后会专门的深入~