Number theory Pt II

The Return of Number Theory

We covered in the First part:

Primarily Test
Prime Factorisation
Sieve of Eratosthenes
Binary Exponentiation
Euclid's Algorithm for GCD
Number of divisors/sum of divisors
Segmented Sieve

We would cover:

Modulus Operations
Binomial Coefficients
Extended Euclidian Algorithm
Diophantine
Matrix Exponentiation
Fibonacci in O(log(n))
Chinese Remainder Theorem
Euler's Totient Function

And these are the methods which we would cover only in theory, no questions in the fight:

Pollard p-1
Pollard rho algorithm

Modulus Arithmetic:

Before jumping to the formulas for addition, subtraction, etc., firstly, let's have a look at what is Modular Congruence.

Modular Congruences:

a and b are modular congruent under n if they give the same remainder on dividing by n.

Representation: a ≡ b(mod n)

What that means is that wherever you are given a%n, you can replace it with b%n and it would have no impact no final answer, for example,

9=13 mod 4

(12+9)%4=21%4=1

(12+13)%4=25%4=1

With this, there is a great observation, we just made: a%n (remainder when a is divided by n) is always congruent to a under n! i.e.: a≡a%n(mod n).

Now, let's suppose, I ask you to compute (a*b)%n, which is quite simple, but if a and b are greater than 10^9, you can't store a*b in a long long int, so, we can safely replace a with a%n and b with b%n to get:

(a*b)%n=((a%n)*(b%n))%n

This is an essential property commonly used in many theorems; similarly, you can do the same in addition as well:

(a+b)%n=(a%n+b%n)%n

But when it comes to division, there is a different story.

But before moving to that, let's see a trick:

Finding the last digit of some big number*another big number:

123456*7890123

So, let's be clear on what exactly we want to find:

(a*b)%10 (last digit)

Now, things are already sorted: (a*b)%n=(a%n*b%n)%n

=(123456%10*7890123%10)%10=(6+3)%10=9

For seeing the proof of divisibility rule of 9 and 3 using modular arithmetic, click here.

Also, a-b≡0 mod n, I.e. a-b is divisible by n.

Modular Exponentiation:

If a≡b mod N. then

a^k≡b^k mod N

Again, using the observation that a=a%n mod N

(a^k)%n=((a%n)^k)%n

for eg, let's calculate (25^20)%12=((25%12)^20)%12=(1^20)%12=1

But wait, we can have something like (2^123456789)%7 also.

If you did It by the same approach, come on man, why would I make you do the same thing again, this time, you just replace 2 by 8 and divide 123456789 by 3. And 8%7=1. So whatever be the power, the answer is going to be one.

Simple enough?

Let's now jump to Modular inverse, the rules in division operation in modulus arithmetic:

Modulo Multiplicative Inverse

We can't just use (a/b)%c != (a%c/b%c)%c

But what we can do, is just replace / by *: (a*(1/b))%c

=(a%c*((1/b)%c))%c

What we need to find is now (1/b)%c

So, modulo multiplicative inverse of a number b under N is said to be x, if:

b*x≡1 mod p

And it can be a case where modulo inverse doesn't exist. If b and p are coprime to each other, then only modulo inverse exists. (GCD(b,p)=1)

So, how do we find modulo inverse?

Fermat's Little Theorem:

Fermat's little theorem states this equation:

a^m-1=1 mod m

a^m-2= a^-1 mod m

So, calculate a^m-2, and a^m-2 is the modulo inverse of a.

Caution: use binary exponentiation to calculate a^m-2, else you would get the time complexity as O(sqrt(n)).

Binomial Coefficients using Modulo Inverse:

Given q queries of type n k, you have to calculate C(n,k)%P, where p>n.(mostly p=10^9 + 7)

We know that,

C(n, k)= n!/[k!(n-k)!]

Questions:

...................................

Euler's Totient Function

Concept:

So, what's this fancy term actually mean?

This function returns the number of positive integers up to n which are coprime to n.

Fascinating, huh?

The naive solution is straightforward, and it's just a for loop up to n, and taking GCD of each i with n, a simple approach, time complexity: O(nlog(n))

Let's see in detail how this works:

Let F(n) be our Euler totient function.

Now there are these cases:

1. Case 1: If n is a prime number => If n is a prime number, the answer is just n-1. I don't think I have to explain that too. But still, a prime number is a number that has gcd equal to 1 with all numbers except for itself.

2. Case 2: If n is of the form P^x where P is a prime number. This is a bit tricky but still simple.

F(n)=P^x- number of integers not coprime with P^x.

And the numbers which are not coprime are those which are divisible by P. Eg, in 3^5, the number of integers divisible by 3 till 3^5, are 3^4=81. and 3^5=243.

Ans= 243-81+1=162.(+1 for 3^5 itself)

So, F(n)=P^x-P^(x-1)=(P^(x-1))*(P-1)

General Formula:

So, here is an interesting property of Euler's totient function: it is multiplicative. What that means is:

f(n*m)=f(n)*f(m)

So, your brain must be predicting what would happen next: we split N into its prime factorization form and just calculate the result! Every number is of the form P^x1*P^x3*P^x3

So, F(n)=F(p1^x1)*F(p2^x2)*....

=(P1^(x1-1))*(P1-1)*(P2^(x2-1))*(P2-1)....

But to calculate the prime factorization, you would take O(sqrt(n)) and calculate exponents, O(log(n)). And iterating through would take time O(number of prime divisors). So, you can transform the same formula to a much cleaner formula:

N*((P1-1)/p1)*((p2-1)/p2)*.....

So, just iterating through the prime factors, make time complexity: O(sqrt(n)).

Full Code Implementation:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int ans=n;
	for(int i=2;i<=sqrt(n);i++)
	{
		if(!(n%i))
		{
			ans*=(i-1);
			ans/=i;
			while(!(n%i))
				n/=i;
		}
	}	
	if(n>1)
	{
		ans*=(n-1);
		ans/=n;
	}
	cout<<"F(n): "<<ans<<"\n";
	return 0;
}

Examples:

Questions:

...................................

Competitive Coding

Search This Blog