Lemma: For positive integers $m$, $m^2+m+1$ has no divisors $5 \pmod{6}$. Proof: Since the product of two numbers being $5 \pmod{6}$ implies that one of those numbers is $5 \pmod{6}$, any divisor of that form must be divisible by a prime $5 \pmod{6}$. If a prime divides $m^2+m+1$, it also divides $(m^2+m+1)(m-1) = m^3-1$, and therefore $m^3 \equiv 1 \pmod{p}$. This means that either $m \equiv 1 \pmod{p}$ or that $3 | p-1$ (since $3$ would be the order of $m$ modulo $p$). If $3 | p-1$, then $p$ can't be $5 \pmod{6}$. If $p | m-1$ and $p | m^2+m+1$ then $p | m^2+m+1-(m+2)(m-1) \implies p | 3$, so $p=3$. $\square$. a) We will prove that $(n, k)$ being a lovely couple implies that $k(k-1) +1= n$, which will show that the only residues are $1, 3$. (by the lemma, taking $m=k-1$) Examples of lovely couples giving that result are $(7, 3)$, and $(3, 2)$, which can easily be checked. WLOG, we assume that the first row consists of $k$ ones followed by $n-k$ zeroes. The $n-1$ next rows are considered separately. Each of those rows must have one $1$ ("`the first $1$"') in the first $n$ columns and the rest must be in the other columns ("`right zone"'). Let's consider how many of these rows at maximum can have the first one in the same column. The ones in right part must not share the same columns, and since there are $k-1$ of these ones per row and $n-k$ allowed columns in the right zone, the maximum there can be is $\left\lfloor \frac{n-k}{k-1} \right\rfloor$. (See diagram) Since there are $k$ possible columns where the ones may be placed and the total number of rows is $n-1$, in order to be able to fill all the rows we must have: $$ \left\lfloor \frac{n-k}{k-1} \right\rfloor \cdot k \geq n-1 $$ We can transform that condition into a form that will be more useful later: $ \left\lfloor \frac{n-k}{k-1} \right\rfloor \cdot k \leq \frac{n-k}{k-1} \cdot k \implies \frac{n-k}{k-1} \cdot k \geq n-1 \implies nk-k^2 \geq nk-k-n+1 \implies $ $$n-1 \geq k(k-1)$$ Now, we consider another way of bounding $k$ by means of considering the maximum number of rows with the first one in the same column. Note that we can't have all the rows sharing the same column with row $1$; there must be, therefore, at least a row which doesn't have the first $1$ placed in the same column as the rest. Consider a group of $q$ rows which have the first one placed in the same column and one row which has it in a different column. In the $n-k$ right zone there can be no shared ones, so clearly $q$ groups of ones are formed. Now consider the other row. In other to share an $1$ with all of the previous $q$ rows, there has to be exactly one $1$ placed in each of the $q$ groups. There are $k-1$ ones to be placed in the "`right zone"', so $q \leq k-1$: that means that the maximum amount of rows with the first $1$ placed in a certain column is $k-1$. Again, since there are $n-1$ rows to be filled and $k$ colums we have: $$k(k-1) \geq n-1$$ Combining it with the previous inequality, we have the equality we were looking for. $\blacksquare$. b) We will give a construction for lovely couples of the form $(p^2+p+1, p+1)$ where $p$ is a prime number. The first row is set up just like we assumed it was in the previous section, and the next $k-1$ rows have a $1$ in the first column and blocks of $1$ forming "`horizontal periods"', each identified by an integer $t$. Here is an example for the $(13, 4)$ case: For the next rows, $k-1$ "`vertical groups"' of $k-1$ rows are made; each of these group is identified by an integer $l$ and they have the first $1$ in the same column. Each of those rows is identified by an integer $m$. Now, for each of those rows, we place one $1$ in each of the horizontal periods in the "`right zone"': the position of the $1$, out of the $k-1$ possible positions, is given by $$P(l, m, t) \equiv m + lt \pmod{k-1}$$This works because for rows of the same "`vertical group"' there are no two $1$ in the same columns (since $l$ and $t$ are the same, and $m$ is different), and that's the desired result since the first $1$ is the only shared one. For rows of different groups, we have that ones are shared if $m_1+l_1t \equiv m_2+l_2t \pmod{k-1} \implies t \equiv (m_1-m_2)(l_2-l_1)^{-1} \pmod{k-1}$, having an unique solution since $k-1$ is prime, so there is only one $1$ shared, which is what was wanted.