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 $\mathrm{\Gamma }=\text{PSL}(2,\mathbb{Z})$.