Rules Flashcards
If p divides mn
p divides m OR p divides n
if p divides c^2
p^2 divides c^2 AND p divides c
if a and b are relatively prime and ab=c^2
a and b are square numbers
Chinese Remainder Theorem
If m and n are coprime, then the simultaneous congruences x=a(mod m) and x=b(mod n) have a unique solution (mod mn).
How many Hamiltonian cycles in a complete graph?
1/2 (n-1)!
If gcd(a,b) = d (4)
gcd(a/d, b/d) = 1
gcd (a, a-b) = d
gcd (b, a-qb) = d
There exist integers such that ma+nb=d
If a divides N and b divides N
LCM (a,b) divides N
gcd(a,b)*lcm(a,b)=
ab
If a and b are relatively prime
2
gcd (a,b) = 1
lcm (a,b) = ab
General solution of a first order recurrence relation
Un=c*a^n+d
Auxiliary equation of a second order recurrence relation
Un=k^n
General solution of a second order recurrence relation
Un=ck(1)^n + dk(2)^n (where k(1) and k(2) are unique solutions to the auxiliary equation.
If there is a repeated solution - Un=(c+dn)k^n
Divisibility rule for 2
Last digit is even
Divisibility rule for 3
3 divides the sum of the digits
Divisibility rule for 4
4 divides the last two digits
Divisibility rule for 5
Last digit is 0 or 5
Divisibility rule for 8
8 divides the last three digits
Divisibility rule for 9
9 divides the sum of the digits
Divisibility rule for 10
Last digit is 0
Divisibility rule for 11
11 divides n1 - n2 + n3 -n4 + n5….
If a graph is Eularian
Every vertex has even degree
If a graph is semi-Eularian
Exactly two vertices have odd degree so it is possible to find a Eularian trail starting at one of the vertices of odd degree, and ending at the other.
Fermat’s Little Theorem
3 parts
If p is prime and a is any integer: a^p = a (mod p) p divides (a^p-a) If p is prime, and p does not divide a: a^(p-1) = 1 (mod p)
A base n number is divisible by n-1 if, and only if
n-1 divides the sum of its digits
If a number n gives remainder r when divided by d
n = kd + r
If a = b (mod m)
5
a and b have the same remainder when divided by m a = km + b ka = kb (mod m) a^n = b^n (mod m) a = b(+/-)m (mod m)
If a = b (mod m) AND c = d (mod m)
3
a+c = b+d (mod m) a-c = b-d (mod m) ac = bd (mod m)
If a = b (mod m), d divides a and b AND d and m are relatively prime
a/d = b/d (mod m)
If a = b (mod m), d divides a, b and m
a/d = b/d (mod m/d)
Solutions to a Diophantine equation ax + by = c with solutions x(1) and y(1) and where gcd (a,b) = d
x = x(1) + kb/d y = y(1) - ka/d
A linear Diophantine equation (ax + by = c) has integer solutions if, and only if
gcd (a,b) divides c
If a divides b and a divides c
a divides b(+/-)c
If a divides b
a divides bc
If a divides N and b divides N and a and b are relatively prime
ab divides N
A factor of a^n - b^n is
a-b
A factor of a^n + b^n is
a+b
The complete graph with n vertices has how many edges?
nC2
A tree with n vertices has how any edges?
n-1
The complete bipartite graph k(r,s) has how many edges?
rs
The compliment of a graph with v vertices and e edges has how many edges?
vC2 - e
The number of vertices of odd degree in a graph is always
Even
