Help with an example from venn diagram chapter  TOPIC_SOLVED

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

Help with an example from venn diagram chapter

Postby tonyc1970 on Wed Sep 25, 2013 2:31 am

Hi, I am trying to understand this example from my study guide and am getting no where with it and need some help.

Example: How many positive integers n with 1 <= n <= 2500 are prime relative to 3 and 5?

The example come from the chapter on Venn Diagrams.

Let U = {n E Z+ | 1 <= n <= 2500}
We need to establist the number or positive interger in U such that gcd(3, n) = 1 and gcd(5, n) = 1

In this case, it is easier to count the integers that are relative primes with 3 and 5
Note that an integer is not a relative prime with 3 if it is a multiple of 3, Thus,
A = {n E U | gcd(3, n) = 1}
A = {n E U | gcd(3, n) = 1} = {3n E U | 1 <= n <= 1249} Can someone explain how 1249 is obtained?
and
B = {n E U | gcd(5, n) = 1} = {5n E U | 1 <= n <= 500} Can someone explain how 500 is obtained?

Thus, A = {n E U | gcd(3, n) = 1} and B = {n E U | gcd (5, n) = 1}

We want to find | A intersection B| = |A U B| = |U| - |A U B|

We have
|A intersection B | = |{15k E U | 1 <= k <= 166}| = 166

Thus,
|A intersection B|
=|U| - |A| - |B| + |A intersection B|
= 2500 - 1249 - 500 + 166 = 917

Thanks for any help.

Tony
tonyc1970
 
Posts: 13
Joined: Fri Aug 02, 2013 4:58 pm

Sponsor

Sponsor
 

Re: Help with an example from venn diagram chapter  TOPIC_SOLVED

Postby anonmeans on Wed Sep 25, 2013 10:18 am

tonyc1970 wrote:
Example: How many positive integers n with 1 <= n <= 2500 are prime relative to 3 and 5?

Let U = {n E Z+ | 1 <= n <= 2500}
We need to establist the number or positive interger in U such that gcd(3, n) = 1 and gcd(5, n) = 1

Note that an integer is not a relative prime with 3 if it is a multiple of 3, Thus,
A = {n E U | gcd(3, n) = 1}
A = {n E U | gcd(3, n) = 1} = {3n E U | 1 <= n <= 1249}

Can someone explain how 1249 is obtained?

They went from "n, with gcd(3, n) = 1" to "3n", with the limit on "n, with gcd(3, n) = 1" being 2,500. Then the limit on "3n" is 2,500: 3n < 2,500 so n < 2,500/3 = 833.33... So it SHOULD have been "3n, with n < 833". You can see this working with the other one: 5n < 2,500, so n < 2,500/5 = 500.

Maybe this example started with "prime relative to 2" (so 2n < 2,500, n < 2,500 = 1250, that they switched to 1249 for some reason). I think they just made a mistake in the book. Plus, this is a really weird way to do Venn Diagrams.
anonmeans
 
Posts: 48
Joined: Sat Jan 24, 2009 7:18 pm


Return to Discrete Math

cron