Discrete Structures PREFI

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.

Divisibility Rule for 2

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

Divisibility Rule for 3

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

Divisibility Rule for 4

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

Divisibility Rule for 5

5 divides n if the last digit is either 0 or 5.

Divisibility Rule for 6

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

Divisibility Rule for 7

To find out if 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.

Divisibility Rule for 8

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

Divisibility Rule for 9

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

Divisibility Rule for 10

10 divides n if the last digit is 0.

Divisibility Rule for 11

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.

Divisibility Rule for 12

12 divides n if the number is divisible by both 3 and 4.

Prime Numbers

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

Sieve of Eratosthenes

A procedure for finding out the prime numbers by writing the numbers from 1 to 100 in 10 rows of 10 and crossing off non-prime numbers.

Composite Numbers

These are positive integers that are greater than 1 and are not prime.

Composite Number

A composite number can be divided by at least one (1) number (a factor) other than itself.

Greatest Common Factor (GCF)

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

Least Common Multiple (LCM)

It is the smallest integer that is a common multiple of all the given integers.

Prime Factorization

A way of expressing a number as a product of its prime factors.

gcf (a, b)

It denotes the greatest common factor of a and b.

lcm (a, b)

It denotes the least common multiple of a and b.

Steps in Obtaining the GCF

Identify the common factors and list them, then multiply the common factors to find the greatest common divisor (factor).

Prime Divisors

List the prime divisors (factors) with the greatest power of all the given integers.

Finding GCF Example

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

Finding LCM Example

To find the least common multiple of 18 and 20: 1. Find the prime factorization of the given integer. 2. List the prime divisors (factors) with the greatest power of all the given integers. 3. Multiply the prime divisors (factors) to find the least common multiple.

Practice Exercises for GCF

Find the greatest common divisor of the following pair of numbers: 4480 and 10000, 2345 and 5000, 1346 and 2248, 1101 and 2002.

Practice Exercises for LCM

Find the LCM of the following: 1101 and 1000, 445 and 1125, 240 and 135, 172 and 426.

d | a

It is read as d divides a.

d | b

It is read as d divides b.

Common Divisor

If d | a and d | b, then d is a common divisor/factor of a and b.

Factors of a Number

Write any pair of factors of the given number. If some initial factors are not yet primes, find their factors.

Listing Factors

When all the factors are deduced to primes, write the numbers from least to greatest.

Theorem

Let k be a positive integer greater than 1.

n

A positive integer that can be expressed uniquely in the form: n = amkm + am-1km-1 + … + a1k + a0

Decimal

Base 10 number system with digits: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Binary

Base 2 number system with digits: {0, 1}

Octal

Base 8 number system with digits: {0, 1, 2, 3, 4, 5, 6, 7}

Hexadecimal

Base 16 number system with digits: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}

Decimal Number System

Base 10 system where the place values are powers of 10.

Binary Number System

Base 2 system where the place values are powers of 2.

Octal Number System

Base 8 system where the place values are powers of 8.

Hexadecimal Number

Base 16 system where the place values are powers of 16.

Conversion from Binary to Decimal

Multiply each digit by its corresponding place value and sum them up.

Conversion from Decimal to Binary

Divide the number by 2 repeatedly and note the remainders.

Conversion from Octal to Decimal

Multiply each digit by its corresponding place value based on powers of 8.

Conversion from Decimal to Octal

Divide the number by 8 repeatedly and note the remainders.

Conversion from Hexadecimal to Decimal

Multiply each digit by its corresponding place value based on powers of 16.

Conversion from Decimal to Hexadecimal

Divide the number by 16 repeatedly and note the remainders.

Place Value in Decimal

The value of a digit based on its position in the number, e.g., 3 Thousands, 8 Hundreds.

Place Value in Binary

The value of a digit based on its position in the number, e.g., 1 x 32, 0 x 16.

Place Value in Octal

The value of a digit based on its position in the number, e.g., 2 x 512.

Place Value in Hexadecimal

The value of a digit based on its position in the number, e.g., 11 x 256.

Value of 101101 in Binary

(101101)2 = (45)10

Value of 2467 in Octal

(2467)8 = (1335)10

Value of BF4 in Hexadecimal

(BF4)16 = (3060)10