Ex 1 (The Unique Factorization Theorem)

Prove that,. (P5)

First, to be obvious, for all, we have.

Letdenotes the largestthat. According to the unique factorization theorem, we have

Let’s consider a prime factorof.

To be exactly,.

Let, so we have, becauseandshould both be divisible by. Also we want to maximize, so we try to maximize the power ofin. That is equal to.

Similarly, Let, so we have.

So when we multiplyand, we will get

Finally.

Q. E. D.

Ex 2 (Diophantine Equation)

Given that, find the largestthat makesunsolvable. (P6)

Answer:.

Ex 3 (Module)

Euler Function: Prove that

through direct calculation or combination meanings. (P13)

Solve using Direct Calculation

Let.

Use the unique factorization theorem, Let. We further define.Use inclusion-exclusion principle we get

Asis factor of, let’s change the way we calculateto calculate the coefficient of factors of.

Letbe one of factors of. Then the coefficient of it will be

So we have

Since only whensatisfies, otherwise it will be. Thus we get.

Q. E. D.

Solve using Combination Meanings

Letbe one of factors of, consider the number ofthat. This is equal to the number ofthatand. Replace theby, we get. That just means the number ofthatandis coprime, aka.

On the other hand,, thus we have

Q. E. D.

Ex 4 (Quadratic Equation)

(2017ICPC) Given, solve positive integer solution for

with. (P21)

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

Pell’s Equation I

We defineas the Pellequation.is a positive integer.

Theorem: The solution of Pellequation exists. If the smallest solution is, then the equation can be expressed as

So we can use recurrence to solve it.

Pell’s Equation II

Similarly, we defineas the Pellequation.is also a positive integer.

Theorem: The solution of Pellequation exists. If the smallest solution is, 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 Pellequation. So we can simply use binary search and algorithm similar to quick power to solve it.

Time complexity is.

Ex 5 (Legendre Theorem)

Count the number of zeros at the end of. (P24)

Letdenotes the power ofin. The answer isexactly.

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

Let’s definedenotes the last nonzero digit of. Consider recursion.

First we computeand. Thus we can divide the number into multiple of 5 or not.

Another observation is that, it means we make the last a few numbers modulo to 10 so we get. Now we have

Notice thatfor, 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.

Ex 6 (Lucas Theorem)

Calculate. (P26)

As we know the Euler Theorem we have

Because, so we can simply apply Lucas Theorem and the Chinese Remainder Theorem to compute the answer.

Let, so the time complexity is.

Code

BZOJ2111: Too simple to solve it …

Ex 7 (Mobius Function)

Prove that. (P29)

When, the equation is absolutely satisfied. Let’s say.

According to the unique factorization theorem, we have

So we have

Q. E. D.

Ex 8 (Prefix Sum Compute)

Letdenotes the sum of all the factors of, design an algorithm to calculate,. (P29)

We have

By number theory partition, we can compute it in.

Ex 9 (Quadratic Residue)

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

Legendre symbol

Given, if there existssolves

then we defineas a quadratic residue.

Givenas a odd prime,isn’t divisible by. Then

Theis what we called Legendre symbol.

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

Obviously, Legendre symbol is a multiplicative function.

Quadratic Reciprocal Law

It’s such a magic low:

Now let’s do some exercises.

Findsuch that. (P36)

According to quadratic reciprocal law we have

As we know, so we get

.should be a prime.

Findsuch that. (P36)

Similar to above. Skip.

Calculate. (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: Ifis not divisible by odd prime, then the number of solutions of

is.

The number of solutions of

isor.

takesdifferent values whengoes through a reduced residue system of.

(MU training 2017) Letbe a prime number,be the number of solutions of

where. Calculate

(P38)

First we have

if, the equation always satisfies.

Otherwise, for a fixed,can goes through a reduced residue system of. The number of solutions is. So we have

Thus

Let’s define the last sum as:

Concentrate on the latter part:

Thus

So we can use Min_25’s Sieve Method to computein.