Number theory: formulas
Pick a formula to see it explained with worked examples and a solver that shows every step.
About this topic
Number theory looks at whole numbers and their patterns: what divides what, prime numbers and remainders. On this page you will find 27 pages, such as Divisibility rule for 11, Pythagorean triples and Fibonacci: Cassini’s identity.
Every page has a solver that shows each step, examples to follow and the mistakes to avoid. Divisibility rule for 11 is a good place to start, or go back to Discrete maths and number theory.
Formulas in this topic
- Digit sum and divisibility by 9 and 3A number leaves the same remainder as its digit sum when divided by 9 (and by 3): N≡S(N)(mod9). So a number…
- Divisibility rule for 11A number is divisible by 11 exactly when its alternating digit sum (adding and subtracting the digits in…
- Legendre’s formula (powers of p in n!)The exponent of a prime p in n! is vp(n!)=⌊pn⌋+⌊p2n⌋+⌊p3n⌋+⋯
- Pythagorean triplesFor integers m>n>0, the numbers m2−n2, 2mn and m2+n2 form a Pythagorean triple: (m2−n2)2+(2mn)2=(m2+n2)2.
- Squares modulo 4 and 8Every perfect square leaves remainder 0 or 1 when divided by 4, and every odd square leaves remainder 1 when…
- Sum of two squares theoremA positive integer n is a sum of two squares, n=a2+b2, exactly when every prime q≡3(mod4) divides n to an…
- Fibonacci: Cassini’s identityFor the Fibonacci numbers 1,1,2,3,5,8,…, Cassini's identity says Fn+1Fn−1−Fn2=(−1)n.
- Fibonacci: sumThe sum of the first n Fibonacci numbers is one less than the number two places further on:…
- Fibonacci: gcdThe greatest common divisor of two Fibonacci numbers is the Fibonacci number at the gcd of the positions:…
- Pell equation recurrenceIf (x1,y1) is the smallest positive solution of x2−Dy2=1, all solutions come from…
- Euler's criterionFor an odd prime p and p∤a, Euler's criterion says (pa)≡a(p−1)/2(modp): a is a square modulo p (a quadratic…
- Quadratic reciprocityFor distinct odd primes p and q, (qp)(pq)=(−1)2p−1⋅2q−1. The two symbols are equal unless both primes are…
- Prime number theoremThe prime number theorem says that the number of primes up to x satisfies π(x)∼lnxx: the ratio of the two…
- Möbius inversionIf g(n)=∑d∣nf(d) for all n, then f(n)=∑d∣nμ(d)g(n/d), where μ is the Möbius function: μ(1)=1, μ(n)=(−1)k if…
- Elliptic curve group lawPoints on y2=x3+ax+b form a group. To add P1=(x1,y1) and P2=(x2,y2), take λ=x2−x1y2−y1 (for…
- Hasse’s bound and discriminantAn elliptic curve over Fp has #E(Fp) points with #E−(p+1)≤2p. The curve y2=x3+ax+b is non-singular…
- Euclidean algorithmThe Euclidean algorithm finds the greatest common divisor using gcd(a,b)=gcd(b, amodb): replace the pair by…
- Bézout identityBézout's identity says that for integers a,b (not both zero) there are integers x,y with ax+by=gcd(a,b). The…
- Linear congruenceThe congruence ax≡b(modn) has a solution if and only if gcd(a,n)∣b; when it does, there are exactly gcd(a,n)…
- Fermat's little theoremIf p is prime and p∤a, then ap−1≡1(modp). Equivalently, np≡n(modp) for every integer n.
- Euler's theorem and totientIf gcd(a,n)=1 then aφ(n)≡1(modn), where the totient φ(n)=n∏p∣n(1−p1) counts the integers from 1 to n that…
- Wilson's theoremWilson's theorem: for an integer p>1, (p−1)!≡−1(modp) if and only if p is prime.
- Chinese remainder theoremIf n1,…,nk are pairwise coprime, the system x≡ai(modni) has a solution, unique modulo N=n1n2⋯nk.
- Number of divisorsIf n=p1a1p2a2⋯pkak then n has τ(n)=(a1+1)(a2+1)⋯(ak+1) positive divisors.
- Sum of divisorsFor n=∏piai, the sum of all positive divisors is σ(n)=∏pi−1piai+1−1. A number is perfect when σ(n)=2n.
- RSARSA uses n=pq (two primes), a public exponent e coprime to φ(n)=(p−1)(q−1) and a private exponent d with…
- Mod, powers mod n, inverses and congruencesModular arithmetic works with remainders, like a clock. a mod n is the remainder when a is divided by n,…
Number theory questions
What is modular arithmetic?
It is arithmetic with remainders, like how a clock goes back to 1 after 12.
Can I try my own numbers?
Yes. Open any page, type your own question into the solver and it works it out step by step.