UkraineMO

Answer: $2016 * 121 = 16$, $2016 * 144 = 13$.

Suppose there are two positive integers $a, b$. Let us rewrite them as follows: $a = bq + r$, where $q$ is a non-negative integer, $r$ is a positive integer and $r \le b$. We prove that under such conditions $a*b = q$.

If in the second condition $\forall a \in \mathbb{N}$ we put $a = b$, then we will obtain $a*a = 0$. If we suppose that $a*b = 0$, and in condition 1) put $a_1 + b_1 = a$, $b_1 = b$, then we obtain
$$(a_1 + b_1)*b_1 = a_1*b_1 + 1 \text{ or } a*b = (a-b)*b + 1.$$
But this contradicts the definition of the operation, because in such case for positive integers $a-b$ and $b$ the operation is not defined, because then $(a-b)*b = -1$, which is impossible. Thus, for $a > b$ $b*a = 0$.

Now suppose $a > b$ and $a = bq + r$, $q, r \in \mathbb{N}$, $r \le b$. Then
$$\begin{align*} & r*b = 0 \Rightarrow (r + b)*b = r*b + 1 = 1 \Rightarrow ((r + b) + b)*b = (r + b)*b + 1 = 2 \Rightarrow \dots \\ & \qquad (r + qb)*b = ((r + (q-1)b) + b)*b + 1 = q-1 + 1 = q, \end{align*}$$

Finally we obtain
$$\begin{aligned} 2016 &= 121 \cdot 16 + 80 &\Rightarrow 2016 * 121 &= 16, \\ 2016 &= 144 \cdot 14 = 144 \cdot 13 + 144 &\Rightarrow 2016 * 144 &= 13. \end{aligned}$$