Mathematics X

Real Numbers

Divisibility

What is meant by divisibility in Mathematics?

In mathematics, divisibility refers to the relationship between two numbers where one number can be evenly divided by another number without leaving a remainder. It is a fundamental concept used to determine if one number is a factor or multiple of another number.

Let us consider two integers, [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math]. We say that "[math]\displaystyle{ a }[/math] is divisible by [math]\displaystyle{ b }[/math]" or "[math]\displaystyle{ b }[/math] divides [math]\displaystyle{ a }[/math]" if there exists an integer [math]\displaystyle{ k }[/math] such that when we multiply [math]\displaystyle{ b }[/math] by [math]\displaystyle{ k }[/math], we obtain [math]\displaystyle{ a }[/math]. In other words,

[math]\displaystyle{ a = bk }[/math]

The terms used to describe this relationship are as follows:

Dividend: The number being divided "[math]\displaystyle{ a }[/math]".

Divisor: The number by which the dividend is divided "[math]\displaystyle{ b }[/math]".

Quotient: The result of the division, the integer obtained "[math]\displaystyle{ k }[/math]".

Remainder: The whole number that is left over when the dividend is divided by the divisor (if it is not evenly divisible).

If the remainder is zero, it indicates that the division is exact, and the dividend is divisible by the divisor. Conversely, if the remainder is not zero, it means the division is not exact, and the dividend is not divisible by the divisor.

Divisibility plays a significant role in many areas of mathematics, including number theory, algebra, arithmetic, and cryptography. It is used to determine prime numbers, factors, multiples, common divisors, and various properties of integers. Divisibility rules and properties provide useful shortcuts and techniques to identify divisibility without performing actual division calculations, making it a valuable tool in problem-solving and mathematical reasoning.

Here are some key points to consider when exploring the divisibility of numbers:

• Divisibility by 2: A number is divisible by 2 if its units digit is even, meaning it ends with 0, 2, 4, 6, or 8. For example, 24, 136, and 1,790 are divisible by 2.

• Divisibility by 3: A number is divisible by 3 if the sum of its digits is divisible by 3. For example, 87 (8 + 7 = 15) and 1,452 (1 + 4 + 5 + 2 = 12) are divisible by 3.

• Divisibility by 4: A number is divisible by 4 if the number formed by its last two digits is divisible by 4. For example, 2,408 (08 is divisible by 4) and 456 (56 is divisible by 4) are divisible by 4.

• Divisibility by 5: A number is divisible by 5 if its units digit is 0 or 5. For example, 250 and 1,035 are divisible by 5.

• Divisibility by 6: A number is divisible by 6 if it is divisible by both 2 and 3. In other words, it should satisfy the criteria for divisibility by 2 and 3 simultaneously. For example, 48 (divisible by 2 and 3) and 198 (divisible by 2 and 3) are divisible by 6.

• Divisibility by 9: A number is divisible by 9 if the sum of its digits is divisible by 9. For example, 2,601 (2 + 6 + 0 + 1 = 9) and 4,914 (4 + 9 + 1 + 4 = 18) are divisible by 9.

• Divisibility by 10: A number is divisible by 10 if it ends with a zero, indicating that it is a multiple of 10. For example, 80, 1,350, and 25,000 are divisible by 10.

These are some of the basic rules for divisibility by small integers. However, there are more complex rules for divisibility by larger primes and composite numbers. For example, divisibility rules for 7, 11, and 13 involve alternating digit sums and differences.

Understanding the concept of divisibility and applying the relevant rules can greatly simplify calculations, factorisation, and problem-solving in mathematics. Divisibility plays a crucial role in determining factors, multiples, prime numbers, and various properties of integers, making it an essential concept across different branches of mathematics.

How do we denote "[math]\displaystyle{ a }[/math] divides [math]\displaystyle{ b }[/math]"?

In mathematics, we express the relationship of divisibility by saying "[math]\displaystyle{ a }[/math] divides [math]\displaystyle{ b }[/math]" or "[math]\displaystyle{ b }[/math] is divisible by [math]\displaystyle{ a }[/math]." Symbolically, we use the notation "[math]\displaystyle{ a }[/math] | [math]\displaystyle{ b }[/math]" to represent this concept.

Using the notation "[math]\displaystyle{ a }[/math] | [math]\displaystyle{ b }[/math] ," we can say that "[math]\displaystyle{ a }[/math] divides [math]\displaystyle{ b }[/math] " if there exists an integer [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ ak = b }[/math] . In other words, if we can find an integer [math]\displaystyle{ k }[/math] such that when we multiply [math]\displaystyle{ a }[/math] by [math]\displaystyle{ k }[/math] , we obtain [math]\displaystyle{ b }[/math] , then we say that [math]\displaystyle{ a }[/math] divides [math]\displaystyle{ b }[/math] .

For example:

• If 3 divides 12, we write it as 3 | 12, because 3 * 4 = 12.
• If 7 divides 35, we write it as 7 | 35, because 7 * 5 = 35.
• If 2 does not divide 9, we write it as [math]\displaystyle{ 2 \nmid 9 }[/math], because there is no integer [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ 2 * k = 9 }[/math].

