Library / /552 of 740

, 2016

Number theory Difficulty 5.2 AIME, harder Prove it United States

Problem:
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

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$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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