Problem
NT-B2-M07-P016 A Strong Divisibility Bound
#16
★★★★☆ Level 4 of 5
Find all positive integer pairs \((x,y)\) such that \(x^2+y^2\mid xy+1\).
Compare the sizes of \(x^2+y^2\) and \(xy+1\). Check small values separately.
If \(x,y\ge 2\), then \(x^2+y^2-xy-1=(x-y)^2+xy-1\ge 3>0\), so \(x^2+y^2>xy+1\). The divisibility is then impossible because the positive divisor is larger than the positive number. If \(x=1\), the condition becomes \(1+y^2\mid y+1\), which is possible only for \(y=1\). The case \(y=1\) is symmetric. The pair \((1,1)\) indeed works: \(2\mid 2\). The answer is \((1,1)\).
A good example where a size estimate completely replaces a search.