Ex 11.2, 3 - Divisors occur in pairs. For instance, the divisors of 18 - Exercise Set 11.2

part 2 - Ex 11.2, 3 (i) - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Ex 11.2, 3 (i) - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 4 - Ex 11.2, 3 (i) - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 5 - Ex 11.2, 3 (i) - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo ยท Class 9 Explore Class 9

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.

CA Maninder Singh's photo - Co-founder, Teachoo

Made by

CA Maninder Singh

CA Maninder Singh is a Chartered Accountant qualified since 2010 and an educator teaching since 2006. At Teachoo, he draws on his accounting and tax experience to explain Accounts, Income Tax and GST through step-by-step lessons and practical examples.

For an uninterrupted learning experience, students can use Teachoo Black to remove ads and focus better.