📌 Basic Properties

Sum of First \( n \) Naturals:

\( S = \frac{n(n+1)}{2} \)

Sum of Squares:

\( S = \frac{n(n+1)(2n+1)}{6} \)

Sum of Cubes:

\( S = \left( \frac{n(n+1)}{2} \right)^2 \)

Even Number:

\( n = 2k \)

Odd Number:

\( n = 2k + 1 \)

Factorial:

\( n! = n \cdot (n-1) \cdot \ldots \cdot 1 \)

Binomial Coefficient:

\( \binom{n}{k} = \frac{n!}{k!(n-k)!} \)

Pascal’s Identity:

\( \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \)

Sum of Binomial Coefficients:

\( \sum_{k=0}^{n} \binom{n}{k} = 2^n \)

Alternating Binomial Sum:

\( \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \)

📌 Divisibility

Divisibility by 2:

Last digit is 0, 2, 4, 6, 8

Divisibility by 3:

Sum of digits is divisible by 3

Divisibility by 4:

Last two digits form a number divisible by 4

Divisibility by 5:

Last digit is 0 or 5

Divisibility by 6:

Number is divisible by both 2 and 3

Divisibility by 9:

Sum of digits is divisible by 9

Divisibility by 11:

Alternating sum of digits is divisible by 11

Remainder Definition:

\( a = bq + r \), where \( 0 \leq r < b \)

Division Algorithm:

For \( a, b \in \mathbb{Z}, b > 0 \), \( \exists q, r \) such that \( a = bq + r \)

Divisor Property:

If \( a | b \) and \( b | c \), then \( a | c \)

📌 Prime Numbers

Prime Definition:

\( p > 1 \) with only divisors 1 and \( p \)

Composite Definition:

\( n > 1 \) and \( n = ab \), where \( 1 < a, b < n \)

Fundamental Theorem of Arithmetic:

\( n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \) (unique factorization)

Number of Divisors:

\( d(n) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1) \)

Sum of Divisors:

\( \sigma(n) = (1 + p_1 + \cdots + p_1^{e_1})(1 + p_2 + \cdots + p_2^{e_2}) \cdots \)

Euclid’s Theorem:

There are infinitely many primes

Sieve of Eratosthenes:

Mark multiples of each prime up to \( \sqrt{n} \)

Prime Number Theorem (Approximation):

\( \pi(x) \approx \frac{x}{\ln x} \)

Twin Prime Conjecture:

Infinite pairs \( (p, p+2) \) both prime (unproven)

Goldbach Conjecture:

Every even \( n > 2 \) is sum of two primes (unproven)

📌 GCD and LCM

GCD Definition:

\( \gcd(a, b) = \max \{ d : d | a \text{ and } d | b \} \)

LCM Definition:

\( lcm(a, b) = \min \{ m : a | m \text{ and } b | m \} \)

GCD-LCM Relationship:

\( \gcd(a, b) \cdot lcm(a, b) = a \cdot b \)

Euclidean Algorithm:

\( \gcd(a, b) = \gcd(b, a \mod b) \)

Bézout’s Identity:

\( \gcd(a, b) = ax + by \) for some integers \( x, y \)

Coprime Property:

\( \gcd(a, b) = 1 \) if no common factors other than 1

GCD of Multiple Numbers:

\( \gcd(a, b, c) = \gcd(\gcd(a, b), c) \)

LCM of Multiple Numbers:

\( lcm(a, b, c) = lcm(lcm(a, b), c) \)

GCD with Prime Factorization:

\( \gcd(a, b) = p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \cdots \)

LCM with Prime Factorization:

\( lcm(a, b) = p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \cdots \)

📌 Modular Arithmetic

Congruence:

\( a \equiv b \pmod{m} \) if \( m | (a - b) \)

Modular Addition:

