Rules Flashcards Preview

IB Discrete Maths HL > Rules > Flashcards

Flashcards in Rules Deck (41):
1

If p divides mn

p divides m OR p divides n

2

if p divides c^2

p^2 divides c^2 AND p divides c

3

if a and b are relatively prime and ab=c^2

a and b are square numbers

4

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).

5

How many Hamiltonian cycles in a complete graph?

1/2 (n-1)!

6

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

7

If a divides N and b divides N

LCM (a,b) divides N

8

gcd(a,b)*lcm(a,b)=

ab

9

If a and b are relatively prime
(2)

gcd (a,b) = 1
lcm (a,b) = ab

10

General solution of a first order recurrence relation

Un=c*a^n+d

11

Auxiliary equation of a second order recurrence relation

Un=k^n

12

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

13

Divisibility rule for 2

Last digit is even

14

Divisibility rule for 3

3 divides the sum of the digits

15

Divisibility rule for 4

4 divides the last two digits

16

Divisibility rule for 5

Last digit is 0 or 5

17

Divisibility rule for 8

8 divides the last three digits

18

Divisibility rule for 9

9 divides the sum of the digits

19

Divisibility rule for 10

Last digit is 0

20

Divisibility rule for 11

11 divides n1 - n2 + n3 -n4 + n5....

21

If a graph is Eularian

Every vertex has even degree

22

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.

23

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)

24

A base n number is divisible by n-1 if, and only if

n-1 divides the sum of its digits

25

If a number n gives remainder r when divided by d

n = kd + r

26

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)

27

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)

28

If a = b (mod m), d divides a and b AND d and m are relatively prime

a/d = b/d (mod m)

29

If a = b (mod m), d divides a, b and m

a/d = b/d (mod m/d)

30

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

31

A linear Diophantine equation (ax + by = c) has integer solutions if, and only if

gcd (a,b) divides c

32

If a divides b and a divides c

a divides b(+/-)c

33

If a divides b

a divides bc

34

If a divides N and b divides N and a and b are relatively prime

ab divides N

35

A factor of a^n - b^n is

a-b

36

A factor of a^n + b^n is

a+b

37

The complete graph with n vertices has how many edges?

nC2

38

A tree with n vertices has how any edges?

n-1

39

The complete bipartite graph k(r,s) has how many edges?

rs

40

The compliment of a graph with v vertices and e edges has how many edges?

vC2 - e

41

The number of vertices of odd degree in a graph is always

Even