>> 798
(A) The problems suggests that $p = 2$ is the problem. If we consider $\gcd(a_{2i} + 2j, a_{2j} + 2i) = 1$, we see that at least one of $a_{2i}$, $a_{2j}$ has to be odd — say, $a_{2i}$. Then $\gcd(a_{2i} + 2j + 1, a_{2j + 1} + 2i) = 1$ implies that $a_i$ is odd for odd $i$. But then $\gcd(a_{2i + 1} + 2j + 1, a_{2j + 1} + 2j + 1) = 1$ is a contradiction since both sides are divisible by $2$.
(B) Just let $a_i = pi - i + 1 > 0$, which gives $\gcd(pi - i + 1 + j, pj - j + 1 + i) = \gcd(p(i + j) + 2, pj - j + 1 + i)$ and $p \nmid p(i + j) + 2$.