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.

Some Divisibility Criteria

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. The product of two consecutive positive integers is divisible by 2

   Solution:

   Let the integers be [math]\displaystyle{ n }[/math] and [math]\displaystyle{ n+1 }[/math]

   So the product of the two numbers is [math]\displaystyle{ p=n\times(n+1) }[/math]

   Case I

   when [math]\displaystyle{ n }[/math] is an even number

   then [math]\displaystyle{ n }[/math] can be expressed as [math]\displaystyle{ 2k }[/math] for some positive integer [math]\displaystyle{ k }[/math].

   [math]\displaystyle{ \therefore p=2k\times(2k+1) }[/math]; clearly [math]\displaystyle{ 2|p }[/math]

   Case II
   

   when [math]\displaystyle{ n }[/math] is an odd integer

   n can be expressed as [math]\displaystyle{ 2k+1 }[/math] for some positive integer [math]\displaystyle{ k }[/math].

   [math]\displaystyle{ p=(2k+1)\times{(2k+1)+1}=(2k+1)\times 2(k+1) }[/math]; clearly [math]\displaystyle{ 2|p }[/math]

   So, in both cases [math]\displaystyle{ 2|p }[/math]; hence 2 divides product of two consecutive positive integers

2. Show that if a positive integer is divisible by both 3 and 4, then it must be divisible by 12.

   Solution:

   Let's assume that a positive integer, denoted by "[math]\displaystyle{ n }[/math]," is divisible by both 3 and 4.

   Since n is divisible by 3, we can express it as [math]\displaystyle{ n = 3k }[/math], where [math]\displaystyle{ k }[/math] is an integer.

   Since n is divisible by 4, we can express it as [math]\displaystyle{ n = 4m }[/math], where [math]\displaystyle{ m }[/math] is an integer.

   Clearly [math]\displaystyle{ 3k=4m }[/math];

   since [math]\displaystyle{ 3 \nmid 4 \implies 3|m, \implies m=3l, }[/math] where [math]\displaystyle{ l }[/math] is an integer

   [math]\displaystyle{ n=4m=4\times3l=12l \implies 12|n }[/math]

   Therefore, if a positive integer is divisible by both 3 and 4, it must be divisible by 12.

3. Prove that the square of any integer is either of the form [math]\displaystyle{ 3m }[/math] or [math]\displaystyle{ 3m + 1 }[/math].

   Solution

   Any integer [math]\displaystyle{ n }[/math] can be expressed as [math]\displaystyle{ 3k, 3k+1, 3k+2 }[/math]

   Case I: if [math]\displaystyle{ n=3k }[/math]

   [math]\displaystyle{ n^2=9k^2=3\times3k^2=3m; m=3k^2 }[/math]

   Case II: if [math]\displaystyle{ n=3k+1 \implies n^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1=3m+1; m=(3k^2+2k) }[/math]

   Case III: if [math]\displaystyle{ n=3k+2 \implies n^2=(3k+2)^2=9k^2+12k+4=3(3k^2+4k+3)+1=3m+1; m=(3k^2+4k+3) }[/math]

   Hence, the square of any integer is either of the form [math]\displaystyle{ 3m }[/math] or [math]\displaystyle{ 3m + 1 }[/math]

4. Prove that the cube of any integer has one of the forms: [math]\displaystyle{ 9m, 9m + 1, }[/math] or [math]\displaystyle{ 9m + 8 }[/math], where [math]\displaystyle{ m }[/math] is an integer.

   Solution

   Any integer [math]\displaystyle{ n }[/math] can be expressed as [math]\displaystyle{ 3k, 3k+1, 3k+2 }[/math]

   Case I: if [math]\displaystyle{ n=3k \implies n^3=27k^3=9\times3k^3=9m; m=3k^3 }[/math]

   Case II: if [math]\displaystyle{ n=3k+1 \implies n^3=(3k+1)^3=27k^3+27k^2+9k+1=9(3k^3+3k^2+1)+1=9m+1; m=(3k^3+9k^2+1) }[/math]

   Case III: if [math]\displaystyle{ n=3k+2 \implies n^3=(3k+2)^3=27k^3+54k^2+36k+8=9(3k^3+6k^2+4)+8=9m+8; m=(3k^3+6k^2+4) }[/math]

5. Prove that the square of any odd integer can be expressed in the form [math]\displaystyle{ 8k + 1 }[/math], where [math]\displaystyle{ k }[/math] is an integer.

   Solution:

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

   The square of 2n + 1 is (2n + 1)² = 4n² + 4n + 1 = 4n(n + 1) +1

   Now, n and n+1 represent two consecutive integers, and product of two consecutive integers is always even. [as one of the two consecutive numbers is always even, e.g. 3x4=12]

   Therefore, n(n+1) = 2k for some integer k.

   (2n + 1)²=4x2k+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.

6. Prove that the fourth power of any integer is either of the form [math]\displaystyle{ 5k }[/math] or [math]\displaystyle{ 5k + 1 }[/math].
7. Prove that [math]\displaystyle{ 3a^2 - 1 }[/math] is never a perfect square.
8. For [math]\displaystyle{ n\geq 1 }[/math] prove that [math]\displaystyle{ n(n + 1)(2n + 1)/6 }[/math] is an integer.
9. Show that the cube of any integer is of the form [math]\displaystyle{ 7k }[/math] or [math]\displaystyle{ 7k ± 1 }[/math].
10. Prove that no integer in the following sequence is a perfect square:

    11, 111, 1111, 11111, ...

11. Verify that if an integer is simultaneously a square and a cube (as is the case with [math]\displaystyle{ 64 = 8^2 = 4^3 }[/math]), then it must be either of the form [math]\displaystyle{ 7k }[/math] or [math]\displaystyle{ 7k + 1 }[/math].
12. Prove that for every integer [math]\displaystyle{ n \geq 1, 7n^2+5 }[/math] is of the form [math]\displaystyle{ 6k }[/math].
13. For every odd integer [math]\displaystyle{ n }[/math], show that [math]\displaystyle{ n^4 + 4n^2 + 11 }[/math] is of the form [math]\displaystyle{ 16k }[/math].
14. Prove that [math]\displaystyle{ n^5-5n^3+4n }[/math] is divisible by [math]\displaystyle{ 120 }[/math]
15. Prove that [math]\displaystyle{ n^2+3n+5 }[/math] is divisible by 121

The Greatest Common Divisor

Let [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] be given integers, not both of them zero. The greatest common divisor of [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math], denoted by [math]\displaystyle{ gcd(a, b) }[/math], is the positive integer [math]\displaystyle{ d }[/math] satisfying the following: (a) [math]\displaystyle{ d|a }[/math] and [math]\displaystyle{ d|b }[/math]. (b) If [math]\displaystyle{ c|a }[/math] and [math]\displaystyle{ c|b }[/math], then [math]\displaystyle{ c\leq d }[/math]