Subsets $A_i$ of $\mathbb{N}$ such that $|A_i\cap A_j| = (i,j)$ Here is a problem that I can not solve. Any suggestion or hint would be helpful. If there is a history of this problem in the literature please let me know. 
Does there exists subsets $A_1, A_2, \cdots$ of $\mathbb{N}$ such that for any two (not necessary different) natural numbers $i,j$, $|A_i\cap A_j| = (i,j)$ ? (Where $(i,j)$ is the greatest common divisor of $i$ and $j$.) As joriki also pointed out, this implies that $|A_k|=k$ for all $k$.
 A: Hint: What if $A_k$ were the set of complex numbers $z$ such that $z^k=1$?
A: Jyrki just posted a far more elegant proof than the one I was about to write up, but I'll post it anyway, in case you're interested in a proof with a more combinatorial flavour.
Yes, such subsets exist. We can prove this by an inductive construction. For $k\in\mathbb N$, let $b_k$ be the number of elements that $A_k$ is constrained to contain due to its overlaps with sets $A_j$ with $j\lt k$, so that we're left free to choose $c_k=k-b_k$ additional elements that don't appear in any of the $A_j$. We need to prove $c_k\ge0$.
Consider the prime factorization $k=\prod_{i=1}^dp_i^{n_i}$. By inclusion–exclusion on the lattice of divisors of $k$, we have
$$
c_k=\sum_{\epsilon\in\{0,1\}^d}(-1)^{\sum_i\epsilon_i}\frac k{\prod_ip_i^{\epsilon_i}}=k\prod_i\left(1-\frac1{p_i}\right)\;,
$$
which is clearly positive. Note that this is Euler's totient function, which counts the number of positive integers up to $k$ that are coprime with $k$, and that this is precisely the number of solutions to $z^k=1$ in Jyrki's answer that are not solutions to any equation $z^m=1$ with $m\lt k$.
