Discrete Math Pre Final

Number Theory

It is a branch of mathematics concerned with integers and their properties.

Divisibility

It means dividing a number evenly.

d | n

d divides n if there is no remainder on the division

d ∤ n

d does not divide n

2

divides n if the last digit of the number is even (e. g. 0, 2, 4, 6, or 8).

3

divides n if the sum of the digits is divisible by 3

4

divides n if the number formed by the last two (2) digits is divisible by 4.

5

divides n if the last digit is either 0 or 5

6

divides n if it is divisible by 2 and it is divisible by 3.

7

divides n, take the last digit, double it, and subtract it from the rest of the number. If you get an answer divisible by 7 (including zero), then the original number is divisible by seven. If you don't know the new number's divisibility, you can apply the rule again.

8

divides n if the number formed by the last three digits is divisible by 8

9

divides n if the sum of the digits is divisible by 9.

10

divides n if the last digit is 0.

11

divides n if the difference between the sum of one set of alternate digits (from left to right) and the sum of the other set of alternate digits (from left to right) is 0 or divisible by 11

12

divides n, if the number is divisible by both 3 and 4 (it passes both the 3 rule and 4 rule above)

Prime Numbers

These are positive integers greater than 1 that cannot be divided by any number except themselves and 1.

Composite Numbers

These are positive integers that are greater than 1 and are not prime. A ? number can be divided by at least one (1) number (a factor) other than itself.

Greatest Common Factor

It is the largest non-zero integer d that is a common divisor of all the given integers

d | a

is read as d divides a

d | b

is read as d divides b

Least Common Multiple

It is the smallest integer that is a common multiple of all the given integers. It is denoted by lcm (a, b).

Prime Factorization

A way of expressing a number as a product of its prime factors • Write any pair of factors of the given number. • If some initial factors are not yet primes, find their factors. • When all the factors are deduced to primes, write the numbers from least to greatest

GCF of Two (2) or More Integers using their prime factorization

• Identify the common factors and list them. • Multiply the common factors to find the greatest common divisor (factor). Example: Find the greatest common divisor of 375 and 525 1. Find the prime factorization of the given integers 2. Identify their common factors (5 and 5) 3. Multiply the common factors (5 x 5 = 25) 4. gcf (375, 525) = 25

Theorem

Let k be a positive integer greater than 1. Then if n is a positive integer, it can be expressed uniquely in the form: n = amkm + am-1km-1 + … + a1k + a0

Decimal

k = 10, digits: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Binary

k = 2, digits: {0, 1}

Octal

k = 8, digits: {0, 1, 2, 3, 4, 5, 6, 7}

Hexadecima

k = 16, digits: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}