---
# System prepended metadata

title: Untitled

---

## Basic Number Theoratic functions

- Floor 
- Ceiling

-----

## Divisors
- What does being a divisor means
- Properties of division operation
- Primes
- Prime Factorization

-----

## Prime Factorization
- Wheel optimization

-----

## Finding Divisors


-----

## Modulo

----

## Binary Exponentiation

-----

## Modular Division

----

## GCD


----

## Euclidean GCD

-----

## Extended Euclidean Algorithm

----

## LCM


----

## Euler Totient Function 

----

## Chinese Reminder Theorem


----

## Tricks

- Computing all factorials upto n in O(n)
- Computing all inverse factorials up to n in O(n)



-----
## Resources
- [Slides](https://docs.google.com/presentation/d/1W-9cgYKU5tmIWC_KViemBunD1EB2ltXKDbo7EFkMun0/edit#slide=id.gf1f4080e95_1_14)
- [Sieve](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html)
- [GCD](https://cp-algorithms.com/algebra/euclid-algorithm.html)
- [Extended Euclidean Algorithm](https://cp-algorithms.com/algebra/extended-euclid-algorithm.html)
- [Integer Factorization](https://cp-algorithms.com/algebra/factorization.html#wheel-factorization)
- [Euler Toteint Function](https://cp-algorithms.com/algebra/phi-function.html)
- [Number and Sum of divisors](https://cp-algorithms.com/algebra/divisors.html)
- [Blog on NT in CP](https://discuss.codechef.com/t/guide-to-modular-arithmetic-plus-tricks-codechef-edition-there-is-no-other-edition/67424)
- [Factorization](https://cp-algorithms.com/algebra/factorization.html)
- [Template](https://pastebin.com/60eNkTNj)