## Ex 1 (The Unique Factorization Theorem)

Prove that$a\times b=(a,b)\times [a,b]$,$a,b\in \mathbf{N}$. (P5)

First, to be obvious, for all$a,b\in N$, we have$a+b=\min(a,b)+\max(a,b)$.

Let$f(x,p)$denotes the largest$c\in \mathbf{N}$that$p^c|x$. According to the unique factorization theorem, we have

Let’s consider a prime factor$p$of$ab$.

To be exactly,$f(ab,p)=f(a,p)+f(b,p)$.

Let$d=(a,b)$, so we have$p^{\min(f(a,p),f(b,p))}|d,p^{\min(f(a,p),f(b,p))+1}\nmid d$, because$a$and$b$should both be divisible by$d$. Also we want to maximize$d$, so we try to maximize the power of$p$in$d$. That is equal to$f(d,p)=\min(f(a,p),f(b,p))$.

Similarly, Let$m=[a,b]$, so we have$f(m,p)=\max(f(a,p),f(b,p))$.

So when we multiply$d$and$m$, we will get

Finally$ab=\prod_{p\text{ is prime}}p^{f(ab,p)}=\prod_{p\text{ is prime}}p^{f(dm,p)}=dm$.

Q. E. D.

## Ex 2 (Diophantine Equation)

Given that$a,b,c,x,y,z\in \mathbf{Z}^+,(a,b)=(b,c)=(a,c)=1, a,b,c>0$, find the largest$n(n\in \mathbf{N})$that makes$abx+bcy+acz=n$unsolvable. (P6)

Answer:$2abc-ab-bc-ac$.

## Ex 3 (Module)

Euler Function: Prove that

through direct calculation or combination meanings. (P13)

### Solve using Direct Calculation

Let$M(S)=\prod_{x\in S}x$.

Use the unique factorization theorem, Let$m={p_1}^{a_1}{p_2}^{a_2}\cdots{p_n}^{a_n}$. We further define$P(m)=\{p_1,\cdots,p_n\}$.Use inclusion-exclusion principle we get

As$\frac{m}{M(S)}$is factor of$m$, let’s change the way we calculate$\sum_{d|m}\varphi(d)$to calculate the coefficient of factors of$m$.

Let$d$be one of factors of$m$. Then the coefficient of it will be

So we have

Since only when$d=m$satisfies$[P(\frac{m}{d})=\varnothing]=1$, otherwise it will be$0$. Thus we get$\sum_{d|m}\varphi(d)=m$.

Q. E. D.

### Solve using Combination Meanings

Let$d$be one of factors of$m$, consider the number of$x$that$(x,m)=d$. This is equal to the number of$x$that$d|x$and$(\frac{x}{d},\frac{m}{d})=1$. Replace the$\frac{x}{d}$by$x'$, we get$(x',\frac{m}{d})=1$. That just means the number of$x$that$x$and$\frac{m}{d}$is coprime, aka$\varphi(\frac{m}{d})$.

On the other hand,$\sum_{d|m}[(x,m)=d]=1$, thus we have

Q. E. D.

(2017ICPC) Given$T<10^{16}$, solve positive integer solution for

with$n>T$. (P21)

To solve this problem we first learn the concept of Pell’s Equation.

### Pell’s Equation I

We define$x^2-Dy^2=1$as the Pell$I$equation.$D$is a positive integer.

Theorem: The solution of Pell$I$equation exists. If the smallest solution is$(x_0,y_0)$, then the equation can be expressed as

So we can use recurrence to solve it.

### Pell’s Equation II

Similarly, we define$x^2-Dy^2=-1$as the Pell$II$equation.$D$is also a positive integer.

Theorem: The solution of Pell$II$equation exists. If the smallest solution is$(x_0,y_0)$, then the equation can be expressed as

Now let’s go back to the original problem.

Do some modification we can get

That is just a Pell$II$equation. So we can simply use binary search and algorithm similar to quick power to solve it.

Time complexity is$O(\log_2^2T)$.

## Ex 5 (Legendre Theorem)

Count the number of zeros at the end of$n!$. (P24)

Let$f(n,p)=\sum_{i\ge 1}\lfloor\frac{n}{p^i}\rfloor$denotes the power of$p$in$n$. The answer is$\min(f(n,2),f(n,5))$exactly.

Design an algorithm calculate the last nonzero digit of$n!$. (P24)

Let’s define$F(n)$denotes the last nonzero digit of$n!$. Consider recursion.

First we compute$1\times 2\times 3\times 4\bmod 10=4$and$6\times 7\times 8\times 9\bmod 10=4$. Thus we can divide the number into multiple of 5 or not.

