Subsets and Greatest Common DivisorDate: 03/26/99 at 16:38:57 From: Megan Subject: Math for elementary teaching Question 1: A finite set A with k elements, i.e. n(A) = k, has a finite number of subsets. How many subsets does A have? Solve this problem by considering simple cases. List all the subsets of A (sub)0, A (sub)1, A (sub)2, and A (sub) 3. How many subsets are in each case? Make a conjecture about the number of subsets of A (sub)8 and of A (sub)n for any whole number n. Question 2 Use Euclid's Algorithm to find the GCD of the two numbers 2046 and 1122. (Show all calculations.) When you have found the GCD write each number 2046 and 1122 as a product of this common divisor and another factor. Use the GCD (2046 and 1122) that you just found to compute the least common multiple of 2046 and 1122. Date: 03/26/99 at 17:37:52 From: Doctor Santu Subject: Re: Math for elementary teaching This is easier than it looks. You have not told us what A_1, A_2 and so on are. (Or, on the other hand, it might be material that you were given in class.) Let us begin with a simple case: a set with only one element, like, A = {1} As you know, the Empty Set (let us call it E} is a subset of all other sets. So the subsets of this set A are E, and {1} So, if A has one element, it has 2 different subsets. (It makes no difference what the actual elements are; if it contains one element, it will always have two subsets.) Let us consider B = {1,2}, a 2-member set. The subsets are: E, {1}, {2}, and {1,2} That is four different subsets. This is true for every two-element set. How about C = {1,2,3}, a three-element set? What are the different possible subsets? I will start you off, and you finish the list. E, {1}, {2}, {1,2}, {3}, .... There should be three more, all containing the new member, 3. Part of what your teacher is trying to do is to see if you can figure this out on your own, because some kids can, (little kids!) and you have to practice being one jump ahead of the little tykes. As you can see, so far all we have done is just list the possible subsets. The data so far are: A has 1 element --> A has 2 subsets. B has 2 elements --> B has 4 subsets. C has 3 elements --> C has 8 subsets. Question: Is it always true that every additional element in the original set doubles the number of subsets you end up with? Answer: Yes. Question: Why? Answer: Well, consider, B had 4 subsets. C has those very same 4 subsets, and 4 new ones. How come? The new subsets C has are the same as the old subsets B had, WITH 3 ADDED ON. Obviously, this will happen when you throw in the number 4 to make D = {1,2,3,4}, and D will have twice as many sets as C, that is, 16. ---------------------------------------- I'll get you started on the second question. The GCD of two numbers is the same as the GCD of the smaller of them and their difference. For instance, the GCD of 200 and 196, or GCD(200, 196), is the same as GCD(196, 4), where 4 = 200 - 196. So we can cheat a little, and find GCDs of small numbers. ["GCD" means greatest common divisor, or the largest number that goes into both; e.g. GCD 60 and 48 is 12, since 12 goes into both of them evenly, but nothing larger than 12 does.] So, GCD(2046, 1122) = GCD(1122, 2046 - 1122) = GCD(1122, 924) [that is a little easier already. Let us do it again:] = GCD(924,1122-924) = GCD(924,198). Now you take over! (By the way, instead of just subtracting, you can take the remainder after division by the smaller number. So, GCD(924, 198) = GCD(198, x) where x is the remainder after you divide 924 by 198, which is 924-792 = ?) Once you get to really tiny numbers, like GCD (45, 9), the answer will be (9). The LCM (least common multiple) is the smallest number that can be DIVIDED BY both the numbers. Little known fact: if a and b are any two numbers, lcm(a,b) . gcd(a,b) = a.b Example: lcm (12, 15) = 60. gcd (12, 15) = 3. lcm(12,15) . gcd(12,15) = 60.3 = 180. But, 12.15 = 180. So if I know the gcd of 12 and 15, to find the lcm, I go lcm = 12*15 / gcd = 180 / 3 = 60. That is the last part of the second question. - Doctor Santu, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/