On The Two-Square Theorem and The Modular Group

Abstract

Given a positive integer \(n\) such that \(-1\) is a quadratic residue mod \(n\), we give an algorithm that computes the integers \(u\) and \(v\) which satisfy the equation \(n = u^2 + v^2\). To do this, we use the group structure of the Modular group \(\Gamma= \text{PSL}(2,\mathbb{Z})\).