# Mathematics For Competitive Programming

Hello guys,

I am writing about most of the mathematics topics involved in competitive Programming.

GCD (Greatest Common Divisor)
→ Properties of GCD
→ Brute Force and Euclidean algorithm to compute GCD
→ Analysis of Euclidean algorithm

Modular Arithmetic
→ Basic properties of modulo
→ proof of condition for inverse modulo to exist
->Modulo inverse using extended euclidean algorithm with proof
→ Modulo inverse using Fermat’s theorem
→ Solution of Modulo inverse of all integers less than m

Prime Numbers
→ Properties of prime
→ Wilson’s theorem
→ School method for primality testing
→ Fermat’s theorem and its drawbacks
→ Miller-Rabin test with proof
→ Why Miller-Rabin is better
→ Deterministic version of Miller-Rabin
→ Seive of Eratosthenes

Prime Factors
→ Properties of Prime Factors
→ Proof of Number of divisors
→ Trial Division Method for Prime Factors
→ Optimization for trial Division method
O(N^{1/3}) algorithm for calculating number of divisors
→ Logarithmic Prime Factorisation Using Seive

Star and Bars - Combinatorics(Latest Post)
→ Star and Bars theorem with proof
→ Number of non-negative integer sum
→ Number of lower bound integer sum
→ Coefficient of x^n in (1-x)^{-k}

Combinatorics (coming soon)

Probability (coming soon)

Geometry (coming soon)

Miscellaneous topics (coming soon)

Thank you and Happy Coding

16 Likes

in part 1- you have included only the most general part there is a more in that topic like gcd in an interval and relations btw gcd and lcm.

1 Like

Thanks for the suggestion! I thought relation between gcd and lcm was trivial and I didn’t thought of gcd in an interval. I will add both of them very soon

1 Like

good boi XDXD

1 Like