Divisibility Rules

• Divisibility is a fundamental concept in number theory that describes when one integer can be divided evenly by another.
• An integer a is divisible by an integer b if there exists an integer k such that a = b k.
• The notation b | a denotes that b divides a. In this case, b is a divisor (or factor) of a, and a is a multiple of b.
• If b divides a, then the remainder of the division a / b is zero.
• If b does not divide a, then the notation b <binary data, 1 bytes><binary data, 1 bytes><binary data, 1 bytes> a is used.

Basic Properties

• If a | b and a | c, then a | (b + c). If a number divides two other numbers, it also divides their sum.
• If a | b and a | c, then a | (b - c). If a number divides two other numbers, it also divides their difference.
• If a | b, then a | (b c) for any integer c. If a number divides another number, it also divides that number multiplied by any integer.
• If a | b and b | c, then a | c. If a number divides another number, and that second number divides a third, then the first number also divides the third.
• If a | 1, then a = 1 or a = -1. The only integers that divide 1 are 1 and -1.
• If a | 0 for any non-zero integer a. Every non-zero integer divides 0.
• If a | b and b | a, then a = b or a = -b. If two numbers each divide the other, they must be equal or the negative of each other.

Divisibility Rules

• Divisibility rules are shortcuts to determine whether an integer is divisible by a fixed divisor without performing the division.
• A number is divisible by 2 if its last digit is even (0, 2, 4, 6, or 8).
• A number is divisible by 3 if the sum of its digits is divisible by 3.
• A number is divisible by 4 if the number formed by its last two digits is divisible by 4.
• A number is divisible by 5 if its last digit is 0 or 5.
• A number is divisible by 6 if it is divisible by both 2 and 3.
• A number is divisible by 8 if the number formed by its last three digits is divisible by 8.
• A number is divisible by 9 if the sum of its digits is divisible by 9.
• A number is divisible by 10 if its last digit is 0.
• A number is divisible by 11 if the alternating sum of its digits is divisible by 11. (e.g., for 1232, 1 - 2 + 3 - 2 = 0, which is divisible by 11)
• A number is divisible by 12 if it is divisible by both 3 and 4.

Prime Numbers

• A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
• Examples of prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, etc.
• An integer greater than 1 that is not prime is called a composite number.
• The number 1 is neither prime nor composite; it is a unit.
• Prime numbers are the building blocks of all other integers because every integer can be expressed as a product of prime numbers (Fundamental Theorem of Arithmetic).

Composite Numbers

• A composite number is a positive integer that has at least one divisor other than 1 and itself.
• Every composite number can be expressed as a product of two or more prime numbers.
• To test if a number n is prime, it is sufficient to check for divisibility by prime numbers less than or equal to the square root of n.

Greatest Common Divisor (GCD)

• The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers.
• The GCD of a and b is denoted as gcd(a, b) or sometimes as (a, b).
• One method to find the GCD is by listing all the factors of each number and finding the largest factor they have in common.
• The Euclidean algorithm is an efficient method for computing the GCD of two integers. For integers a and b, where a > b, divide a by b and replace a with b and b with the remainder. Repeat until the remainder is 0; the GCD is the last non-zero remainder.
• If gcd(a, b) = 1, then a and b are said to be relatively prime or coprime.

Least Common Multiple (LCM)

• The least common multiple (LCM) of two or more integers is the smallest positive integer that is divisible by each of the integers.
• The LCM of a and b is denoted as lcm(a, b).
• One method to find the LCM is by listing multiples of each number until a common multiple is found.
• The LCM can also be found using the formula: lcm(a, b) = (|a b|) / gcd(a, b).

Prime Factorization

• Prime factorization is the process of expressing a composite number as a product of its prime factors.
• Every integer greater than 1 can be uniquely represented as a product of prime numbers raised to certain powers (Fundamental Theorem of Arithmetic).
• To find the prime factorization of a number, divide the number by the smallest prime number that divides it evenly. Continue dividing the quotient by prime numbers until the quotient is 1. The prime factorization is the product of these prime divisors.
• Prime factorization is used in finding the GCD and LCM of numbers.

Applications of Divisibility

• Divisibility is used in simplifying fractions.
• Divisibility is applicable in cryptography.
• Divisibility is used to optimize algorithms.
• Divisibility is employed in scheduling and resource allocation problems.
• Divisibility plays a role in error detection and correction.