Inspired by Chung Kevin

Observation 1 : The answer cannot be more than 18. After all, any arrangement of the even numbers $2, 4, 6, 8, 10, 12, 14, 16, 18$ would be valid.

In what follows, we are therefore only interested in values less than 18.

Observation 2 : The number 1 cannot be part of the grid. The answer must therefore be at least 10.

Observation 3 : If a prime number $p$ is part of the solution, the answer is at least equal to $3p$ . Explanation: The number $p$ has at least two neighbors, which are at least $2p$ and $3p$ .

Thus we know that 7 is not part of the solution, since it is prime and $3\cdot 7 = 21 > 18$ . For the same reason, 11 and 13 cannot be part of the solution.

Also, if we keep the number 5 in the grid, we need 10 and 15.

Observation 4 : If the grid contains 3 and 9, it must also contain 6, 12, and 15. Explanation: All neighbors of 3 and 9 must have 3 as a prime factor. By placing them next to each other in a corner, we attain the minimal number of such neighbors: three.

Based on these observations, we will start with the set $2,4,6,8,10,12,14$ . We also include either 3 or 9, which must be placed in a corner next to 6 and 12. Now we must decide on one additional number in the set.

• We cannot include 1 (observation 2), 7, 11, or 13 (observation 3).

• If we include both 3 and 9, we also need 15 (observation 4).

• But if instead we include 5, we also need 15 (observation 3).

• The next possible value that might be included is 15.

No matter how we choose, we end up with $\boxed{15}$ or greater in the grid. A concrete example where this is accomplished: $\begin{array}{|c|c|c|} \hline 3 & 9 & 15 \\ \hline 6 & 12 & 10 \\ \hline 2 & 4 & 8 \\ \hline \end{array}$

To start with, we cannot use $1$ since gcd $(1,n) = 1$ for any positive integer $n$ . So with this restriction, since we need to use $9$ distinct digits, the best we could do is to use $2,3,4,5,6,7,8,9,10$ .

However, the 4 corner boxes, each being connected to 2 other boxes, must each have a number that has a gcd other than $1$ , (i.e., a non-unit gcd), with 2 other numbers in the set of integers we use. If we were to include the prime $7$ , then, we would be forced to include $14$ and $21$ . Now we could include all 9 positive multiples of $2$ in the grid in any arrangement, with the result that each adjacent pair has a gcd of at least $2$ , and with $18$ as the maximum number. So we know we can do better than $21$ as the maximum, and so we should drop $7$ from our set. The next smallest number we can add is $11$ , which being an odd prime presents the same problem as did $7$ . So skipping $11$ brings us to the addition of $12$ to our set.

Next, if we were to keep the prime $5$ , since $10$ at the moment is the only number in our set that has a non-unit gcd with $5$ we would be forced to add $15$ . If we were to drop $5$ then the next smallest number after $12$ we could add is $14$ , since $13$ would have the same problem as did $7$ and $11$ .

Now if $14$ were the smallest maximum then we would be working with $2, 3, 4, 6, 8, 9, 10, 12, 14$ . The number we place in the center box will be adjacent to 4 other numbers, so must share a non-unit gcd with at least 4 other numbers in the set. All the even numbers are thus candidates for the center box, but $3$ and $9$ are not, since they each share non-unit gcd's with only three other numbers, (including each other). Now if we place either of $3$ or $9$ in one of the non-corner side boxes, then we would need to place either $6$ or $12$ in the center box. So say $3$ is placed in the upper middle box. As only $6,9$ and $12$ share non-unit gcd's with $3$ and one of $6$ or $12$ is in the center box, (say we choose $6$ ), we would need to place $9$ in one of the upper corner boxes and $12$ in the other. But now this leaves $9$ hung out to dry, since the only numbers left to place in the adjacent box below it are even and coprime with $9$ . The only other option is to place $3$ and $9$ in corner boxes, but this would then necessitate finding 3 numbers for the adjacent middle side boxes which have non-unit gcd's with $3$ and $9$ , (one of these being mutual). $6$ and $12$ are all we have to work with here, so this option is out too. Thus we cannot make the grid work with a smallest maximum of $14$ .

