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