Listing the equivalence classes of a specific relation on a set

Question

Say we have the set $S=\{1, 2, 3, ..., 20\}$ and we define our relation (R) as

For every $x, y \in S$, $xRy$ iff for every prime $p, p | x \iff p | y$

This relation is an equivalence relation (as it is reflexive, symmetric and transitive) so I want to go ahead and find the equivalence classes for this relation.

So from my understanding, I'm looking for the ordered pairs in $S$ where $x$ and $y$ share a prime factor. With this in mind I believe one of the classes would be $\{5, 10, 15, 20\}$ as they all share the prime $5$ as a factor. I was wondering if there was some sort way to determine and list these equivalence classes without manually going through and listing all the ordered pairs?

Edit - I understand my initial understanding of the relation was incorrect and $\{5, 10, 15, 20\}$ isn't a valid equivalence class.

Answer 1

The primes $\le 20$ are $\{2,3,5,7,11,13,17,19\}$.

A number has a unique prime factorization. And two numbers are equivalent if there prime factors is from the same set of primes.

So consider ever possible set of primes:

Set 1: $\emptyset$. Consider the set of numbers with no prime factors. That is $\{1\}$ So that is the first equivalence class $\{1\}$

Set 2: $\{2\}$. Consider the set of numbers with only $2$ as a prime factor. That is $\{2^k\}= \{2,4,8,16\}$. That's the second equivalence class.

Set 3: $\{2,3\}$. Consider $\{2^m3^n\} = \{6, 12,18\}$. That's the third class.

Set $\{2,3,5\}$. Well $2*3*5=30$ and ther are no such numbers. The cant be any other sets with $2$ and $3$.

Set 4: $\{2,5\}$. Consider $\{2^m5^n\}=\{10,20\}$. That's the fourth

Set $\{2,5,7\}$. Well, $2*5*7=70$ so there are no more three element sets with $2$.

Set 5: $\{2,7\}$. Consider $\{2^m7^n\} = \{14\}$. That's the fifth.

And $2*11=22> 20$ so there are no more sets containing $2$.

Set 6: $\{3\}$ and the sixth equivalence class is $\{3^k\} = \{3,9\}$.

Set 7: $\{3,5\}$ and the seventh equivalce class is $\{3^m5^n\}=\{15\}$.

$3*7=21$ so there are no more sets with $3$. And for and primes $p, q > 3$ then $pq \ge 5*7=35$ so there are no more set to consider than just the sets with a single prime.

So the next equivalence classes are:

Set 8: $\{5\}$. The eighth equivalence class is $\{5^k\}=\{5\}$. Note for $p\ge 5$ then $p^2 > 20$ so the next equivalence classes will only contain the primes.

So

Class 9: $\{7\}$; Class 10: $\{11\}$; Class 11: $\{13\}$; Class 12: $\{17\}$; Class 13: $\{19\}$.

....

Answer 2

Note that for your relation to hold, we need the property to be true for EVERY prime. This means that given $x,y$, if you take any prime number, it should either be a factor of both of them, or of none of them.

Having this in mind, it would be wise to instead view a number, view its decomposition as a product of powers of prime numbers. Using the decomposition, you can see that the equivalence classes are exactly the numbers which have the same primes in their decomposition (but with possibly different powers). So an equivalence class can be identified with a finite set of primes, and it will consist of all numbers which can be written as a product of powers of these primes.

Answer 3

Here are all the divisibility facts we need to know:

$\tag {numbers divisible by 2} \{2,4,6,8,10,12,14,16,18,20\}$ $\tag {numbers divisible by 3} \{3,6,9,12,15,18\}$ $\tag {numbers divisible by 5} \{5,10,15,20\}$ $\tag {numbers divisible by 7} \{7,14\}$ $\tag {numbers divisible by 11} \{11\}$ $\tag {numbers divisible by 13} \{13\}$ $\tag {numbers divisible by 17} \{17\}$ $\tag {numbers divisible by 19} \{19\}$

By scanning the above divisibility table and taking intersections we can quickly figure out the classes. For example, intersecting the first two sets we see that the only numbers divisible by $2$ and $3$ are $6$, $12$ and $18$. Moreover, $6$, $12$ and $18$ appear nowhere else.

So these are the classes:

$\; \{1\}$
$\; \{2,4,8,16\}$
$\; \{3,9\}$
$\; \{5\}$
$\; \{7\}$
$\; \{11\}$
$\; \{13\}$
$\; \{17\}$
$\; \{19\}$
$\; \{14\}$
$\; \{10,20\}$
$\; \{15\}$
$\; \{6,12,18\}$

As a check all elements must be accounted for exactly once. You will eventually be able to scan/check and verify your answer.