Arturia's Math Lesson Day 1

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

$$x=\prod_{p\text{ is prime}}p^{f(x,p)}$$

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

$$\begin{aligned} f(dm,p) &=f(d,p)+f(m,p)\\ &=\min(f(a,p),f(b,p))+\max(f(a,p),f(b,p))\\ &=f(a,p)+f(b,p)\\ &=f(ab,p) \end{aligned}$$

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

$$\sum_{d|m}\varphi(d)=m$$

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

$$\begin{aligned} \varphi(m)&=m\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_n}\right)\\ &=\sum_{S\subseteq P(m)}(-1)^{|S|}\frac{m}{M(S)} \end{aligned}$$

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

$$\sum_{S\subseteq P(\frac{m}{d})}(-1)^{|S|}=\left[P\left(\frac{m}{d}\right)=\varnothing\right]$$

So we have

$$\sum_{d|m}\varphi(d)=\sum_{d|m}\left[P\left(\frac{m}{d}\right)=\varnothing\right]d$$

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

$$m=\sum_{i=1}^m\sum_{d|m}[(i,m)=d]=\sum_{d|m}\varphi\left(\frac{m}{d}\right)=\sum_{d|m}\varphi(d)$$

Q. E. D.

Ex 4 (Quadratic Equation)

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

$$n(n+1)=2m(m+1)$$

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

$$x_n+\sqrt{D}y_n=(x_0+\sqrt{D}y_0)^n$$

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

$$x_n+\sqrt{D}y_n=(x_0+\sqrt{D}y_0)^{2n+1}$$

Now let’s go back to the original problem.

Do some modification we can get

$$(2n+1)^2-2(2m+1)^2=-1$$

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

$$F(n)=4^{2\lfloor\frac{n}{10}\rfloor}F(n\bmod 10)F\left(\left\lfloor\frac{n}{5}\right\rfloor\right)\frac{1+[(n\bmod 10)\ge 5]}{2^{\lfloor\frac{n}{5}\rfloor}}\\ =4^{\lfloor\frac{n}{10}\rfloor}F(n\bmod 10)F\left(\left\lfloor\frac{n}{5}\right\rfloor\right)$$

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

$$G^{\sum_{d|n}\binom{n}{d}}\equiv G^{\sum_{d|n}\binom{n}{d}\bmod 999911658} \pmod {999911659}$$

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

$$n={p_1}^{a_1}{p_2}^{a_2}\cdots{p_m}^{a_m}$$

So we have

$$\begin{aligned} \sum_{d|n}\mu(d)&=\sum_{S\subseteq\{p_1,p_2,\cdots,p_n\}}\mu\left(\prod_{x\in S}x\right)\\ &=\sum_{S\subseteq\{p_1,p_2,\cdots,p_n\}}(-1)^{|S|}\\ &=0 \end{aligned}$$

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

$$\sum_{i=1}^nf(i)=\sum_{i=1}^n\sum_{j|i}j=\sum_{j=1}^nj\left\lfloor\frac{n}{j}\right\rfloor$$

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

Ex 9 (Quadratic Residue)

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

Legendre symbol

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

$$x^2=m\mod m$$

then we define$n$as a quadratic residue.

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

$$\left( \frac{n}{p} \right)=\begin{cases} 1 & n\text{ is a quadratic residue}\\ -1 & \text{Otherwise} \end{cases}$$

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

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

$$n^{\frac{p-1}{2}}=\left( \frac{n}{p} \right) \mod p$$

Obviously, Legendre symbol is a multiplicative function.

Quadratic Reciprocal Law

It’s such a magic low:

$$\left( \frac{p}{q} \right)\left( \frac{q}{p} \right)=(-1)^{\frac{(p-1)(q-1)}{4}}$$

Now let’s do some exercises.

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

According to quadratic reciprocal law we have

$$\left( \frac{p}{3}\right)=(-1)^{\frac{p-1}{2}}$$

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

$$\begin{cases} p\bmod 3=1\\ p\bmod 2=1\\ \frac{p-1}{2}\bmod 2=0 \end{cases} \text{ or } \begin{cases} p\bmod 3=2\\ p\bmod 2=1\\ \frac{p-1}{2}\bmod 2=1 \end{cases}$$

$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

$$x^2=n\mod p^l$$

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

The number of solutions of

$$x^k=1\mod p$$

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

$$(x+y)^i=x^i\mod p$$

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

$$\sum_{i=1}^{p-1}i\times f(i) \mod {10^9+7}$$

(P38)

First we have

$$(1+x^{-1}y)^i=1\mod p$$

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

$$f(i)=\left\lfloor\frac{m}{p}\right\rfloor(p-1)+\left(m-\left\lfloor\frac{m}{p}\right\rfloor\right)(i,p-1)$$

Thus

$$\sum_{i=1}^{p-1}i\times f(i) =\frac{p(p-1)}{2}\left\lfloor\frac{m}{p}\right\rfloor(p-1) + \left(m-\left\lfloor\frac{m}{p}\right\rfloor\right)\sum_{i=1}^{p-1}i (i,p-1)$$

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

$$\begin{aligned} g(n)&=\sum_{i=1}^ni(i,n)\\ &=n^2+\frac{1}{2}\sum_{i=1}^{n-1}i(i,n)+(n-i)(n-i,n)\\ &=n^2+\frac{1}{2}n\sum_{i=1}^{n-1}(i,n)\\ &=n^2+\frac{1}{2}n\sum_{i=1}^{n-1}\sum_{d|i,d|n}\varphi(d) \end{aligned}$$

Concentrate on the latter part:

$$\begin{aligned} &\sum_{i=1}^{n-1}\sum_{d|i,d|n}\varphi(d)\\ =&\sum_{d|n}\varphi (d) \left(\frac{n}{d}-1\right)\\ =&\sum_{d|n}\varphi (d) \frac{n}{d}-n \end{aligned}$$

Thus

$$\begin{aligned} g(n)&=n^2+\frac{1}{2}n\sum_{i=1}^{n-1}\sum_{d|i,d|n}\varphi(d)\\ &=\frac{1}{2}n^2+\frac{1}{2}n\sum_{d|n}\varphi (d) \frac{n}{d} \end{aligned}$$

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