Sums of Two Squares Visualized

Abstract

In 1972, John Brillhart described an algorithm for expressing a prime $p\equiv 1\hspace{1em}(\mathrm{\text{mod}}4)$ as the sum of two squares. Brillhart’s algorithm, which is based on the Euclidean algorithm, is simplicity itself. However, Brillhart’s proof of his algorithm’s correctness uses several previous results, and subsequent simplifications of his argument still retain something of an air of mystery. We provide a geometric interpretation of Brillhart’s algorithm, which not only proves that it works, but also sheds light on a surprising palindromic property proved by Perron, and used by Brillhart in his proof.

MSC:

• 11A05
• 11H99

Acknowledgment

Both authors are extremely grateful to the second author’s teacher and mentor, Peter Shiu, whose paper [7] was the inspiration for this project, and whose encouragement and feedback has been indispensable.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Ishan Banerjee

ISHAN BANERJEE hails from West Bengal, India. He completed his high school studies from St. Augustine’s Day School, Barrackpore, West Bengal. He is currently pursuing his Bachelors Degree in Mathematics and Computer Science at Chennai Mathematical Institute, Chennai, India.

Amites Sarkar

AMITES SARKAR has roots in West Bengal, India and Karachi, Pakistan, but was born in London, England. He was educated, many years ago, at Dulwich College Preparatory School, Winchester College, and Cambridge University. This article is quietly dedicated to the memory of his parents, Amares and Guli Sarkar.