# Number Theory
1. Basic Questions
2. FIbbnacci
3. Bitmasking
4. Prime Numbers
5. Gcd & Lcm
6. Euler Tutoinent
7. Binary Exponention
8. Modulo Inverse
9. Combinations
10. Number of Intergral Solutions
## 1. Basic Questions
> Sum of squares of first N natural number
Factorial of a Number
Trailing Zeroes in Factorial
Maximum Power Dividing Factorial
## 2. Fibbnaci
> Normal FIbbnaci
Matrix exponention Fibnacci
Sum of N Fibbnaci is is Fib[n+2]-1
## 3. Bitmasking
> Power Set (IMP.)
Two Missing Numbers Link
## 4. Prime Numbers
> Sieve of Erathoneses
Segemented Seive
Prime Factorization Of Number
Count , Sum , Product Of Divisors
## 5. GCD & LCM
> Gcd Eucledian Algo (gcd(a,b))
LDE (Linear Diophanite Equation ) :- ax + by = c; positive or negative value of x and y exist only and only if c%(gcd(a,b))==0;
Extended Euclid Algo :- It basicaly give the value of x and y also if ax+by=__gcd(a,b)
## 6. Euler Tointent
> phi(n) is count of 1 to n-1 where __gcd(i,n)==1
phi(n) if n is prime n-1
phi(n) if n has only one prime factor like 2^3 then p^k - p^k-1
phi(n) is prime factorization then it has multiplicatiive property (p1^k1 - p1^k1-
1)*(p2^k2-p2^k2-1)
## 7. Binary Exponention
## 8. Module Inverse (IMP)
> modulo inverse is that no. example modulo of a in a*x mod m=1 then here x is modulo inverse of a ;
Modulo inverse can only be find if a and m are coprime
There are mainly 3 ways to find :-
> Extended Euclid Basically ax+by=gcd(a,b) then if if(gcd(a,b) is 1 then x is modulo inverse of a (Most Optimized )
Euler theorem it states that a^phi(m)mod m =1 condition is a and m is coprime
then a^(phi(m)-1) is modulo inverse
Fermat Little Theorem states that a ^ m =amodm where m is prime then by using it we can find modulo inverse and then inverse is a ^ m-2 condition is m is prime and a is not multipe of m mainly gcd(a,m)==1
> Euler Theorem Basic Question
1. what is last digit of 7 ^ 1002 ?
2. what is value of 2^1000 mod 13 ?
3. what is of 5 ^ 99 mod 13 ?
## 9. Combination
```//nCr
#include
using namespace std;
#define ll long long int
int fact[100005];
int mod = int (1e9 + 7);
int powerArray[100005];
void preCompute() {
fact[0] = 1;
for (int i = 1; i < 100005; i++){
fact[i] = i * fact[i - 1] % mod;
powerArray[i]=power(fact[i], mod - 2, mod);
}
}
int power(int base, int n, int mod) {
int ans = 1;
while (n) {
if (n % 2) {
n = n - 1;
ans = (ans * base) % mod;
}
else {
n = n / 2;
base = (base * base) % mod;
}
}
return ans;
}
void nCr(int n, int r) {
//return fact[n]/fact[n-r]*fact[r]; SimpleWay
//return (fact[n] * power(fact[r], mod - 2, mod) * power(fact[n - r], mod - 2, mod)) % mod; // Fermat Little Theorem
return fact[n]*powerArray[r]*powerArray[n-r] %mod ; // Premoute powerArray
}
int main() {
int n, r;
cin >> n >> r;
cout << nCr(n, r);
}
```
## 11 Number of Integral Solution
>https://www.youtube.com/watch?v=6y20cowA3s8
>https://www.geeksforgeeks.org/number-of-integral-solutions-of-the-equation-x1-x2-xn-k/
>Number of non-negative integral solutions of equation x1 + x2 +…+ xn = k is equal to the number of ways in which k identical balls can be distributed into N unique boxes.
n+k-1 C k-1
Number of positive integral solutions of equation x1 + x2 + … + xn = k is equal to the number of ways in which k identical balls can be distributed into N unique boxes such that each box must contain at-least 1 ball.
## 12. Catalan Numbers
> 2nCn/n+1
sigma of 1 to n C(n-i)*C(i-1)
in second line C is Catalan number
## 13. Chicken McNugget Theorem
> The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers m,n, the greatest integer that cannot be written in the form am + bn for nonnegative integers a, b is mn-m-n.
A consequence of the theorem is that there are exactly {(m - 1)(n - 1)}/{2} positive integers which cannot be expressed in the form am + bn.
Link