Chapter 16 — Playing With Numbers

Definition: A factor (or divisor) of a number n is an integer d such that d divides n exactly (n = d × q). A multiple of a number n is any integer m that can be written as n × k for some integer k. Factors of a number are finite; multiples are infinite.

Key ideas and methods:

• Factor pairs: If d is a factor of n, then n/d is the paired factor. List factor pairs to find all factors.
• Prime factorization: Express n as n = p1^a · p2^b · ... (where p1, p2 are primes). This is the basis for finding HCF (GCD), LCM and number of divisors.
• HCF / GCD (Highest Common Factor or Greatest Common Divisor): For several numbers, take each prime common to all and use the minimum exponent: HCF = ∏ p_i^{min(exponents)}. Euclid’s algorithm (repeated division) is a fast method for two numbers.
• LCM (Least Common Multiple): For several numbers, take each prime that appears in any number and use the maximum exponent: LCM = ∏ p_i^{max(exponents)}. For two numbers, LCM(a,b) = |a·b| / GCD(a,b).
• Divisibility tests: Quick checks help find factors: 2 (last digit even), 3 (sum of digits divisible by 3), 5 (last digit 0 or 5), 9 (sum of digits divisible by 9), 11 (difference of alternating digit sums divisible by 11), etc.
• Number of positive divisors: If n = ∏ p_i^{a_i}, the number of positive divisors τ(n) = ∏ (a_i + 1). The product of all positive divisors = n^{τ(n)/2}.

Important distinctions: Factors divide the number exactly; multiples are numbers you obtain by repeated addition (or multiplication) of the original number. Use factor trees and prime-power rules to compute HCF and LCM reliably.

Definition: A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. A composite number is a natural number greater than 1 that has more than two positive divisors (i.e. it can be factored into smaller natural numbers).

Special cases: 0 is neither prime nor composite. 1 is neither prime nor composite (it has only one positive divisor).

Basic properties:

• Every even prime number is 2; all other even numbers are composite because they are divisible by 2.
• If n is composite, it has a prime factor less than or equal to sqrt(n). Thus to test primality of n you only need to check divisibility by primes ≤ sqrt(n).
• Prime factorization (unique factorization): every integer > 1 can be written uniquely (up to order) as a product of primes — this is the Fundamental Theorem of Arithmetic.

How to find primes — Sieve of Eratosthenes (brief steps):

• Write the list 2,3,4,...,N. Start with the first number (2), mark its multiples (4,6,8,...).
• Move to the next unmarked number (3), mark its multiples (9,12,15,...). Continue up to sqrt(N).
• Numbers remaining unmarked are primes.

Divisibility checks (useful shortcuts):

• Divisible by 2: last digit even.
• Divisible by 3: sum of digits divisible by 3.
• Divisible by 5: last digit 0 or 5.
• Divisible by 11: alternating sum of digits difference is multiple of 11.

Prime factorization and consequences:

• Write n = p1^a1 * p2^a2 * ... * pk^ak, where p1,p2,... are distinct primes and a1,a2,... are positive integers.
• Number of positive divisors of n = (a1 + 1)(a2 + 1)…(ak + 1).
• Sum of all positive divisors of n = Π (p_i^{a_i+1} − 1)/(p_i − 1).
• For two numbers a and b: HCF(a,b) × LCM(a,b) = a × b (useful when prime factors are known).

Types and patterns:

• Twin primes: pairs of primes that differ by 2 (e.g. 11 and 13).
• Composite numbers can be expressed as product of primes (e.g. 84 = 2^2 × 3 × 7).

Study tips: Practice factor trees for composite numbers, use the sieve to generate primes quickly, and for checking primality use divisibility by primes up to sqrt(n).

What are tests of divisibility?
A test (or rule) of divisibility is a quick method to decide whether a given integer is divisible by another integer without performing full division. These tests use properties of base‑10 representation of numbers and modular arithmetic.

Why they work (brief ideas):