We now move on to see if we can make the grid work with $15$ as the maximum. If we bring in $5$ then we would drop any two of $2,3,4,6,8,9,12,14$ , or if we leave $5$ out we would drop any one of the remaining numbers. Suppose we keep $5$ . Then it would need to be placed in a corner box, as only $10$ and $15$ share with it a non-unit gcd. We would then have to place $10$ and $15$ in the adjacent side boxes, and since the center box must be even and would now have to share a non-unit gcd with $15$ we would have to place one of $6$ or $12$ in the center box; say we place $6$ there. Then either $12$ or $3$ must go in the remaining corner box adjacent to $15$ . If we go with $3$ then $12$ would then need to go in the adjacent side box. The rest of the boxes can then be filled with three of the available even numbers. For example, the configuration with the least sum is

$\Large 2 \space \space 10 \space \space 5$

$\Large 4 \space \space \space 6 \space \space 15$

$\Large 8 \space \space 12 \space \space 3$

There are several other valid configurations we can construct, but the bottom line is that $\boxed{15}$ is the smallest possible value of the largest integer used.

We'll show a maximum of 14 or less is impossible.

With a maximum of at most 14, there are at most 7 even integers, so we include at least 2 odd integers. However, 1 clearly cannot be included (GCD of it and any other integer is 1). If we include a prime $p \ge 5$ , it must be adjacent to at least two other numbers $a, b$ ; since $\gcd(p, a), \gcd(p, b) > 1$ , we must have $\gcd(p, a), \gcd(p, b) = p$ . Thus $a, b$ are both divisible by $p$ . Since they are different from each other and from $p$ , we need $\max \{a, b\} \ge 3p$ . But since $p \ge 5$ , we have $3p \ge 15 > 14$ , so $\max \{a, b\} > 14$ and thus it exceeds our maximum. So we may not include any prime $p \ge 5$ .

That leaves us with only 3 and 9 as our odd numbers. Thus in fact, a maximum of 14 or less would include all seven even integers, along with 3 and 9. Now consider the places where the 3 and 9 are in; no matter where they are, there are at least three other boxes adjacent to at least one of 3 and 9. (You can try all possible cases, if you want.) Each of these boxes must include a multiple of 3 (because their GCD with either 3 and 9 must be a multiple of 3), and they are also even, so they must be multiples of 6. But there are only two multiples of 6 below 14, namely 6 and 12, so we cannot fill the third box.

Thus a maximum of 14 or less is impossible, requiring a maximum of 15. This also shows how we can try constructing one example. There are two parts in the above proof where relaxing the maximum to 15 doesn't work:

In the discussion about primes, if we relax the maximum to 15, then $p = 5$ is now possible. It will be in a corner, adjacent to a 10 and a 15. The 15 is odd, but it's divisible by 3, so we can cover the two adjacent boxes to it with 6 and 12:

1
2
3

 5 15  6
10 12  2
 4  8 14

Or otherwise, in the part about 3 and 9, the result breaks down as well. One important point was that we had even numbers besides 3 and 9; here, this is not true, because we only got rid of 5 odd numbers, leaving 3 left (3, 9, 15). Thus our claim that all the remaining numbers after placing 3 and 9 are even is not true. And in fact, this lets us to make an example. We still may only have three boxes adjacent to one of 3 and 9 (because we only have three multiples of 3 left, namely 6, 12, 15), but now we can place the 15 somewhere. The 15 may have more adjacent boxes, but it may share a GCD of 5 instead of 3 with them (in particular, the 15 would be adjacent to 10). One such construction, after placing 3 and 9 at top row and 15 to fill it:

1
2
3

 3  9 15
 6 12 10
 2  4  8

Knowing that the max cannot be larger than 18, and looking at all numbers from 2-18. Apart from 18, to minimize the max, we must incorporate factors that occur often in 2-18. Incorporating 3 in a corner doesn't work out, and incorporating 3 in the middle leaves 15 as the max.