Track / Stage 5 / 127 of 400 #1207 of 2444

Problem 1207

AIME late

Number theory Difficulty 5.2 Prove it HMMT November · United States · 2016

A positive integer is written on each corner of a square such that numbers on opposite vertices are relatively prime while numbers on adjacent vertices are not relatively prime. What is the smallest possible value of the sum of these 4 numbers?
Proposed by: Eshaan Nichani

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:
Answer: 60
Two opposite vertices are relatively prime, but they both share a factor with their common neighbor. So that common neighbor must have two prime factors. So each of the 4 numbers has two prime factors, which are not shared with the opposite vertex. Moreover, it suffices to choose the vertices to be the numbers $ab$ , $bc$ , $cd$ , $da$ for some prime numbers $a, b, c, d$ . It's clear that we should choose them to be the smallest primes $2, 3, 5, 7$ in some order. The order that minimizes the sum of all of the numbers gives $14, 10, 15, 21$ for a sum of $60$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.