Another observation is that$F(n)=F(n-n\bmod 10)F(n\bmod 10)$, it means we make the last a few numbers modulo to 10 so we get$F(n\bmod 10)$. Now we have

Notice that$F(x)=2F(x-5)$for$x\in[5,9]$, so we can make it.

F0 = [1,1,2,6,4,2,2,4,2,8]
def F(x):
return F0[x] if x<10 else F0[x%10]*F(x//5)%10*(4 if(x//10%2)else 6)%10

print(F(int(input())))

Time complexity is$O(\log_5n)$.

## Ex 6 (Lucas Theorem)

Calculate$G^{\sum_{d|n}\binom{n}{d}}\bmod 999911659$. (P26)

As we know the Euler Theorem we have

Because$999911658=2\times 3\times 4679\times 35617$, so we can simply apply Lucas Theorem and the Chinese Remainder Theorem to compute the answer.

Let$p=35617,P=999911659$, so the time complexity is$O(p+\log_pn+\log_2P)$.

Code

BZOJ2111: Too simple to solve it …

## Ex 7 (Mobius Function)

Prove that$\sum_{d|n}\mu(d)=[n=1]$. (P29)

When$n=1$, the equation is absolutely satisfied. Let’s say$n>1$.

According to the unique factorization theorem, we have

So we have

Q. E. D.

## Ex 8 (Prefix Sum Compute)

Let$f(n)$denotes the sum of all the factors of$n$, design an algorithm to calculate$\sum_{i=1}^n f(i)$,$n\le 10^{12}$. (P29)

We have

By number theory partition, we can compute it in$O(\sqrt{n})$.

Before starting solving problems, we learn the concept of Legendre symbol.

### Legendre symbol

Given$(m,n)=1$, if there exists$x$solves

then we define$n$as a quadratic residue.

Given$p$as a odd prime,$n$isn’t divisible by$p$. Then

The$\left( \frac{n}{p} \right)$is what we called Legendre symbol.

There’s a theorem given by Euler to help compute Legendre symbol:

Obviously, Legendre symbol is a multiplicative function.

It’s such a magic low:

Now let’s do some exercises.

Find$p$such that$\left( \frac{3}{p}\right)=1$. (P36)

According to quadratic reciprocal law we have

As we know$\left(\frac{1}{3}\right)=1,\left(\frac{2}{3}\right)=-1$, so we get

$p=12k+1,12k+11$.$p$should be a prime.

Find$p$such that$\left( \frac{5}{p}\right)=1$. (P36)

Similar to above. Skip.

Calculate$\left( \frac{74}{101}\right)$. (P36)

def Legendre(p,q):
p%=q
if p==0 : return 0
ans=-1
for i in range(1,q):
if(i*i%q==p):
ans=1
return ans

Just a joke. Obviously we should use quadratic reciprocal law to solve it. Python code:

def sig(x):
return 1-2*(x%2)

def Legendre(p,q): # q should be a prime
p1=p
q1=q
if p==2:
return sig((q*q-1)//8)
if p==0:
return 0
x=2
res=1
while x*x<=p:
if p%x==0:
t=Legendre(x,q) if x==2 else Legendre(q%x,x)*sig((x-1)*(q-1)//4)
while p%x==0:
res*=t
p//=x
if res==0:
return 0
x += 1
if p>1:
res*=Legendre(p,q) if p==2 else Legendre(q%p,p)*sig((p-1)*(q-1)//4)
return res

print(Legendre(int(input()),int(input())))

## Ex 10 (Exponential Congruence Equation)

First let’s learn some conclusion of exponential congruence equation.

Theorem: If$n$is not divisible by odd prime$p$, then the number of solutions of

is$(\frac{n}{p})+1$.

The number of solutions of

is$(k,p-1)$or$1$.

$x^k$takes$\frac{p-1}{(p-1,k)}$different values when$x$goes through a reduced residue system of$p$.

(MU training 2017) Let$p$be a prime number,$f(i)$be the number of solutions of

where$0<x<p,0<y<m+1$. Calculate

(P38)

First we have

if$p|y$, the equation always satisfies.

Otherwise$p\nmid y$, for a fixed$y$,$(1+x^{-1}y)$can goes through a reduced residue system of$p$. The number of solutions is$(i,p-1)$. So we have

Thus

Let’s define the last sum as$g$:

Concentrate on the latter part:

Thus

So we can use Min_25’s Sieve Method to compute$g(n)$in$O(\frac{n^{\frac{3}{4}}}{\log n})$.