The Hermite-Serret Algorithm and 122 + 332
Alf van der Poorten · Birkhäuser Basel eBooks · 2001
Musing on the cute observation that 12 2 + 33 2 = 1233 led me to remind myself of well-known techniques for writing a given integer n as a sum of two squares, given (or having already found) a square root z , say, of -1 modulo n. In brief, one applies the Euclidean algorithm to n and z , stopping at the first pair x and y of remainders that are smaller than Then, lo! it happens that n = x 2 + y 2 . Naturally, square roots of -1 properly different from z lead to different representations of n as sum of two squares. Obviously, so simple an algorithm must have an elegant and near trivial explanation, yet the literature contains some rather turgid proofs. I briefly point out that, in general, a representation of n by a reduced definite binary quadratic form can readily be found by symmetric decomposition of a symmetric matrix, a process well known as reduction ; and that this does give insight into why certain remainders in the Euclidean algorithm applied to n and some square root modulo n yield the representation. My story is for our mild amusement, and provides a nice and easily comprehended story to tell our students These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.