Rules

Question 1

If p divides mn

Answer 1

p divides m OR p divides n

Question 2

if p divides c^2

Answer 2

p^2 divides c^2 AND p divides c

Question 3

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

Answer 3

a and b are square numbers

Question 4

Chinese Remainder Theorem

Answer 4

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

Question 5

How many Hamiltonian cycles in a complete graph?

Answer 5

1/2 (n-1)!

Question 6

If gcd(a,b) = d
(4)

Answer 6

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

Question 7

If a divides N and b divides N

Answer 7

LCM (a,b) divides N

Question 8

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

Answer 8

ab

Question 9

If a and b are relatively prime

2

Answer 9

gcd (a,b) = 1

lcm (a,b) = ab

Question 10

General solution of a first order recurrence relation

Answer 10

Un=c*a^n+d

Question 11

Auxiliary equation of a second order recurrence relation

Answer 11

Un=k^n

Question 12

General solution of a second order recurrence relation

Answer 12

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

Question 13

Divisibility rule for 2

Answer 13

Last digit is even

Question 14

Divisibility rule for 3

Answer 14

3 divides the sum of the digits

Question 15

Divisibility rule for 4

Answer 15

4 divides the last two digits

Question 16

Divisibility rule for 5

Answer 16

Last digit is 0 or 5

Question 17

Divisibility rule for 8

Answer 17

8 divides the last three digits

Question 18

Divisibility rule for 9

Answer 18

9 divides the sum of the digits

Question 19

Divisibility rule for 10

Answer 19

Last digit is 0

Question 20

Divisibility rule for 11

Answer 20

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

Question 21

If a graph is Eularian

Answer 21

Every vertex has even degree

Question 22

If a graph is semi-Eularian

Answer 22

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.

Question 23

Fermat’s Little Theorem

3 parts

Answer 23

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)

Question 24

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

Answer 24

n-1 divides the sum of its digits

Question 25

If a number n gives remainder r when divided by d

Answer 25

n = kd + r

Question 26

If a = b (mod m) | 5

Answer 26

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

Question 27

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

Answer 27

``` a+c = b+d (mod m) a-c = b-d (mod m) ac = bd (mod m) ```

Question 28

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

Answer 28

a/d = b/d (mod m)

Question 29

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

Answer 29

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

Question 30

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

Answer 30

``` x = x(1) + kb/d y = y(1) - ka/d ```

Question 31

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

Answer 31

gcd (a,b) divides c

Question 32

If a divides b and a divides c

Answer 32

a divides b(+/-)c

Question 33

If a divides b

Answer 33

a divides bc

Question 34

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

Answer 34

ab divides N

Question 35

A factor of a^n - b^n is

Answer 35

a-b

Question 36

A factor of a^n + b^n is

Answer 36

a+b

Question 37

The complete graph with n vertices has how many edges?

Answer 37

nC2

Question 38

A tree with n vertices has how any edges?

Answer 38

n-1

Question 39

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

Answer 39

rs

Question 40

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

Answer 40

vC2 - e

Question 41

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

Answer 41

Even