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
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?

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search