Computer Science · Data Sheet

Number Theory and Graph Theory Cheat Sheet

Symbol	Constant	Value	Unit
C	Chinese remainder congruences	C congruent r_i (mod m_i), with pairwise coprime moduli	formula
phi(n)	Euler totient from factorization	If n=product p_i^e_i, phi(n)=product p_i^(e_i-1)(p_i-1)	formula
a^phi(n)	Euler theorem	a^phi(n) congruent 1 (mod n) when gcd(a,n)=1	formula
a^(p-1)	Fermat little theorem	a^(p-1) congruent 1 (mod p) for prime p and p not dividing a	formula
gcd(a,b)	Euclidean algorithm	gcd(a,b)=gcd(a mod b,b)	formula
sigma(n)	Divisor sum	If n=product p_i^e_i, sigma(n)=product (p_i^(e_i+1)-1)/(p_i-1)	formula
N	Even perfect number	N=2^(p-1)(2^p-1) when 2^p-1 is prime	formula
(p-1)!	Wilson theorem	(p-1)! congruent -1 (mod p) iff p is prime	formula
F(n)	Mobius inversion	If G(n)=sum(d\|n)F(d), then F(n)=sum(d\|n)mu(d)G(n/d)	formula
sum deg(v)	Handshake lemma	sum(v in V) deg(v)=2\|E\|	formula
n-m+f	Planar Euler formula	n-m+f=2 for a connected plane graph	formula
m	Planar edge bound	m<=3n-6 for a simple planar graph with n>=3	formula
m	Bipartite planar edge bound	m<=2n-4 for a simple bipartite planar graph	formula

About this calculator

A searchable formula reference transcribed and normalized from the supplied Theoretical Computer Science Cheat Sheet.

Number Theory and Graph Theory formula reference

This searchable reference organizes formulas from the supplied Theoretical Computer Science Cheat Sheet into web-friendly notation. Use the search box to find a formula by name or symbol, then review its assumptions before applying it.

Some identities use conventional mathematical notation such as summation limits, factorials, congruences, expectations and asymptotic bounds. These entries are reference material and should be interpreted within their stated domains.