Last updated at October 28, 2026 by Teachoo
Transcript
Ex 11.2, 3 (i) Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6). (i) If we write out divisors in pairs, how many numbers do we have to examine between 1 and n to find all the divisors of n? For n = 18 The divisor pairs are (1, 18), (2, 9) and (3, 6) This means, 18 = 1 ร 18 = 2 ร 9 = 3 ร 6 Now, If we find a divisor ๐, Partner of j in divisor pair = (๐)/(๐) For example Finding that 2 divides 18 also tells us that: (18)/(2)=9 is a divisor. We do not need to discover 9 separately. Where should the search stop? At least one member of every divisor pair must be less than or equal to sqrt(๐). Suppose both members were greater than sqrt(๐). Their product would then be greater than: sqrt(๐) ร sqrt(๐)=๐ which is impossible because their product must equal ๐. Therefore, checking: 1, 2,โฆ, [sqrt(๐)] is sufficient. The symbol โsqrt(๐)โ means the greatest integer not exceeding sqrt(๐). We need to examine only โsqrt(๐)โ candidates. which is impossible because their product must equal ๐. Therefore, checking: 1, 2, 3โฆ, [sqrt(๐)] is sufficient. The symbol [sqrt(๐)] means the greatest integer not exceeding sqrt(๐). We need to examine only [sqrt(๐)] candidates. Example: ๐=๐๐ Since: 4^(2)<18<5^(2) we check only 1, 2, 3, 4 We have found all six divisors using four checks instead of eighteen. Special case: perfect squares For 36 , check candidates up to 6 The pairs are: (1, 36),(2, 18),(3, 12),(4, 9),(6, 6) The final pair repeats the same divisor, so record 6 only once. Candidate j | Does it divide 18? | Divisors obtained 1 | Yes | 1, 18 2 | Yes | 2, 9 3 | Yes | 3, 6 4 | No | None Pairwise divisor algorithm Start with an empty list. Examine positive integers ๐ while ๐^(2)โค๐. If ๐ divides ๐ : Add ๐. Add (๐)/(๐), unless (๐)/(๐)=๐. Report the list.