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:

*

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


*How many arcs are there in total?


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

*

*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.


*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$.


*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.
 A: 

*

*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}$).



*How many arcs are there in total?


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



*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.
