Problem 1745

To prove that $|\det A| = k^2$ for some integer $k$, we will analyze the structure of the matrix $A$ and use properties of determinants and permutations.

1. Matrix Definition and Structure:
- The matrix $A = (a_{ij})_{1 \leq i,j \leq n}$ is defined such that $a_{ij} = 1$ if $i + j$ is prime, and $a_{ij} = 0$ otherwise.
- This means that $A$ is a symmetric matrix because $a_{ij} = a_{ji}$.

2. Permutation and Sign Function:
- Consider the set $B$ of bijective maps from $\{1, 3, \ldots, 2n-1\}$ to $\{2, 4, \ldots, 2n\}$.
- For $f, g \in B$, define the permutation $\pi(f, g) \in S_{2n}$ such that:
$$\pi(f, g)(i) = \begin{cases} f(i) & \text{if } i \text{ is odd}, \\ g^{-1}(i) & \text{if } i \text{ is even}. \end{cases}$$
- Define $\delta(f) = \text{sgn}(\pi(f, h))$ for a fixed $h \in B$.

3. Properties of Permutations:
- It can be checked that $\pi(f, g) \pi(g, f) = \text{Id}$ and $\pi(f, g) = \pi(f, h) \pi(h, h) \pi(h, g)$.
- Therefore, $\text{sgn}(\pi(f, g)) = \delta(f) \delta(g) \delta(h)$.
- It is also straightforward to check that $\delta(h) = (-1)^n$.

4. **Determinant Calculation for Even $n$**:
- Let $X = (x_{i,j})$ be a $2n \times 2n$ matrix with $x_{i,j} = 0$ whenever $i + j$ is even and at least 4.
- For $\sigma \in S_{2n}$, the product $x_{1, \sigma(1)} \ldots x_{2n, \sigma(2n)}$ vanishes unless $\{\sigma(1), \sigma(3), \ldots, \sigma(2n-1)\} = \{2, 4, \ldots, 2n\}$, i.e., $\sigma = \pi(f, g)$ for some $f, g \in B$.
- Hence,
$$\det X = \sum_{\sigma \in S_{2n}} (\text{sgn}(\sigma)) x_{1, \sigma(1)} \ldots x_{2n, \sigma(2n)} = \sum_{f, g \in B} \text{sgn}(\pi(f, g)) x_{1, f(1)} x_{3, f(3)} \ldots x_{2n-1, f(2n-1)} x_{g(1), 1} x_{g(3), 3} \ldots x_{g(2n-1), 2n-1}.$$
- This simplifies to:
$$\det X = (-1)^n \left( \sum_{f \in B} \delta(f) x_{1, f(1)} x_{3, f(3)} \ldots x_{2n-1, f(2n-1)} \right) \left( \sum_{f \in B} \delta(f) x_{f(1), 1} x_{f(3), 3} \ldots x_{f(2n-1), 2n-1} \right).$$

5. **Determinant Calculation for Odd $n$**:
- Let $X = (x_{i,j})$ be a $2n+1 \times 2n+1$ matrix with $x_{i,j} = 0$ whenever $i + j$ is even and at least 4.
- The product $x_{1, \sigma(1)} \ldots x_{2n+1, \sigma(2n+1)}$ vanishes unless $\sigma(1) = 1$ and $\{\sigma(2), \sigma(4), \ldots, \sigma(2n)\} = \{3, 5, \ldots, 2n+1\}$.
- The determinant of $X$ is $x_{1,1}$ times the $(1,1)$-th minor, which is of the form considered in the preceding paragraph.
- For a closed expression, set $y_{i,j} = x_{i-1, j-1}$ to obtain:
$$\det X = (-1)^n x_{1,1} \left( \sum_{f \in B} \delta(f) y_{1, f(1)} y_{3, f(3)} \ldots y_{2n-1, f(2n-1)} \right) \left( \sum_{f \in B} \delta(f) y_{f(1), 1} y_{f(3), 3} \ldots y_{f(2n-1), 2n-1} \right).$$

6. Conclusion:
- If $X$ is symmetric and $x_{1,1} = 1$, we obtain $\det X = \pm 1 \times \text{a square}$.
- Therefore, $|\det A| = k^2$ for some integer $k$.

$\blacksquare$

The final answer is $\boxed{ |\det A| = k^2 }$ for some integer $k$.