\( (a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m \)

Modular Multiplication:

\( (a \cdot b) \mod m = [(a \mod m) \cdot (b \mod m)] \mod m \)

Modular Exponentiation:

\( a^n \mod m \) (computed via repeated squaring)

Fermat’s Little Theorem:

\( a^{p-1} \equiv 1 \pmod{p} \) if \( p \) is prime, \( p \nmid a \)

Euler’s Theorem:

\( a^{\phi(m)} \equiv 1 \pmod{m} \) if \( \gcd(a, m) = 1 \)

Chinese Remainder Theorem:

Unique \( x \pmod{m_1 m_2} \) for \( x \equiv a_1 \pmod{m_1}, x \equiv a_2 \pmod{m_2} \) if \( \gcd(m_1, m_2) = 1 \)

Inverse Modulo \( m \):

\( a \cdot a^{-1} \equiv 1 \pmod{m} \) if \( \gcd(a, m) = 1 \)

Wilson’s Theorem:

\( (p-1)! \equiv -1 \pmod{p} \) if \( p \) is prime

Carmichael Function:

\( \lambda(m) = lcm(\phi(p_1^{e_1}), \phi(p_2^{e_2}), \ldots) \)

📌 Diophantine Equations

Linear Diophantine Equation:

\( ax + by = c \) solvable if \( \gcd(a, b) | c \)

General Solution (Linear):

\( x = x_0 + \frac{b}{\gcd(a, b)} k, \, y = y_0 - \frac{a}{\gcd(a, b)} k \)

Pell’s Equation:

\( x^2 - d y^2 = 1 \) (solve for fundamental solution)

Fermat’s Last Theorem:

\( a^n + b^n = c^n \) has no solutions for \( n > 2 \) (proven)

Pythagorean Triple:

\( a^2 + b^2 = c^2 \), e.g., \( a = m^2 - n^2, b = 2mn, c = m^2 + n^2 \)

Sum of Two Squares:

\( n = a^2 + b^2 \) if prime factors \( p \equiv 3 \pmod{4} \) have even exponents

Sum of Four Squares:

Every \( n \geq 0 \) is \( a^2 + b^2 + c^2 + d^2 \) (Lagrange’s Theorem)

Congruent Number Equation:

\( y^2 = x^3 - n^2 x \) for rational points

Partition Function:

\( p(n) \) = number of ways to write \( n \) as sum of positive integers

Euler’s Pentagonal Number Theorem:

\( p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + \cdots \)

📌 Number-Theoretic Functions

Euler’s Totient Function:

\( \phi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right) \)

Multiplicative Property of \( \phi \):

\( \phi(mn) = \phi(m) \phi(n) \) if \( \gcd(m, n) = 1 \)

Sum of Totients:

\( \sum_{d|n} \phi(d) = n \)

Möbius Function:

\( \mu(n) = \begin{cases} 1 & \text{if } n \text{ is square-free, even # of primes} \\ -1 & \text{if square-free, odd # of primes} \\ 0 & \text{if not square-free} \end{cases} \)

Möbius Inversion Formula:

\( f(n) = \sum_{d|n} g(d) \implies g(n) = \sum_{d|n} \mu(d) f\left(\frac{n}{d}\right) \)

Divisor Function \( \sigma_k(n) \):

\( \sigma_k(n) = \sum_{d|n} d^k \)

Perfect Number:

\( \sigma(n) = 2n \) (e.g., 6, 28)

Abundant Number:

\( \sigma(n) > 2n \)

Deficient Number:

\( \sigma(n) < 2n \)

Liouville Function:

\( \lambda(n) = (-1)^{\Omega(n)} \), where \( \Omega(n) \) is total # of prime factors

📌 Sequences and Series

Fibonacci Sequence:

\( F_n = F_{n-1} + F_{n-2} \), \( F_0 = 0, F_1 = 1 \)

Binet’s Formula:

\( F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}} \), where \( \phi = \frac{1 + \sqrt{5}}{2} \)

Lucas Numbers:

\( L_n = F_{n-1} + F_{n+1} \)

Arithmetic Sequence:

\( a_n = a_1 + (n-1)d \)

Sum of Arithmetic Sequence:

\( S_n = \frac{n}{2} (a_1 + a_n) \)

Geometric Sequence:

\( a_n = a_1 r^{n-1} \)

Sum of Geometric Sequence:

\( S_n = a_1 \frac{1 - r^n}{1 - r} \), \( r \neq 1 \)

Infinite Geometric Sum:

\( S = \frac{a_1}{1 - r} \), \( |r| < 1 \)

Harmonic Number:

\( H_n = \sum_{k=1}^{n} \frac{1}{k} \)

Triangular Number:

\( T_n = \frac{n(n+1)}{2} \)

📌 Analytic Number Theory

Riemann Zeta Function:

\( \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_p \left(1 - \frac{1}{p^s}\right)^{-1} \)

Euler Product Formula:

\( \zeta(s) = \prod_{p \text{ prime}} \left(1 - p^{-s}\right)^{-1} \)

Special Value \( \zeta(2) \):

\( \zeta(2) = \frac{\pi^2}{6} \)

Special Value \( \zeta(4) \):

\( \zeta(4) = \frac{\pi^4}{90} \)

Dirichlet Beta Function:

\( \beta(s) = \sum_{n=0}^{\infty} \frac{(-1)^n}{(2n+1)^s} \)

Prime Counting Function:

\( \pi(x) = \sum_{p \leq x} 1 \)

Logarithmic Integral (Prime Approximation):

\( \pi(x) \approx \text{li}(x) = \int_2^x \frac{dt}{\ln t} \)

Mangoldt Function:

\( \Lambda(n) = \begin{cases} \ln p & \text{if } n = p^k \\ 0 & \text{otherwise} \end{cases} \)

Chebyshev Function:

\( \psi(x) = \sum_{n \leq x} \Lambda(n) \approx x \)

Riemann Hypothesis (Critical Line):

Non-trivial zeros of \( \zeta(s) \) at \( \text{Re}(s) = \frac{1}{2} \) (unproven)