Find the largest cardinality 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?
 A: 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.
A: 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?
