Instructors:
|
Mr. Ahmed Hefny
Mr. Rameel Rizvi |
Attendance:
|
Aidan, Areej, Ayyan, Omar
|
Homework:
|
None
|
Class Activity:
|
Placement test and follow-up discussion.
|
Concepts:
| |
Student Difficulties:
| GCD and LCM |
Notes:
|
- Every whole number (>1) can be written as a product of prime numbers.
- When we divide a whole number X by Y, we essentially remove from X all the prime factors that constitute Y. For example, if X = 12 = 2*2*3 and Y = 4 = 2*2 then X/Y = 3.
- Therefore, for X/Y to be a whole number, X must contain all the prime factors of Y (repeated factors must be repeated with at least the same multiplicity). In this case we say that "Y is a divisor of X" and "X is a multiple of Y". For example, "4 is a divisor of 12" and "12 is a multiple of 4".
- A "common multiple" of two numbers is a number that can be evenly divided by both of them (i.e. is a multiple of both of them). A common multiple of X and Y must contain all the prime factors of X and the prime factors of Y. For example 36=2*2*3*3 is a common multiple of 6=2*3 and 4=2*2*3.
- Given two numbers X and Y, an obvious common multiple is X*Y.
- The "least common multiple (LCM)" of X and Y is the smallest number that can be divided by both of them-- that is, any smaller number will not be a common multiple. To find the LCM, we enumerate the prime factors of X and Y. The LCM must contain each prime factor with the highest multiplicity in X and Y. For example:
If X = 12 = 2*2*3 and Y = 90 = 2*3*3*5
Then the LCM has to contain 2's, 3's and 5's as prime factors.
Since 2 is repeated twice in X but only once in Y, we need to include 2 twice.
Similarly, 3 is repeated twice in Y and once in X, so we need to include 3 twice.
Finally, There is only one 5 in Y and none in X, so we need to include 5 once.
That gives LCM = 2*2*3*3*5 = 180.
If we add more factors to the LCM is won't be "least" anymore. If we remove factors it won't be a common multiple anymore. Hence, it is indeed the least common multiple.
- A "common divisor" of two numbers is a number that evenly divides both of them. A common divisor of X and Y must have its prime factors contained in both X and Y. For example 2 is a common divisor of 6=2*3 and 4=2*2*3.
- The most trivial common divisor between any two numbers is 1.
- The "greatest common divisor (GCD)" of X and Y is the largest number that divides both of them-- that is, any larger number will not be a common divisor. To find the GCD, we enumerate the prime factors of X and Y. The GCD must contain each prime factor with the lowest multiplicity in X and Y. For example:
If X = 12 = 2*2*3 and Y = 90 = 2*3*3*5
Since 2 is repeated twice in X but only once in Y, we need to include 2 once.
Similarly, 3 is repeated twice in Y and once in X, so we need to include 3 once.
Finally, There is only one 5 in Y and none in X, so we need will not include 5.
That gives GCD = 2*3 = 6.
If we add more factors to the GCD is won't be a common divisor anymore. If we remove factors it won't be "greatest" anymore. Hence, it is indeed the greatest common divisor. If there are no common prime factors in X and Y, the GCD is 1.
Note:
We can also talk about GCD and LCM of more than two numbers, the same principle and procedure apply.
