number theory - Prove that it is sufficient to check $lceil log(k) rceil$ pairs to tell if a set of integers is pairwise coprime

I am reading chapter 31 of Introduction to Algorithms (CRLS) and I encountered some difficulties while solving 31.2-9. I managed to prove the first part of a problem, but I can't prove the generalized version.

This is the problem statement:

Prove that $n_1, n_2, n_3,$ and $n_4$ are pairwise relatively prime if and only if $gcd(n_1 n_2, n_3 n_4) = gcd(n_1 n_3, n_2 n_4) = 1$. More generally, show that $n_1, n_2, ..., n_k$ are pairwise relatively prime if and only
if a set of $\lceil \log(k) \rceil$ pairs of numbers derived from the $n_i$ are relatively prime.

Proof of the first part: $gcd(n_1 n_2, n_3 n_4) = 1$ means that $n_1 n_2$ and $n_3 n_4$ doesn't have any common factors, so $gcd(n_1, n_3) = gcd(n_1, n_4) = gcd(n_2, n_3) = gcd(n_2, n_4) = 1$. The same is for the second equation so, $gcd(n_1, n_2) = gcd(n_1, n_4) = gcd(n_3, n_2) = gcd(n_3, n_4) = 1%%$

Answer

Hint: Assume that we have $k$ positive integers $a_0,\ldots,a_{k-1}$ and $k\leq 2^m$. For any $j$ such that $1\leq j \leq m$, we define $f_j(m)$ as the value of the $(j-1)$-th bit from the right in the binary representation of $m$, then take:

$$N_1^{(j)} = \prod_{k : f_j(k)=1}a_k,\qquad N_0^{(j)} = \prod_{k: f_j(k)=0}a_k$$
and compute $G_j=\gcd\left(N_0^{(j)},N_1^{(j)}\right)$. If $G_j=1$ for any $j$ in the range $[1,m]$, the original integers are pairwise coprime, otherwise they are not. And obviously $m\approx \log_2(k)$.

This construction is kindly stolen from Hadamard matrices.