HMMT 二月 2000 · POW 赛 · 第 20 题

HMMT February 2000 — POW Round — Problem 20

Find the 2000th p ositiv e in teger that is not the di eren e b et w een an y t w o in teger squares.

解析

First, w e will sho w that a p ositiv e in teger x is not a di eren e of squares if and only if x 2 (mo d 4). 2 2 First, supp ose x = a b for some in tegers a; b , so x = ( a b )( a + b ). No w, if a b = 1, then a + b = 2 n + 1 for some in teger n , so x = ( a b )( a + b ) = 2 n + 1, and x is o dd. Con v ersely , if x is o dd, then x = 2 n + 1 for some in teger n , so x = 1(2 n + 1) = 2 2 ( n + 1 n )( n + 1 + n ) = ( n + 1 ) n . No w, if a b = 2, then a + b = 2 n + 2 for some in teger n , so x = ( a b )( a + b ) = 2(2 n + 2) = 4 n + 4 2 2 Con v ersely , if x 0 (mo d 4), then x = 4 n + 4 for some in teger n , so x = ( n + 2) n . So, for all other ases, a b 2. If a b is ev en, then w e kno w a b = 2 n for some in teger n , and a + b = 2 n + 2 m for some in teger m , so x = ( a b )( a + b ) = 2 n (2 n + 2 m ) = 2 4 nm + 4 n , so x 0 (mo d 4), and w e ha v e already o v ered this ase. If a b is o dd, then w e kno w a b = 2 n + 1 for some in teger n , and a + b = 2 n + 2 m + 1, 2 where m is some in teger, so x = ( a b )( a + b ) = (2 n + 1) (2 n + 2 m + 1) = 4( n + nm + n ) + 2 n + 2 m + 1 1 (mo d 4), whi h is a ase that w e ha v e already o v ered. Therefore, x is not a di eren e of t w o squares if and only if x 2 (mo d 4). So, the 2000th n um b er is 4 1999 + 2 = 7998 .