Number Theory: Divisibility Rules

• Number theory is a branch of mathematics dealing with integers and their properties.

Divisibility

• Divisibility means dividing a number evenly.
• d | n means that d divides n, leaving no remainder.
• dł n means that d does not divide n.

Divisibility Rules

• 2 divides n if the last digit is even (0, 2, 4, 6, or 8). For example, 2 | 128 but 2 ł 129.
• 3 divides n if the sum of the digits is divisible by 3. For example, 3 | 381 but 3 ł 217.
• 4 divides n if the number formed by the last two digits is divisible by 4. For example, 4 | 1312 but 4 ł 7019.
• 5 divides n if the last digit is 0 or 5. For example, 5 | 175 but 5 ł 809.
• 6 divides n if it is divisible by both 2 and 3. For example, 6 | 114 but 6 ł 308.
• To check if 7 divides n, take the last digit, double it, and subtract it from the rest of the number; if the result is divisible by 7 (including zero), then 7 divides n. For example, 7 | 672 but 7 ł 905.
• 8 divides n if the number formed by the last three digits is divisible by 8. For example, 8 | 109816 but 8 ł 216302.
• 9 divides n if the sum of the digits is divisible by 9. For example, 9 | 1629 but 9 ł 2013.
• 10 divides n if the last digit is 0. For example, 10 | 220 but 10 ł 221.
• 11 divides n if the difference between the sums of alternate digits (from left to right) is 0 or divisible by 11. For example, 11 | 3729 but 11 ł 987.
• 12 divides n if the number is divisible by both 3 and 4. For example, 12 | 648 but 12 ł 524.

Prime and Composite Numbers

• Prime numbers are positive integers greater than 1 that are only divisible by themselves and 1.
• Composite numbers are positive integers greater than 1 that are not prime, meaning they have factors other than 1 and themselves.

Sieve of Eratosthenes

• The Sieve of Eratosthenes is a method for finding prime numbers:
• Write numbers from 1 to 100 in ten rows.
• Cross off 1.
• Keep 2 as prime, cross off multiples of 2.
• Keep 3 as prime, cross off multiples of 3.
• Keep the next remaining number (5) and cross off its multiples; continue this process.
• The remaining "surviving" numbers are prime.

LCM/GCF

• GCF (Greatest Common Factor) is the largest non-zero integer d that is a common divisor of all given integers. d | a means d divides a.
• If d | a and d | b, then d is a common divisor/factor of a and b, denoted as gcf(a, b).
• LCM (Least Common Multiple) is the smallest integer that is a common multiple of all given integers; it is denoted by lcm(a, b).

Prime Factorization

• Prime factorization expresses a number as a product of its prime factors. Steps:
  • Write any pair of factors of the given number.
  • If some factors are not prime, find their factors.
  • When all factors are prime, write the numbers from least to greatest.

Finding the GCF Using Prime Factorization

• Identify the common prime factors of the numbers.
• Multiply the common factors to find the GCF.
• For example to find the GCF of 375 and 525:
• Prime factorization: find the prime factorization of each integer
• Common factors: Identify their common factors (5 and 5)
• Multiply: Multiply the common factors (5 x 5 = 25)
• The GCF of 375 and 525 is 25, or gcf(375, 525) = 25.

Steps in Obtaining the LCM of Two (2) or More Integers

• Find the prime factorization of each integer.
• List the prime divisors (factors) with the greatest power of all given integers.
• Multiply the prime divisors (factors) to find the LCM (denominator).

Number Systems

• Theorem: Any positive integer n can be uniquely expressed in the form n = amkm + am-1km-1 + ... + a1k + a0, where k is a positive integer greater than 1.
• Common Bases:
• Decimal: Base 10, digits: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• Binary: Base 2, digits: {0, 1}
• Octal: Base 8, digits: {0, 1, 2, 3, 4, 5, 6, 7}
• Hexadecimal: Base 16, digits: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}

Conversion

• To convert from one number system to another, it is common practice to convert first to base 10.

Binary to Decimal Conversion

Steps:

• Multiply each digit by its corresponding place value (power of 2).
• Add the values of the digits based on their place value.
• For example, (101101)2 = (45)10 can be computed as follows:
• (1 x 2^5) + (0 x 2^4) + (1 x 2^3) + (1 x 2^2) + (0 x 2^1) + (1 x 2^0) = 32 + 0 + 8 + 4 + 0 + 1 = 45

Decimal to Binary Conversion

Steps:

• Divide by the base (2) and note the remainder.
• Divide the previous quotient by 2 and note the remainder.
• Keep dividing until you arrive at an answer of zero or remainder 1.
• Write the remainders as digits from bottom to top.
• For example, (45)10 = (101101)2 can be computed as follows:
• 45 ÷ 2 = 22 remainder 1
• 22 ÷ 2 = 11 remainder 0
• 11 ÷ 2 = 5 remainder 1
• 5 ÷ 2 = 2 remainder 1
• 2 ÷ 2 = 1 remainder 0
• 1 ÷ 2 = 0 remainder 1

Octal to Decimal Conversion

Steps:

• Multiply each digit by its corresponding place value (power of 8).
• Add the values of the digits based on their place value.
• For example, (2467)8 = (1335)10 can be computed as follows:
• (2 x 8^3) + (4 x 8^2) + (6 x 8^1) + (7 x 8^0) = 1024 + 256 + 48 + 7 = 1335

Decimal to Octal Conversion

Steps:

• Divide by the base (8) and note the remainder.
• Divide the previous quotient by 8 and note the remainder.
• Keep dividing until you arrive at an answer of zero or remainder 1.
• Write the remainders as digits from bottom to top.
• For example, (1335)10 = (2467)8 can be computed as follows:
• 1335 ÷ 8 = 166 remainder 7
• 166 ÷ 8 = 20 remainder 6
• 20 ÷ 8 = 2 remainder 4
• 2 ÷ 8 = 0 remainder 2

Hexadecimal to Decimal Conversion

Steps:

• Multiply each digit by its corresponding place value (power of 16).
• Add the values of the digits based on their place value.
• For example, (BF4)16 = (3060)10 can be computed as follows:
• (11 x 16^2) + (15 x 16^1) + (4 x 16^0) = 2816 + 240 + 4 = 3060

Decimal to Hexadecimal Conversion

Steps:

• Divide by the base (16) and note the remainder.
• Divide the previous quotient by 16 and note the remainder.
• Keep dividing until you arrive at an answer of zero or remainder 1.
• Note that for values 11 – 15, we represent using the letters A – F (A = 11, B = 12, C = 13, D = 14, E = 15, F = 15).
• Write the remainders as digits from bottom to top.
• For example, (3060)10 = (BF4)16 can be computed as follows:
• 3060 ÷ 16 = 191 remainder 4
• 191 ÷ 16 = 11 remainder 15
• 11 ÷ 16 = 0 remainder 11