Note 2020.09.22 A Bit of Number Theory

This article is supported by Xu Jintao.

Prime determination Finding the number of factors Linear sieve Finding the smallest prime factor Euler's totient function Linear sieve for Euler's totient function のののののの

Determination of prime numbers

How to determine whether a number $x$ is prime? (single query)

Brute force: use numbers in $[2,\lceil\sqrt{N}\rceil]$ to test $x$. If there exists a $y$ in the interval such that $y|x$, then $x$ is composite; otherwise, it is prime.

Complexity $O(\sqrt{N})$

Unique prime factorization

Obviously, an integer can be decomposed into the product of several primes $p$, i.e., the unique prime factorization of a number: $$x= \prod{p_{i}^{k_i}}$$

Finding the unique prime factorization

So how do we find the prime factorization of a number? (At this point we do not know which primes there are.)

Similar to the method in Prime determination, use trial division on $x$ in ascending order with complexity $O(\sqrt{N})$. If there exists $y$ such that $y|x$, let $x=x \div y$. If still $y|x$, continue doing so. For the same $y$, count the number of times it appears.

Intuitively, we can see that each $k$ obtained is necessarily a prime $p$, and the counted number of occurrences is the exponent $k$ of this prime.

Proof: If there exists a $y$ that can be decomposed into two (or more) primes $p_1,p_2......$, then for any such $p$, we must have $p<y$. If so, this prime $p$ must have appeared earlier.

Complexity $O(\sqrt{N})$

How many factors? I

How to find the number of factors of a number?

Represent the primes after decomposing a number $x$ as a multiset $P$. The product $y$ of the elements in any non-empty subset $S \in P$ is a factor of $x$.

Consider the number of times a certain prime factor $p$ of $x$ is used. The total number of factors is $\prod{k_i+1}$.

Using the above method for prime factorization, we can obtain each exponent.

Complexity $O(\sqrt{N})$

Linear sieve

Find in $O(N)$ whether each number in $[1,N]$ is prime.

Using the property of "unique prime factorization", we try to make each number be updated only once:

0. If a number has not been marked, this number is prime.
1. For each number $x$, we traverse the prime list $p$ once and mark $x·p_i$.

Preprocessing $O(N)$, query $O(1)$.

Smallest prime factor

Find the smallest prime factor of a number. It seems unrelated to the linear sieve, but it can indeed be solved with the linear sieve.

