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