Divisibility

Definition and Basic Concepts

Divisibility Definition

Integer a divides integer b (notation: a | b) if ∃ integer k such that b = a × k. If no such k exists, a does not divide b (a ∤ b).

Divisor and Multiple

Divisor: a divides b ⇒ a is divisor of b. Multiple: b is multiple of a. Examples: 3|12 (3 divides 12), 12 is multiple of 3.

Notation and Terminology

Symbols: | (divides), ∤ (does not divide), gcd (greatest common divisor), lcm (least common multiple). Integers considered usually in ℤ.

Divisibility Rules

General Rules for Small Integers

Divisible by 2: last digit even. By 3: sum of digits divisible by 3. By 5: last digit 0 or 5. By 9: sum digits divisible by 9. By 10: last digit 0.

Rules for 4, 6, 8, 11

4: last two digits divisible by 4. 6: divisible by 2 and 3. 8: last three digits divisible by 8. 11: difference between sum of digits in odd and even positions divisible by 11.

Use in Algorithms and Computation

Rules optimize divisibility testing without full division. Used in computer algorithms, cryptographic checks, numeric validation.

Prime Factorization and Divisibility

Fundamental Theorem of Arithmetic

Every integer >1 can be uniquely represented as a product of primes, up to ordering: n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k.

Using Prime Factorization to Test Divisibility

Let a = ∏ p_i^{α_i}, b = ∏ p_i^{β_i}. Then a|b ⇔ ∀ i, α_i ≤ β_i. Prime factors of divisor must be subset with lesser or equal powers.

Example Factorizations

60 = 2² × 3 × 5. 48 = 2⁴ × 3. 60 divides 240? 240 = 2⁴ × 3 × 5 → yes, since powers of prime factors in 60 ≤ powers in 240.

Euclidean Algorithm

Purpose and Definition

Algorithm to compute gcd(a,b) efficiently by repeated remainder calculations. Based on property gcd(a,b) = gcd(b, a mod b).

Algorithm Steps

Given integers a, b with a ≥ b > 0: compute r = a mod b. Replace (a,b) with (b,r). Repeat until r=0. Then gcd = b.

Example Computation

Compute gcd(252,105): 252 mod 105 = 42, gcd(105,42): 105 mod 42=21, gcd(42,21): 42 mod 21=0 ⇒ gcd = 21.

function gcd(a, b): while b ≠ 0: r = a mod b a = b b = r return a

Greatest Common Divisor and Least Common Multiple

Definitions

GCD(a,b): largest integer dividing both a and b. LCM(a,b): smallest positive integer divisible by both a and b.

Relationship Between GCD and LCM

Formula: a × b = gcd(a,b) × lcm(a,b). Enables calculation of one if the other known.

Computing LCM Using GCD

lcm(a,b) = (a × b) / gcd(a,b). Efficient due to gcd calculation by Euclidean algorithm.

Modular Arithmetic and Congruences

Definition of Congruence

a ≡ b (mod n) means n divides (a - b). Equivalence relation partitions integers into residue classes modulo n.

Connection to Divisibility

Divisibility is core to modular arithmetic: a ≡ b (mod n) ⇔ n | (a - b). Enables modular computations replacing divisibility checks.

Properties and Operations

Congruences preserve addition, subtraction, multiplication: if a ≡ b (mod n) and c ≡ d (mod n), then a±c ≡ b±d (mod n), ac ≡ bd (mod n).

Given:a ≡ b (mod n)c ≡ d (mod n)Then:(a + c) ≡ (b + d) (mod n)(a - c) ≡ (b - d) (mod n)(a × c) ≡ (b × d) (mod n)

Properties of Divisibility

Transitivity

If a|b and b|c then a|c. Proof: b = a·k, c = b·m ⇒ c = a·(k·m).

Additivity

If a|b and a|c then a|(b + c). Linear combinations preserve divisibility.

Cancellation Law

If a·c | b·c and gcd(c, b/c) = 1, then a|b. Requires c nonzero and coprime conditions.

Applications of Divisibility

Number Theory and Cryptography

Prime factorization and divisibility underpin RSA, Diffie-Hellman, digital signatures. Security depends on difficulty of factoring.

Algorithm Design

Divisibility tests optimize algorithms for primality, factorization, modular exponentiation, hashing functions.

Problem Solving and Proofs

Divisibility used in induction proofs, Diophantine equations, combinatorics, integer partitions.

Proof Techniques Related to Divisibility

Direct Proof

Start from definition: assume a|b means b = a·k, manipulate expression to show desired property.

Proof by Contradiction

Assume divisibility does not hold, derive contradiction using integer properties or factorization.

Induction

Used for divisibility properties over sequences or sums, e.g. proving n! divisible by certain numbers.

Advanced Topics

Divisibility in Rings and Integral Domains

Generalize divisibility beyond integers to ring elements. Concepts of units, associates, irreducibles.

Unique Factorization Domains

Domains where every element factorizes uniquely into irreducibles. Analogous to integers’ fundamental theorem.

Applications in Algebraic Number Theory

Divisibility concepts extend to integers in number fields. Crucial in understanding primes, ideals, and class groups.

Examples and Exercises

Simple Divisibility Checks

Is 234 divisible by 3? Sum digits: 2+3+4=9 divisible by 3 ⇒ yes.

Computing GCD Using Euclidean Algorithm

Compute gcd(119,544): 544 mod 119=68, 119 mod 68=51, 68 mod 51=17, 51 mod 17=0 ⇒ gcd=17.

Proving Divisibility Properties

Prove: If a|b and a|c then a|(mb + nc) for any integers m, n.

Common Misconceptions

Divisibility vs Division

Divisibility requires integer quotient; division may yield non-integer. Example: 3 divides 12, but 3 divides 10? No.

Zero and Divisibility

All integers divide 0 (a|0 ∀ a ≠ 0). Zero divides no integer except zero itself.

Negative Divisors

Divisibility defined for integers including negatives: a|b ⇔ ∃ k ∈ ℤ with b = a·k, sign of divisor irrelevant for divisibility.

References

• Hardy, G.H., & Wright, E.M. - An Introduction to the Theory of Numbers, Oxford University Press, 2008, pp. 1-300.
• Rosen, K.H. - Elementary Number Theory and Its Applications, Pearson, 2010, pp. 45-150.
• Niven, I., Zuckerman, H.S., & Montgomery, H.L. - An Introduction to the Theory of Numbers, Wiley, 1991, pp. 20-250.
• Burton, D.M. - Elementary Number Theory, McGraw-Hill, 2010, pp. 60-220.
• Ore, O. - Number Theory and Its History, Dover Publications, 1988, pp. 100-280.