Search Results

25 results for “number theory”

Formulae (25)

Euclidean Algorithm

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

Recursively finds the greatest common divisor.

Number TheoryBasic

Modular Congruence

a \equiv b \pmod{m}

a and b have the same remainder when divided by m.

Number TheoryAdvanced

Fermat's Little Theorem

a^{p-1} \equiv 1 \pmod{p}

Holds when p is prime and gcd(a,p)=1.

Number TheoryAdvanced

Euler's Totient

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

Counts integers up to n coprime to n.

Number TheoryAdvanced

Prime Number Theorem

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

Approximates the number of primes below x.

Number TheoryBasic

LCM from GCD

\text{lcm}(a,b) = \frac{|a b|}{\gcd(a,b)}

Least common multiple via the greatest common divisor.

Number TheoryBasic

Sum of First n Integers

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

Closed form for the sum of the first n natural numbers.

Number TheoryIntermediate

Sum of First n Squares

\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}

Closed form for the sum of the first n squares.

Number TheoryBasic

Divisibility Rule for 3

n \text{ divisible by } 3 \iff \text{digit sum divisible by } 3

A number is divisible by 3 if the sum of its digits is.

Number TheoryBasic

Divisibility Rule for 9

n \text{ divisible by } 9 \iff \text{digit sum divisible by } 9

A number is divisible by 9 if the sum of its digits is.

Number TheoryBasic

Even and Odd Numbers

n = 2k \;(\text{even}), \quad n = 2k+1 \;(\text{odd})

Every integer is either even or odd.

Number TheoryIntermediate

Sum of First n Cubes

\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2

The sum of the first n cubes equals the square of the sum.

Number TheoryAdvanced

Number of Divisors

d(n) = \prod (a_i + 1)

Count of divisors from prime factorization exponents.

Number TheoryAdvanced

Sum of Divisors

\sigma(n) = \prod \frac{p_i^{a_i+1}-1}{p_i - 1}

Sum of all divisors from prime factorization.

Number TheoryAdvanced

Even Perfect Number

N = 2^{p-1}(2^p - 1)

Euclid-Euler form of even perfect numbers.

Number TheoryIntermediate

Mersenne Number

M_p = 2^p - 1

Numbers one less than a power of two.

Number TheoryAdvanced

Fermat Number

F_n = 2^{2^n} + 1

Numbers of a special exponential form.

Number TheoryBasic

Triangular Number

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

Sum of the first n natural numbers.

Number TheoryBasic

Square Number

S_n = n^2

The nth perfect square.

Number TheoryIntermediate

Pentagonal Number

P_n = \frac{n(3n-1)}{2}

The nth pentagonal figurate number.

Number TheoryBasic

Fibonacci Recurrence

F_n = F_{n-1} + F_{n-2}

Each term is the sum of the two before it.

Number TheoryAdvanced

Binet Formula

F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}

Closed form for the nth Fibonacci number.

Number TheoryIntermediate

Golden Ratio

\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618

Ratio where the whole is to the larger as the larger is to the smaller.

Number TheoryIntermediate

Collatz Step

n \to \begin{cases} n/2 & \text{even} \\ 3n+1 & \text{odd} \end{cases}

The rule of the famous unsolved Collatz conjecture.

Number TheoryAdvanced

Wilson Theorem

(p-1)! \equiv -1 \pmod{p}

A primality criterion for p.