1

Consider the equivalence relation $E$ defined on the set $A = \{x \in \mathbb N \mid 1 \le x \le 40\}$ by
$xEy$ if and only if $x$ and $y$ have the same set of prime factors.

(a) Provide two distinct equivalence classes under $E$ that have the largest cardinality.

You should write down all elements in the equivalence classes in (a)

The answer for (a) are $[2] = \{2, 4, 8, 16, 32\}$ and $[6] = \{6, 12, 18, 24, 36\}$. Can anyone show me how to get this?

Michael Hardy
  • 1
f.fans
  • 11
  • 1
    The way you word this question sounds like homework. If that's the case, then what have you tried in order to solve the problem? – Chris Jun 15 '17 at 01:39
  • @Chris it's not a homework, it's a test question from uni, and I got it wrong, that's why i ask this question – f.fans Jun 15 '17 at 01:56

2 Answers2

1

Prime factorize all the numbers between 1 and 40, group them into their equivalence classes by seeing which ones have the same prime factors, and then see that the two largest have the same cardinality.

Duncan Ramage
  • 6,928
  • 1
  • 20
  • 38
0

The prime numbers in the set $\{1,\ldots,40\}$ are $2,3,5,7,11,13,17,19,23,29,31,37.$

What are the equivalence classes?

First there are those with no prime factors: $\quad 1$

Then there are those whose only prime factor is $2$: $\quad2,4,8,16,32$

Then there are those whose only prime factor is $3$: $\quad 3,9,27$

Then there are those whose only prime factor is $5$: $\quad 5,25$

Then there are those whose only prime factor is $7$: $\quad7$
(Since $7^2$ and higher powers of $7$ are not in the set $\{1,\ldots,40\}$.)

As with $7$, so also with $11,13,17,19,23,29,31,37:$ Each class has only one number.

Then there are those whose prime factors are $2$ and $3:$ $\quad6,12,18,24,36$

Then there are those whose prime factors are $2$ and $5:$ $\quad10,20,40$

Then there are those whose prime factors are $2$ and $7:$ $\quad14,28$

Then $2$ and $11:$ $\quad22$

As with $11$, so also with $13,17,19:$ There is just one number in each class. And with $23$ and higher primes, there are none whose prime factors are just that number and $2$.

Then there are those whose prime factors are $3$ and $7:$ $\quad21$

Then $3$ and $11:$ $\quad33$

Then $3$ and $13:$ $\quad39$

For $3$ and anything else we've gone above $40.$

Then $5$ and $7:$ $\quad35$.

For $5$ and anything else we've gone above $40.$ And similarly for every pair of primes that are at least $5.$

Then $7$ and $11:$ There are none, and similarly for any pair of primes that are at least $7$.

Now sets of three:

If the prime factors are $2,3,5,$ then we have just one number.

If they're $2,3,7$ then we're above $40.$

All other sets of three primes start beyond $40,$ as do all sets of more than three primes. So now our list is complete. Which classes have the largest number of members?

Michael Hardy
  • 1