Consider maintaining during the linear sieve an $f_i$ representing the smallest prime factor of $i$ ($p$ is some prime): $$\left\{ \begin{aligned} f_i &= i & (i = p) \\ f_i &= f_j & (i = j \times p) \end{aligned} \right.$$

Preprocessing $O(N)$, query $O(1)$.

How many factors? II

We are already familiar with this problem. This time we also consider performing unique prime factorization on a number.

Now we can already obtain the smallest prime factor of each number in linear time. We can use it to decompose a number $x$ by repeatedly setting $x=x \div f_x$. ($f_i$ represents the smallest prime factor of $i$)

Obviously the primes we obtain are in ascending order (smallest prime factor), so the exponents are also convenient to count.

Prove that the complexity of this algorithm is not very high. Consider two questions.

What is the maximum number of prime factors of a number?

Make the prime factors as small as possible, assume they are all $2$. It can be found that the maximum number of prime factors of $x$ is on the order of about $log_2x$.

What is the maximum number of factors of a number?

A relatively obvious conclusion: when there are more distinct prime factors, the number of factors is larger. We can brute-force enumerate each prime in ascending order and multiply them together $\prod{p_i}$. It can be found that this number grows very quickly. When $i=9$, this number already exceeds $10^9$.

Preprocessing $O(N)$, query $O(log_2x)$.

Euler's totient function

Definition: Euler's totient function $φ(x)$ represents the number of numbers less than $x$ that are coprime to $x$.

Multiplicativity of Euler's totient function

Definition: For $f(x)$, if when $(x,y)=1$, $f(xy)=f(x)f(y)$, then $f(x)$ is a multiplicative function.

As is well known, $φ$ is a multiplicative function, but why is it multiplicative?

a If $p$ is prime, $\phi(p)=p-1$

The conclusion is obvious.

b If $p$ is prime, $φ(p^k)=p^k - p^{k-1}$

Consider inclusion-exclusion: subtract the multiples of $p$ from the $p^k$ positive integers. Because there is only one prime factor $p$, all multiples of $p$ are multiples of $p^k$, and other numbers are not multiples of $p^k$. There are $p^k \div p = p^{k-1}$ such numbers.

c If $p_1,p_2$ are primes, $φ(p_{1}^{k_1}·p_{2}^{k_2})=φ(p_{1}^{k_1})·φ(p_{2}^{k_2})$

Similar to $b$, we consider inclusion-exclusion. Because $(p_{1}^{k_1},p_{2}^{k_2})=1$, the overlapping part is only multiples of $p_1p_2$. The formula is:

$$\phi(p_{1}^{k_1}·p_{2}^{k_2})=p_{1}^{k_1}·p_{2}^{k_2}-p_{1}^{k_1-1}·p_{2}^{k_2}-p_{1}^{k_1}·p_{2}^{k_2-1}+p_{1}^{k_1-1}·p_{2}^{k_2-1}$$

Using $b$, we can separately find $φ(p_{1}^{k_1})=p_{1}^{k_1}-p_{1}^{k_1-1}$ and $φ(p_{2}^{k_2})=p_{2}^{k_2}-p_{2}^{k_2-1}$.

Obviously, multiplying them equals the above formula, so it is proved.

d Euler's totient function $φ$ is multiplicative

Consider extending $c$ to the case of multiple prime factors $p$, doing similar inclusion-exclusion. Factoring the formula obtained by inclusion-exclusion gives the following formula: $$φ(x)=\prod{p_{i}^{k_i-1}(p_i-1)}$$

How to find $φ$

Factoring out the common factor from the formula in part $d$ above gives $$φ(x)=x\prod_{p|x}{(1- \frac{1}{p})}$$

Then we use the method in Finding the unique prime factorization to obtain each prime factor and substitute it into the formula.

Complexity $O(\sqrt{N})$

Linear sieve for Euler's totient function

Of course we can also find the unique prime factorization through the linear sieve, but this time we have an even more powerful algorithm.

For a prime $p$ and a number $k$ with $(p,k)>1$, $φ(pk)=p·φ(k)$

Consider conclusion $c$ in Multiplicativity of Euler's totient function: $$φ(p_{1}^{k_1}·p_{2}^{k_2})=p_{1}^{k_1}·p_{2}^{k_2}-p_{1}^{k_1-1}·p_{2}^{k_2}-p_{1}^{k_1}·p_{2}^{k_2-1}+p_{1}^{k_1-1}·p_{2}^{k_2-1}$$ If we let $k_1'=k_1+1$, the above formula only needs to be transformed into $$φ(p_{1}^{k_1'}·p_{2}^{k_2})=p_{1}^{k_1+1}·p_{2}^{k_2}-p_{1}^{k_1+1-1}·p_{2}^{k_2}-p_{1}^{k_1+1}·p_{2}^{k_2-1}+p_{1}^{k_1}·p_{2}^{k_2-1}$$

We can obtain $φ(p_{1}^{k_1'}·p_{2}^{k_2})=φ(p_{1}^{k_1}·p_{2}^{k_2})·p$.

This formula can also be extended.

Alright, now we can perform the linear sieve.

In the linear sieve, if we want to use a number $x$ and a prime $p$ to update the $φ$ of $xp$, we first check the condition $p|x$: $$\left\{ \begin{aligned} φ(p) &= p-1 \\ φ(xp) &= φ(x)*(p-1) & (p \nmid x) \\ φ(xp) &= φ(x)*p & (p|x) \end{aligned} \right.$$