A brief note on Common Factors, the Euclidean Algorithm and Divisors . Try each question before you open its answer.
The key facts HCF and LCM: smaller and larger exponent of each prime. Product rule: gcd ( a , b ) ⋅ lcm ( a , b ) = a b \gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab g cd( a , b ) ⋅ lcm ( a , b ) = ab , for two numbers only. Subtracting: gcd ( a , b ) = gcd ( a − k b , b ) \gcd(a, b) = \gcd(a - kb, b) g cd( a , b ) = g cd( a − k b , b ) . Coprime form: a = d x a = dx a = d x , b = d y b = dy b = d y with gcd ( x , y ) = 1 \gcd(x, y) = 1 g cd( x , y ) = 1 . Euclidean algorithm: gcd ( a , b ) = gcd ( b , r ) \gcd(a, b) = \gcd(b, r) g cd( a , b ) = g cd( b , r ) ; the HCF is the last non-zero remainder. Bezout: a x + b y = gcd ( a , b ) ax + by = \gcd(a, b) a x + b y = g cd( a , b ) has integer solutions; a x + b y = c ax + by = c a x + b y = c is solvable exactly when gcd ( a , b ) ∣ c \gcd(a, b) \mid c g cd( a , b ) ∣ c . Euclid's lemma: p ∣ a b p \mid ab p ∣ ab gives p ∣ a p \mid a p ∣ a or p ∣ b p \mid b p ∣ b . Divisors: τ ( n ) = ∏ ( a i + 1 ) \tau(n) = \prod (a_i + 1) τ ( n ) = ∏ ( a i + 1 ) and σ ( n ) = ∏ p i a i + 1 − 1 p i − 1 \sigma(n) = \prod \dfrac{p_i^{a_i + 1} - 1}{p_i - 1} σ ( n ) = ∏ p i − 1 p i a i + 1 − 1 . Pairs: τ ( n ) \tau(n) τ ( n ) is odd only for squares; the product of the divisors is n τ ( n ) / 2 n^{\tau(n)/2} n τ ( n ) /2 . Perfect: 2 p − 1 ( 2 p − 1 ) 2^{p-1}(2^p - 1) 2 p − 1 ( 2 p − 1 ) with 2 p − 1 2^p - 1 2 p − 1 prime. Practise with new numbers
A program to try The program checks the product rule, searches for Bezout's x x x and y y y , and counts divisors from a list.
Read it first. Then run it. Does the count of divisors match the formula?
1. Change a, b = 84, 132 to two coprime numbers. What HCF and what pair ( x , y ) (x, y) ( x , y ) do you get?
Mistakes to avoid The product rule for three numbers. It does not hold. Stopping the algorithm early. Go on until a remainder is 0 0 0 . Expecting Bezout's x x x and y y y to be unique or positive. Multiplying exponents instead of exponents plus one. Assuming every 2 p − 1 ( 2 p − 1 ) 2^{p-1}(2^p - 1) 2 p − 1 ( 2 p − 1 ) is perfect. It needs 2 p − 1 2^p - 1 2 p − 1 prime. Check yourself Find gcd ( 84 , 132 ) \gcd(84, 132) g cd( 84 , 132 ) by the Euclidean algorithm. Stuck? Show a hint Show the answerTwo numbers have HCF 7 7 7 and product 1764 1764 1764 . Find their LCM. Stuck? Show a hint Show the answerIs 10 x + 14 y = 5 10x + 14y = 5 10 x + 14 y = 5 solvable in integers? Stuck? Show a hint Show the answerHow many divisors does 2 4 ⋅ 5 3 2^4 \cdot 5^3 2 4 ⋅ 5 3 have, and what is their sum? Stuck? Show a hint Show the answerWhich numbers below 50 50 50 have an odd number of divisors? Stuck? Show a hint Show the answerSources David M. Burton, Elementary Number Theory , Chapter 2 and Chapter 6. Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory of Numbers , Chapters 1 and 4.