The notation "[math]\displaystyle{ a | b }[/math]" is a concise and commonly used way to express the concept of divisibility in mathematics. It helps in stating properties, theorems, and relationships related to divisibility, and it allows for clearer and more efficient communication about the mathematical relationships between numbers.

What is Euclid's Division Lemma?

Euclid's Division Lemma, also known as the Euclidean division lemma, is a fundamental result in number theory attributed to the ancient Greek mathematician Euclid. It provides a way to express the division of one integer by another integer in a particular form.

Euclid's Division Lemma states that for any two positive integers, let's say '[math]\displaystyle{ a }[/math]' and '[math]\displaystyle{ b }[/math]', there exist unique integers '[math]\displaystyle{ q }[/math]' (quotient) and '[math]\displaystyle{ r }[/math]' (remainder) such that:

[math]\displaystyle{ a = bq + r }[/math]

where [math]\displaystyle{ 0 ≤ r \lt b }[/math].

In simpler terms, this means that when you divide a positive integer '[math]\displaystyle{ a }[/math]' by another positive integer '[math]\displaystyle{ b }[/math]', you can always express the dividend '[math]\displaystyle{ a }[/math]' as the product of the divisor '[math]\displaystyle{ b }[/math]' and the quotient '[math]\displaystyle{ q }[/math]', plus a remainder '[math]\displaystyle{ r }[/math]' that is less than '[math]\displaystyle{ b }[/math]'.

The important properties of Euclid's Division Lemma are that the quotient '[math]\displaystyle{ q }[/math]' and remainder '[math]\displaystyle{ r }[/math]' are unique for a given pair of '[math]\displaystyle{ a }[/math]' and '[math]\displaystyle{ b }[/math]', and that the remainder is always non-negative and less than the divisor.

This lemma serves as a foundational concept in number theory, and it forms the basis for various algorithms and concepts, including the Euclidean algorithm for finding the greatest common divisor (GCD) of two numbers and the concept of congruence in modular arithmetic.

Where is Euclid's Division Lemma applied?

Euclid's Division Lemma has several important applications in mathematics and number theory. Here are a few examples:

• Euclidean Algorithm: Euclid's Division Lemma is a key component of the Euclidean algorithm, which is used to find the greatest common divisor (GCD) of two integers. The algorithm repeatedly applies the division lemma to compute the GCD efficiently.

• Prime Factorization: Euclid's Division Lemma is used in the process of prime factorization, where a composite number is expressed as a product of prime numbers. By repeatedly dividing a number by prime factors, Euclid's Division Lemma helps in determining the prime factors of a given number.

• Division and Remainder Problems: Euclid's Division Lemma is employed to solve various division and remainder problems. For example, it can be used to determine whether a number is divisible by another number, or to find the remainder when a large number is divided by a smaller one.

• Modular Arithmetic: Euclid's Division Lemma is used to define congruence in modular arithmetic. In modular arithmetic, two numbers are considered congruent if they have the same remainder when divided by a given modulus. Euclid's Division Lemma helps establish the foundations of modular arithmetic.

• Diophantine Equations: Euclid's Division Lemma is applied in solving Diophantine equations, which are equations that seek integer solutions. The lemma can be used to analyze and find solutions to equations of the form ax + by = c, where a, b, c are integers.

Overall, Euclid's Division Lemma is a fundamental tool in number theory and provides the basis for various algorithms and techniques used in mathematics. Its applications extend to diverse areas such as prime numbers, modular arithmetic, and solving equations with integer solutions.

Example Problems on application of Euclid's Division Lemma

1. Prove, by using Euclid's Division Lemma, that the square of any odd integer can be expressed in the form 8k + 1, where k is an integer.

Let's consider an odd integer, which can be represented as 2n + 1, where n is an integer.

Step 1: Express the square of the odd integer. The square of 2n + 1 is (2n + 1)² = 4n² + 4n + 1.

Step 2: Apply Euclid's Division Lemma. We can rewrite 4n² + 4n as 4n(n + 1). According to Euclid's Division Lemma, we can express 4n(n + 1) as 8k + r, where k and r are integers and 0 ≤ r < 8.

Step 3: Evaluate r. When we divide 4n(n + 1) by 8, we get a quotient of 4n/8 = n/2, and the remainder r is equal to 4n(n + 1) - 8(n/2) = 4n(n + 1) - 4n = 4n² + 4n.

Step 4: Express the square in the form 8k + 1. Substituting the value of 4n² + 4n for r, we have: (2n + 1)² = 4n² + 4n + 1 = (8k + r) + 1 = 8k + (r + 1).

Step 5: Evaluate (r + 1). Since 0 ≤ r < 8, the possible values of (r + 1) are 1, 2, 3, 4, 5, 6, 7, and 8.

Step 6: Determine the value of k. We can choose k as (n² + n)/2, which is an integer.

Step 7: Express the square in the form 8k + 1. Considering the possible values of (r + 1), we find: If (r + 1) = 1, then (8k + (r + 1)) = 8k + 1.

Therefore, we can conclude that the square of any odd integer can be expressed in the form 8k + 1, where k is an integer.