The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Subsets and Greatest Common Divisor

Date: 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 

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

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 
- Doctor Santu, The Math Forum   
Associated Topics:
High School Number Theory
High School Sets

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.