• Any integer can be written using its digits: if N has digits ...d3 d2 d1 d0 then N = d0 + 10d1 + 10^2 d2 + ... . Tests use congruences of powers of 10 modulo the divisor (for example 10 ≡ 1 (mod 3), 10 ≡ −1 (mod 11)).
• For small divisors we use simple reductions: e.g., because 10 ≡ 1 (mod 3 and mod 9), the sum of digits rule works for 3 and 9; because 10 ≡ −1 (mod 11), alternating sum works for 11; because 100 ≡ 0 (mod 4) the last two digits decide divisibility by 4, and so on.

Common divisibility rules (intuitive statements and short reasoning):

• 2: A number is divisible by 2 iff its last digit is even (0,2,4,6,8). Reason: 10 ≡ 0 (mod 2), so only the units digit matters.
• 5: Divisible iff last digit is 0 or 5. (10 ≡ 0 (mod 5)).
• 10: Divisible iff last digit is 0. (10 divides N iff units digit 0.)
• 3: Divisible iff sum of digits is divisible by 3. (Because 10 ≡ 1 (mod 3), so each digit contributes itself mod 3.)
• 9: Divisible iff sum of digits is divisible by 9. (10 ≡ 1 (mod 9)).
• 4: Divisible iff the number formed by last two digits is divisible by 4. (100 ≡ 0 (mod 4)).
• 8: Divisible iff the number formed by last three digits is divisible by 8. (1000 ≡ 0 (mod 8)).
• 6: Divisible iff divisible by both 2 and 3.
• 12: Divisible iff divisible by both 3 and 4.
• 11: Divisible iff the alternating sum of digits (sum of digits in odd places − sum of digits in even places) is a multiple of 11. Reason: 10 ≡ −1 (mod 11), so powers of 10 alternate signs.
• 7 (useful rule): Take the last digit, double it and subtract from the number formed by remaining leading digits; repeat if needed. If the result is divisible by 7, the original is divisible by 7. (Algebra: 10a + b ≡ 0 (mod 7) ⇔ a − 2b ≡ 0 (mod 7)).
• 13 (useful rule): Remove the last digit, multiply it by 4 and add to the remaining leading number; repeat as needed. If result divisible by 13 then original is divisible by 13. (Because 10a + b ≡ 0 (mod 13) ⇔ a + 4b ≡ 0 (mod 13)).
• 15: Divisible iff divisible by both 3 and 5.
• 25: Divisible iff last two digits form a number divisible by 25 (i.e., last two digits 00, 25, 50, 75).

How to apply — procedural tips

• For large numbers use repeated application of the simple rule (for 7 or 13 you may repeat the digit removal process until a small number is obtained).
• Combine rules: to test for composite divisors (like 6, 12, 15), check their prime factor rules (6 = 2×3 etc.).
• When a test gives a small remainder or small number, it’s easy to confirm divisibility by direct division.

Usefulness / real-life relevance

• Quick checks while grouping items (e.g., packing identical items into boxes), verifying invoices and ledger totals, verifying barcodes or check digits in simple schemes, and doing mental arithmetic in exams.

What is Prime Factorisation? Prime factorisation of a natural number is expressing it as a product of prime numbers. Every composite number can be written as a product of primes. For example, 84 = 2 × 2 × 3 × 7.

Why it matters (Fundamental idea): By the Fundamental Theorem of Arithmetic, each integer greater than 1 has a unique prime factorisation (up to order). So a number n can be written as n = p1^a1 × p2^a2 × ... × pk^ak, where p1, p2, ..., pk are distinct primes and a1, a2, ..., ak are positive integers.

Methods to find prime factors:

• Repeated division (short division / ladder method): Divide by the smallest prime that goes into the number, continue dividing the quotient until you get 1.
• Factor tree: Break the number into two factors, keep factoring composite factors until all leaves are prime.
• Trial division: Test divisibility by primes 2, 3, 5, 7, 11, ... up to √n.

How to write compactly: Group identical prime factors using exponents. Example 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2^3 × 3^2 × 5.

Applications: Prime factorisation helps in simplifying fractions, finding HCF/GCD and LCM, solving problems on divisibility and equal grouping (tiling, packets), and underlies topics in cryptography and number theory.

