# Listing the equivalence classes of a specific relation on a set

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.

• Note in your example proposed class of $(5,10,15,20)$ that $2$ divides $10$ and $20$, but not the other $2$, plus $3$ divides $15$, but none of the other $3$. – John Omielan May 15 '20 at 6:16
• $5\not R 10$ because $2|10$ but $2\not\mid 5$. Think what this is really saying. – fleablood May 15 '20 at 6:18
• I assumed that x, y didn't need to share the exact same prime factors, simply share 1 or more. Was I wrong to assume this? Meaning, x,y are only related if they share the exact same prime factors? I.e. 3 and 9 – Kermitty May 15 '20 at 6:19
• @Kermitty Consider what the relation $xRy$ is stating. It says for every prime which divides one of the values, it must also divide the other value. What does that say about whether or not they must share the exact same prime factors? – John Omielan May 15 '20 at 6:22
• I see my error now, thanks for pointing out my misunderstanding. The question still remains though about whether or not there is a process of determining the equivalence classes without going for a 'bruteforce' approach – Kermitty May 15 '20 at 6:25

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\}$$.

....

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.

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.