Let a,b be integers. We say that a divides b (a|b) or b is divisible by a, or a is a factor of b, if there exists an integer c such that b = ac

also, b ≡ 0 mod a

if a|b and b|c, then a|c

for any x in the reals, the greatest integer function is defined as the greatest integer m satisfying m ≤ x.

also known as the floor function

given integers a,b with b>0 there exists unique integers q,r such that a = qb + r and 0≤r<b. 

q = [a/b] (floor)

r = a - [a/b]*b

also, a ≡ r mod b

the prime counting function π(x) satisfies

lim(x->∞) [π(x) / (x/lnx)] = 1

i) (a,b) = (-a,b) = (a,-b) = (-a,-b)

ii) (a,b) = (a+bn,b) = (a,b+am) for any integers n,m

iii) (ma,mb) = m(a,b) for any natural number m

iv) if d = (a,b) then (a/d,b/d) = 1

v) d | (a,b) iff d|a and d|b

let a,b be integers and a and b not both zero. Let d = (a,b). Then there exists integers m,n such that d = na +mb

d is a linear combination of a and b with integer coefficients

d is the minimum value combination of a and b

i) [a,b] = [-a,b] = [a,-b] = [-a,-b]

ii) [ma,mb] = m[a,b] for any natural number m

iii) [a,b] = |ab|/(a,b)

iv) let m be a natural number, then [a,b] | m iff a|m and b|m

a sequence of the form a, a+b, a+2b, a+ 3b....

also, {n integers : n ≡ a mod b}

i) if a≡b mod m and c≡d mod m, then a+c ≡ b+d mod m

ii) if a≡b mod m and c≡d mod m, then ac≡bd mod m

iii) if a≡b mod m, then aⁿ≡bⁿ mod m for any natural number

iv) if a≡b mod m, then f(a)≡f(b) mod m for any polynomial f(n) with integer coefficients

v) if a≡b mod m, then a≡b mod d for any positive divisor of m

the congruence relation modulo m is an equivalence relation and satisfies the following properties:

reflexivity: a≡a mod m

symmetry if a≡b mod m, then b≡a mod m

transitivity: if a≡b and b≡c, then a≡c

the equivalence classes defined by the conguence relation modulo m

for any integer a, [a] denotes the equivalence class to which a belongs:

[a] = {n integer | n≡a mod m}

let p be a prime number

(p-1)! ≡ -1 mod p

if p is an integer greater than or equal to 2 satisfying

(p-1)! ≡ -1 mod p

then p must be a prime number

If n is composite, then (n-1)! is not congruent to -1 mod n

If n is greater than 4, then (n-1)! ≡ 0 mod n

Let p be a prime number. Then for any integer a satisfying (a,p) = 1

a^p-1 ≡ 1 mod p

Let p be a prime number, then for any integer a

a^p ≡ a mod p

(10 ≡ 0 mod 2)

n is divisible by 2 iff

a₀ ≡ 0 mod 2

(a₀ denotes units digit)

(10 ≡ 0 mod 5)

n is divisible by 5 iff

a₀ ≡ 0 mod 5

(10 ≡ 1 mod 3)

n is divisible by 3 iff the sum of its digits is divisible by 3

Let s(n) be the sum of decimal digits of n. Then n ≡ s(n) mod 3

(10 ≡ 1 mod 9)

n ≡ s(n) mod 9, so n is divisible by 9 iff the sum of its digits is divisible by 9

8x≡1 mod 35 is interpreted as:

8x = 35y +1

8x + 35(-y) =1

there is a unique solution x mod (m₁*m₂*...*m_r) for the system of linear congruences 

x ≡ b1 mod m1

x ≡ b2 mod m2

x ≡ b3 mod m3

then M = m₁*m₂*m₃, M₁ = m₂*m₃, M₂ = m₁*m₃, M₃ = m₁*m₂

x₁ ≡ 1 mod M₁, x₂ ≡ 1 mod M₂, x₃ ≡ 1 mod M₃

x = x₁b₁M₁ + x₂b₂M₂  + x₃b₃M₃ mod M

algorithm for finding primes

e.g. primes between 1 and 100

list numbers starting at 2 to 100, start to cross off multiples of 2, then 3, then 5, and so on, you will be left with only the prime numbers.

application of the fundamental theorem of arithmetic;

number of divisors is how many unique combinations of the prime factorization you can make

Every integer greater than 1 has a unique factorization into primes; that is, every integer n>1 can be represented in the form

n = PI(r, i = 1) p_i^a_i

where the p_i are distinct primes, and the exponents a_i are positive integers. Moreover, this representation is unique except for the ordering of the primes p_i

the congruence

ax≡b mod m, and d = (a,m),

then has a solution if and only if d|b

Suppose d|b. Then ax≡b mod m has exactly d pairwise incongruent solutions x modulo m.

The solutions are in the form x = x₀ + km/d for k = 0,1,...,d-1 where x₀ is a particular solution

Suppose d|b, then a particular solution can be constructed as follows:

Apply the Euclidean algorithm to compute d = (a,m), and, working backwards, obtain a representation of d as a linear combination of a and m. Multiply the resulting equation through with (b/d) The new equation can be interpreted as a congruence of the desired type, and reading off the coefficient of "a" gives a particular solution