Statement: Every integer greater than 1 can be written as a product of prime numbers, and this representation is unique except for the order of the prime factors. This is called the Fundamental Theorem of Arithmetic or Unique Prime Factorisation.

Definitions: A prime number has exactly two distinct positive divisors: 1 and itself. A composite number has more than two positive divisors. The number 1 is neither prime nor composite.

How to find prime factorisation (methods):

• Division method: Divide repeatedly by the smallest possible prime until the quotient becomes 1. Collect the primes used.
• Factor tree: Break the number into two factors, continue factoring each composite factor until all leaves are prime.

Example idea (step-by-step): To factor 360: divide by 2 → 180, divide by 2 → 90, divide by 2 → 45, divide by 3 → 15, divide by 3 → 5, divide by 5 → 1. Collecting primes: 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2^3 × 3^2 × 5.

Uniqueness (sketch): If a number had two different prime factorizations, one can use the fact that a prime dividing a product must divide at least one factor (Euclid's lemma) to show the primes and their powers must match in both factorizations. Hence the factorisation is unique up to ordering.

Important note: The exponent form, called the canonical form, writes n = p1^a1 × p2^a2 × ... × pk^ak where p1, p2, ..., pk are distinct primes and a1, a2, ..., ak are positive integers.

Definition: The Highest Common Factor (HCF) of two or more integers (also called the Greatest Common Divisor, GCD) is the largest positive integer that divides each of them exactly without leaving a remainder.

Why it matters: HCF is used to simplify fractions, divide objects into equal groups with no leftovers, and solve problems involving common measures (e.g., arranging items, packaging).

Methods to find HCF:

• Listing factors: Write all factors of each number and pick the greatest common one. (Good for small numbers.)
• Prime factorization: Express each number as a product of prime powers. The HCF is the product of all common primes raised to the minimum exponent found in each factorization. Example formula: if a = p1^a1 * p2^a2 * ... and b = p1^b1 * p2^b2 * ..., then HCF(a,b) = p1^min(a1,b1) * p2^min(a2,b2) * ...
• Euclid's division algorithm (efficient for large numbers): For two numbers a and b (a > b), compute a ÷ b = q with remainder r. Then HCF(a,b) = HCF(b,r). Repeat until remainder is 0; the last nonzero remainder is the HCF.

Properties:

• HCF(a,b) divides both a and b.
• For two numbers a and b: HCF(a,b) × LCM(a,b) = a × b.
• If d = HCF(a,b), then HCF(a/d, b/d) = 1 (the reduced numbers are coprime).
• If a divides c and b divides c, then HCF(a,b) also divides c.

Steps to use Euclid's algorithm (short):

1. Divide the larger number by the smaller number and find the remainder.
2. Replace the larger number by the smaller number and the smaller number by the remainder.
3. Repeat until the remainder is 0. The nonzero divisor at that step is the HCF.

Tip: For three or more numbers, find HCF pairwise: HCF(a,b,c) = HCF(HCF(a,b), c).

Definition: The Least Common Multiple (LCM) of two or more non‑zero integers is the smallest positive integer that is divisible by each of them.

Why it matters: LCM helps solve problems where events with different repeating intervals must occur together (schedules, cycles, packing, synchronisation).

Methods to find LCM

• Listing multiples: Write multiples of each number and pick the smallest common one. (Good for small numbers.)
• Prime factorization: Express each number as a product of prime powers. For each prime, take the highest power that appears in any factorization; LCM is the product of these highest powers.
• Division (ladder) method: Divide the numbers simultaneously by common primes until only 1s remain; multiply all divisors to get the LCM.
• Using GCD (for two numbers): LCM(a, b) = |a × b| / GCD(a, b). This is efficient when GCD is known.
• For more than two numbers: LCM(a, b, c, ...) = LCM(LCM(a, b), c, ...). Alternatively use prime powers across all numbers.

Worked examples

1. Find LCM of 12 and 18.

   Prime factors: 12 = 2² × 3, 18 = 2 × 3².

   Take highest powers: 2², 3² → LCM = 2² × 3² = 4 × 9 = 36.

   Check using GCD: GCD(12, 18) = 6 ⇒ LCM = (12 × 18) / 6 = 216 / 6 = 36.

2. Find LCM of 4, 6 and 10.

   Prime factors: 4 = 2², 6 = 2 × 3, 10 = 2 × 5.

   Highest powers: 2², 3, 5 ⇒ LCM = 2² × 3 × 5 = 4 × 3 × 5 = 60.

3. Small listing multiples example: Multiples of 8: 8, 16, 24, 32...; of 12: 12, 24, 36... → LCM = 24.

Properties & notes:

• LCM of positive integers is always positive.
• LCM(a, b) × GCD(a, b) = |a × b| for two integers a and b.
• LCM(0, n) is not usually defined in the basic school context; LCM is defined for non‑zero integers. (Many problems use positive integers.)
• LCM is useful for adding/subtracting fractions (common denominator) and for solving problems with repeating events.

What are HCF and LCM?
HCF (Highest Common Factor), also called GCD (Greatest Common Divisor), of two positive integers is the largest integer that divides both. LCM (Least Common Multiple) of two positive integers is the smallest positive integer that is a multiple of both.

Key relationship (for two numbers)
For any two positive integers a and b,

HCF(a, b) × LCM(a, b) = a × b

Why this is true (two short proofs)

• Using prime factorization: Write a and b as products of primes: a = ∏ p_i^{α_i}, b = ∏ p_i^{β_i}. Then HCF(a,b) = ∏ p_i^{min(α_i,β_i)} and LCM(a,b) = ∏ p_i^{max(α_i,β_i)}. Multiplying these gives ∏ p_i^{α_i+β_i} = a × b.
• Using gcd decomposition: Let g = HCF(a,b). Then write a = g·m and b = g·n where gcd(m,n)=1. LCM(a,b) must be g·m·n (since m and n are coprime). So HCF × LCM = g × (g·m·n) = (g·m) × (g·n) = a × b.

Important notes

• The product formula HCF×LCM = a×b holds for two positive integers. It does NOT directly generalize to three or more numbers in the same simple form.
• If a and b are coprime (HCF = 1), then LCM(a,b) = a×b.
• If a = b, then HCF = LCM = a and HCF×LCM = a² = a×b as expected.

How to use the relationship

• Compute LCM quickly if you know HCF: LCM = (a × b) / HCF.
• Compute HCF quickly if you know LCM: HCF = (a × b) / LCM.

Applications
This relationship helps when scheduling repeating events, cutting objects into largest equal pieces, or arranging things in equal groups. It simplifies calculation of one quantity when the other is known.

Definition: Two positive integers are called co-prime (or relatively prime) if their greatest common divisor (GCD) is 1. In other words, they have no prime factor in common.

How to tell whether two numbers are co-prime

• Prime factorization method: Factor both numbers into primes. If no prime appears in both factorizations, the numbers are co-prime. Example: 8 = 2×2×2 and 15 = 3×5 → no common prime → co-prime.
• Euclid's algorithm (efficient): Repeatedly replace the larger number by its remainder when divided by the smaller. If the final non-zero remainder is 1, the numbers are co-prime. This works fast even for large numbers.

Important properties

• Any two consecutive integers (n and n+1) are always co-prime.
• If gcd(a, b) = 1 then lcm(a, b) = a × b.
• If gcd(a, b) = 1 and a divides b·c, then a divides c. (Useful in many proofs.)
• Two different prime numbers are co-prime. A prime and 1 are co-prime. 1 is co-prime with every positive integer.
• For a positive integer n, the number of integers less than n and co-prime to n is given by Euler's totient function φ(n). (This is a more advanced concept but useful to know.)

Quick checks and tips

• Check small prime factors first (2, 3, 5, 7...). If a common small factor exists, they're not co-prime.
• Use Euclid's algorithm for large numbers: it requires only division and remainders.

Definitions

• Factor (Divisor): A number a is a factor of b if b ÷ a is an integer. Example: 3 is a factor of 12 because 12 ÷ 3 = 4.
• Multiple: A number is a multiple of a if it can be written as a × k for some integer k. Example: 24 is a multiple of 6 (6 × 4).
• Common Factors: Factors shared by two or more numbers. The greatest of these is the Highest Common Factor (HCF) or Greatest Common Divisor (GCD).
• Common Multiples: Multiples common to two or more numbers. The smallest positive common multiple is the Least Common Multiple (LCM).

How to find HCF (GCF)

• Listing method: List all factors of each number and pick the greatest common one. Works for small numbers.
• Prime factorization: Write prime factorization of each number. HCF is the product of common prime factors with the lowest powers.
• Euclidean algorithm (efficient for large numbers): repeatedly replace (a, b) by (b, a mod b) until remainder 0; the last non-zero remainder is the HCF.

How to find LCM

• Listing multiples: List multiples of each number until you find the first common one (good for small numbers).
• Prime factorization: LCM is the product of all prime factors present in any number, each taken with the highest power appearing in any factorization.
• Relation-based (two numbers): LCM(a, b) = |a × b| ÷ HCF(a, b).

Key ideas to remember

• HCF uses the minimum powers of common primes; LCM uses the maximum powers of all primes involved.
• HCF is useful for dividing things into equal groups with no leftovers. LCM is useful to find when repeating events coincide (scheduling, cycles).

What the topic means
In "Playing with Numbers", methods and algorithms are step-by-step procedures used to solve number problems reliably — for example, determining whether a number is divisible by another, finding the Highest Common Factor (HCF) and Least Common Multiple (LCM), or factoring numbers into primes. Algorithms make these processes systematic, fast and easy to follow.

Key methods covered

1. Divisibility Tests — quick checks (rules) to tell if a number is divisible by 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, etc., using digit patterns instead of full division.
2. Prime Factorisation (factor tree or repeated division) — write a number as a product of prime powers (e.g., 180 = 2^2 × 3^2 × 5). This is the foundation for several algorithms.
3. HCF (or GCD) and LCM by Prime Factors — get HCF by taking the minimum powers of common primes and LCM by taking the maximum powers of all primes appearing in the numbers.
4. Euclid’s Algorithm (Division Algorithm) — an efficient method to compute HCF: repeatedly apply division and take remainders until remainder is 0; the last nonzero remainder is the HCF.
5. Relationship between HCF and LCM — for two positive integers a and b: HCF(a,b) × LCM(a,b) = a × b. This gives a fast way to get LCM if HCF is known (and vice versa).

Why these methods help
They reduce repetitive work, allow working with very large numbers, and provide visual/structured ways to reason about factors and multiples. They also connect with real-life planning, scheduling, measurements and optimization problems.

What this topic is about
"Applications and Problem Solving" uses the ideas of factors, multiples, Highest Common Factor (HCF) and Least Common Multiple (LCM) to solve real-life problems. The key skill is to decide whether a situation needs HCF (to divide into equal parts or find the largest possible size) or LCM (to find when repeating events coincide or the smallest common period).

Key concepts and methods

• HCF (GCD): Largest number that divides two or more numbers exactly. Useful for making equal groups or finding the largest possible identical item size.
• LCM: Smallest positive number that is a multiple of two or more numbers. Useful for scheduling recurring events that must coincide or for finding when cycles repeat together.
• How to find HCF and LCM:
  • Prime-factorization method: write prime factors of each number, HCF = product of common primes with lowest powers, LCM = product of all primes with highest powers.
  • Division (successive division) method: divide by common primes repeatedly to get HCF and LCM together.
  • Euclid's algorithm (useful for HCF of two numbers): repeatedly replace larger number by remainder until remainder is zero; last nonzero remainder is HCF.
• Problem-solving steps:
  1. Read carefully and identify what is being asked: equal division or simultaneous occurrence?
  2. Decide HCF (for equal groups/largest size) or LCM (for repeating cycles/meeting times).
  3. Convert units if needed (minutes, hours, seconds) so all numbers use the same unit.
  4. Use prime factorization, division method, or Euclid's algorithm to compute HCF/LCM.
  5. Interpret the result in context (e.g., in minutes, in groups, in rows).

Tips: Draw a timeline for LCM problems (showing repeating events) and draw equal groups or boxes for HCF problems. Always check units and reduce the final answer to a meaningful phrase (minutes, hours, boxes, rows, etc.).