number theoretical questions for division of numbers $1$ to $100$

Suppose we have a directed bipartite graph with $$100$$ vertices on both sides, and both consist of numbers $$1$$ to $$100$$. There is an arc $$(i,b)$$ from the left to the right side if and only if $$i$$ divides $$b$$. There are three questions:

1. Which pairs of vertices have at least $$5$$ neighbors in common (i.e. which pairs of vertices divide at least $$5$$ same numbers)?

2. How many arcs are there in total?

3. Take all possible combinations of vertices (single vertices, pairs, triples, etc) with at least $$5$$ neighbors in common. Find the maximal such sets.

1. I guess here we have to count what each pair of numbers divides, so we have the number $$\lfloor \frac{100}{\mathrm{lcm}(i,j)}\rfloor$$. We first count how many numbers divide at least $$5$$ numbers on their own and that is $$\lfloor \frac{100}{i}\rfloor \geq 5$$. Here we see that $$i\leq 20$$. So we would have to look at $${20\choose 2}$$ pairs. Another condition is that $$\mathrm{lcm}(i,j) \leq 20$$ but I do not know how to continue here to write the exact pairs? I guess each number and its multiples until $$20$$ is included, but there are some pairs such as $$(2,3)$$ which also appear.

2. I figured out the second question by counting how many divisors a number $$b$$ on the right has. From $$1$$ to $$100$$ we sum up $$\lfloor \frac{100}{i}\rfloor$$ and I get the total $$482$$.

3. I wrote a code to calculate these maximal sets, and I know the answer is $$(1, 17), (1, 2, 3, 6, 9, 18), (1, 19), (1, 2, 4, 5, 10, 20), (1, 3, 5, 15), (1, 2, 4, 8, 16), (1, 13), (1, 2, 7, 14), (1, 2, 3, 4, 6, 12), (1, 11).$$ I am not sure how to prove it mathematically. It should be a generalization of the first question. I guess we would use the lcm again and for example the fact that some numbers are prime so they could not be contained in larger sets.

Any help is appreciated.

• You have looked at only one side of part $1$. The vertices on the side could share five neighbours too, if they had five common factors. For example, take $72$ and $54$ , which share all the common factors $1,2,3,6,9,18$. This will come down to their $\gcd$, though. Dec 5, 2020 at 10:15
• In this case we were looking at a directed graph with arcs from left to right, although I agree it makes sense that we could look at the common factors. I am not sure if this would reduce cases though, because I do not see what conditions we could impose on the gcd? Dec 5, 2020 at 10:53
• Ah, sorry, I missed that it is directed. I will try to answer the question. Dec 5, 2020 at 11:34

1. Which pairs of vertices have at least 5 neighbors in common (i.e. which pairs of vertices divide at least 5 same numbers)?

The question in the parentheses only counts the pairs on the left side with five common neighbours. In other words, it only deals with out-neighbours. If you would like to find pairs with five common in-neighbours as well, you have to also find pairs that have at least five common divisors.

The former is, as you say, equivalent to finding pairs $$(i,j), 1 \leq i < j \leq 100$$ with $$\text{lcm}(i,j) \leq 20$$. There seem to be $$56$$ such pairs and they are easy to find by programming (and indeed easy, but tedious, to write out by hand).

The latter is equivalent to finding pairs $$(i,j), 1 \leq i < j \leq 100$$ such that $$\text{gcd}(i,j)$$ has at least five divisors. My computer says that there are $$71$$ such pairs.

This comes out to a grand total of $$127$$ pairs. But unless this was a programming assignment, I think the question was only aimed at giving a characterization of pairs with at least $$5$$ common neighbours (which we have done in terms of their $$\text{lcm}$$ and $$\text{gcd}$$).

1. How many arcs are there in total?

Your approach is sound and my computer says $$482$$ as well.

1. Take all possible combinations of vertices (single vertices, pairs, triples, etc) with at least 5 neighbors in common. Find the maximal such sets.

As in the first part, a set of numbers is valid if and only if the least common multiple $$m$$ of all the elements is at most $$20$$. Also notice that if $$m \leq 20$$, then we can add it to the set to get another valid set, and we can also add every divisor of $$m$$, since this doesn't increase the lowest common multiple of the members. This means that the maximal sets must be of the form $$\{i : i \text{ divides } m\}$$.

Finally, if this number $$m$$ was at most $$10$$, then we could also add $$2m$$ to the set to get a larger one. So in the end the maximal combinations are the sets of divisors of $$m$$ for $$11 \leq m \leq 20$$, and these are exactly the ones you gave in your answer.

• Thank you for the answer. Your approach to count in-neighbors makes sense, but it wasn't required in this case as you mentioned. I do understand the part about the divisors inuitively but I am not sure how to write it mathematically. Maybe another sentence of explanation would help? Dec 5, 2020 at 16:47
• I edited my answer to be a bit more explicit - do tell me if you have further questions about it. Dec 5, 2020 at 17:12
• Thank you for the great answer! Dec 5, 2020 at 18:04
• Good answer, was writing one but you've covered everything. +1 Dec 7, 2020 at 11:48