`Hello codeforces community`

`course updated : 21 May 2020`

```
I have working on Number Theory course which is beginner/Intermediate friendly.The course emphasizes on learning by doing methodology.
After teaching an algorithm/technique and showing how it is implemented we take example practice problems from judges like Codeforces , Codechef , Spoj etc and teach how this algorithm is used in different scenario and how it can be used to solve the problem.
```

```
Here is the list of lecture from the course (I will be uploading more lectures soon)
```

## Number Theory Lectures

- L00 : Course Overview
- L01 : Primality Test in O(sqrt(N)) Time
- E01 : Primality Test (Codechef) | Practice Problem
- L02 : Sieve of Eratosthenes
- E02 : Finding the kth prime (SPOJ) | Practice Problem
- L03 : Prime Factorization in O(sqrt(N)) Time
- L04 : Binary Exponentiation
- E03 : Prime Interval (Hackerearth) | Practice Problem
- E04 : Micro and Prime Prime (Hackerearth) | Practice Problem
- L05 : Prime Factorization using Sieve in O(log(N)) Time
- L06 : Matrix Exponentiation with Problem explanation (MPOW : SPOJ)
- L07 : Finding Nth element of recurrence relation in O(log(N)) Time
- E05 : Fibonacci Finding (HackerRank) | Practice Problem
- L08 : Euclid Algorithm for GCD and Introduction to Modular Arithmetic
- E06 : GCD Queries (Codechef) | Practice Problem
- L09 : modular Arithmetic Part 1
- L10 : Modular Arithmetic Part 2
- E07 : Arpa's Hard exam and Mehardad's Naive Cheat (Codeforces) | Practice Problem
- E08 : Modular GCD (Codechef) | Practice Problem
- L11 : Modulo Multiplicative Inverse
- L12 : Finding Modulo inverse using Fermat's Little Theorem
- L13 : calculating Total Number of divisors from prime factorization
- L14 : Calculating Binomial Coefficient % prime using modulo inverse
- L15 : Euler's Totient Function
- L16 : Euler's Totient Function (Part 2)
- L17 : Calculating Phi(N) in O(sqrt(N))
- L18 : Calculating Phi() from 1 to N in O(Nlog(logN)) Time using Sieve
- L19 : Euler's Totient Function and GCD Sum
- L20 : Euler's Totient Function and GCD Sum (Part 2)
- L21 : Segmented Sieve Introduction (Lecture added : 17 May 2020)
- E09 : Prime Generator (Spoj) | Practice Problem (added : 21 May 2020)

```
Any suggestion or criticism is welcome.
Thank you for your valuable time.
PS : Ignore any grammatical mistake as we ignore compiler warnings (My English is not very good)
```

Thanks a ton! I was being looking for that...are there any more topics left?

yes there are many topics I will add , like Chinese remainder theorem

Please add the Chinese remainder theorem too. Really appreciate your work!!

I have watched graph theory course of yours. It's wonderful. Thanks buddy!!

WOW!!! UPVOTED. I was looking for this. Many many thanks from me.

Chinese remiander theorm

3.A) Derivation of number a which satisfies given crt properties. Suppose we have set of numbers relatively prime with each other eg 3 4 5 and there is a number a: a mod 3 = 2 mod 3 a mod 4 = 2 mod 4 a mod 5 = 1 mod 5

a = 4*5 3*5 3*4

4*5 and 3, 3*5 and 4, 3*4 and 5 are co-prime with each other

Recalling 2 Algorithms: 1) fermats little theorm for inverrse modulo,a and p are co-prime and p is also a prime a^(p-1) == 1 mod p : taking 1/p both sides => a^(p-2) == 1/a mod p which means a^(p-2)%p is the inverse of a wrtx m

2) Extended euclidean algo

now 4*5%3 = 2 hence as the given condition (a mod 3 = 2 mod 3) also satisfies , now action is to be taken now 3*5%4 = 3 hence , as the given condition says it has to be (a mod 4 = 2 mod 4), we first find the modulo inverse of 3*5%4 wrtx 4 i.e invserse of 3 wrtx mod 4, as 3 and 4 are co prime , but 4 is not a prime , hence using extended euclidean algo , we get 3 as modular inverse of 3 wrtx 4. hence 3*5 is multiplied by 3 firstly and then by 2 such that 3*5 * (3 which is mod inverse) *2 ==2 mod 4 now 3*4 mod 5 = 2 mod 5 , using fermat theorm , we get 2^(3)%5 = 3 as mod inverse of 2 wrtx 5, hence multiply 3*4 by 3 for == 1 mod 5

hence the final answer is 3 4 5 a = 4*5 3*5*3*2 3*4*3

hence a is 4*5 + 3*5*3*2 + 3*4*3 = 146 or 146+n*(3*4*5) = 146+n*60