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