Rules Flashcards

1
Q

If p divides mn

A

p divides m OR p divides n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

if p divides c^2

A

p^2 divides c^2 AND p divides c

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

a and b are square numbers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Chinese Remainder Theorem

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How many Hamiltonian cycles in a complete graph?

A

1/2 (n-1)!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q
If gcd(a,b) = d
(4)
A

gcd(a/d, b/d) = 1
gcd (a, a-b) = d
gcd (b, a-qb) = d
There exist integers such that ma+nb=d

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

If a divides N and b divides N

A

LCM (a,b) divides N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

ab

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

If a and b are relatively prime

2

A

gcd (a,b) = 1

lcm (a,b) = ab

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

General solution of a first order recurrence relation

A

Un=c*a^n+d

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Auxiliary equation of a second order recurrence relation

A

Un=k^n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

General solution of a second order recurrence relation

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Divisibility rule for 2

A

Last digit is even

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Divisibility rule for 3

A

3 divides the sum of the digits

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Divisibility rule for 4

A

4 divides the last two digits

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Divisibility rule for 5

A

Last digit is 0 or 5

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Divisibility rule for 8

A

8 divides the last three digits

18
Q

Divisibility rule for 9

A

9 divides the sum of the digits

19
Q

Divisibility rule for 10

A

Last digit is 0

20
Q

Divisibility rule for 11

A

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

21
Q

If a graph is Eularian

A

Every vertex has even degree

22
Q

If a graph is semi-Eularian

A

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
Q

Fermat’s Little Theorem

3 parts

A
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
Q

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

A

n-1 divides the sum of its digits

25
Q

If a number n gives remainder r when divided by d

A

n = kd + r

26
Q

If a = b (mod m)

5

A
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
Q

If a = b (mod m) AND c = d (mod m)

3

A
a+c = b+d (mod m)
a-c = b-d (mod m)
ac = bd (mod m)
28
Q

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

A

a/d = b/d (mod m)

29
Q

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

A

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

30
Q

Solutions to a Diophantine equation ax + by = c with solutions x(1) and y(1) and where gcd (a,b) = d

A
x = x(1) + kb/d
y = y(1) - ka/d
31
Q

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

A

gcd (a,b) divides c

32
Q

If a divides b and a divides c

A

a divides b(+/-)c

33
Q

If a divides b

A

a divides bc

34
Q

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

A

ab divides N

35
Q

A factor of a^n - b^n is

A

a-b

36
Q

A factor of a^n + b^n is

A

a+b

37
Q

The complete graph with n vertices has how many edges?

A

nC2

38
Q

A tree with n vertices has how any edges?

A

n-1

39
Q

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

A

rs

40
Q

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

A

vC2 - e

41
Q

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

A

Even