\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem*{theoremrestate}{Theorem} \newtheorem{question}{Question} \newtheorem{questionrestate}{Question} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Special Numbers in the Ring $\mathbb{Z}_n$} \vskip 1cm Samuel S. Gross \\ Noblis, Inc.\\ Falls Church, VA 22042 \\ USA \\ \href{Samuel.Gross@noblis-nsp.com}{\tt samuel.gross@noblis-nsp.com}\\ \ \\ Joshua Harrington\\ Department of Mathematics\\ Cedar Crest College\\ Allentown, PA 18104 \\ USA \\ \href{mailto:joshua.harrington@cedarcrest.edu}{\tt Joshua.Harrington@cedarcrest.edu}\\ \end{center} \vskip .2in \begin{abstract} In a recent article, Nowicki introduced the concept of a special number. Specifically, an integer $d$ is called \emph{special} if for every integer $m$ there exist solutions in non-zero integers $a,b,c$ to the equation $a^2+b^2-dc^2=m$. In this article we investigate pairs of integers $(n,d),$ with $n\geq 2$, such that for every integer $m$ there exist units $a,b,$ and $c$ in $\mathbb{Z}_n$ satisfying $m\equiv a^2+b^2-dc^2\pmod{n}$. By refining a recent result of Harrington, Jones, and Lamarche on representing integers as the sum of two non-zero squares in $\mathbb{Z}_n$, we establish a complete characterization of all such pairs. \end{abstract} \section{Introduction} The following definition was recently stated by Nowicki \cite{Nowicki}. \begin{definition} We call a positive integer $d$ \emph{special} if for every integer $m$ there exist non-zero integers $a,b,$ and $c$ so that $a^2+b^2-dc^2=m$. \end{definition} The necessary conditions of the following theorem were proven by Nowicki, while Lam \cite{Lam} later provided the sufficient conditions. \begin{theorem}\label{nowickilam} An integer $d$ is special if and only if $d$ is of the form $q$ or $2q$ where either $q=1$ or $q$ is a product of primes all congruent to $1$ modulo $4$. \end{theorem} With this complete representation of special numbers, the following theorem follows from Dirichlet's theorem on primes in arithmetic progression (see Theorem~\ref{Dirichlet} below) and the Chinese remainder theorem. For completeness, we provide a proof of this theorem in Section~\ref{section4}. \begin{theorem}\label{iftrue} For any odd integer $n\geq 3$, any $d$ with $\gcd(d,n)=1$, and any integer $m$, there exist integers $a,b,$ and $c$ such that $a^2+b^2-dc^2\equiv m\pmod{n}$. \end{theorem} In light of Theorem~\ref{iftrue}, we give the following definition, which imposes a unit restriction on $a,b,$ and $c$. \begin{definition} We say that $d$ is \emph{unit-special} in $\mathbb{Z}_n$ if for an integer $m$, there exist units $a,b,$ and $c$ in $\mathbb{Z}_n$ with $a^2+b^2-dc^2\equiv m\pmod{n}$. \end{definition} We note that the requirement that $a,b,$ and $c$ be units in $\mathbb{Z}_n$ ensures that $a^2$, $b^2$, and $c^2$ are non-zero in $\mathbb{Z}_n$. Although one could loosen this restriction to just require $a^2$, $b^2$, and $c^2$ to be non-zero, this is not the setting that we investigate in this article. Among the results in this article, we provide the following complete characterization of unit-special numbers in $\mathbb{Z}_n$. \begin{theorem}\label{main} Let $n$ be a positive integer. An integer $d$ is unit-special in $\mathbb{Z}_n$ if and only if the following three conditions hold: \begin{itemize} \item $n$ is not divisible by 2 or 3. \item If $p\equiv 3\pmod{4}$ is prime and $p$ divides $n$, then $\gcd(d,p)=1$. \item If $5$ divides $n$, then $d\equiv \pm 2\pmod{5}$. \end{itemize} \end{theorem} To establish Theorem~\ref{main} we first refine a recent result of Harrington, Jones, and Lamarche \cite{hjl} on representing integers as the sum of two non-zero squares in the ring $\mathbb{Z}_n$, stated below. \begin{theorem}\label{hjl} Let $n\ge 2$ be an integer. The equation $$ x^2 +y^2 \equiv z \pmod{n} $$ has a non-trivial solution ($x^2,y^2\not\equiv 0\pmod{n}$) for all $z$ in $\mathbb{Z}_n$ if and only if all of the following are true. \begin{enumerate} \item $q^2$ does not divide $n$ for any prime $q\equiv 3 \pmod{4}$. \item $4$ does not divide $n$. \item $n$ is divisible by some prime $p\equiv 1\pmod{4}$. \item If $n$ is odd and $n = 5^km$ with $\gcd(5,m)=1$ and $k<3$, then $m$ is divisible by some prime $p\equiv 1 \pmod{4}$. \end{enumerate} \end{theorem} At the end of their article, Harrington, Jones, and Lamarche ask the following question. \begin{question}\label{qhjl} Theorem~\ref{hjl} considers the situation when the entire ring $\mathbb{Z}_n$ can be obtained as the sum of two non-zero squares. When this cannot be attained, how badly does it fail?\end{question} In this article, we address Question~\ref{qhjl} in a slightly refined setting. In particular, we prove the following theorem. \begin{theorem}\label{main2} Let $n\geq 2$ be an integer. For a fixed integer $z$, there exist units $a$ and $b$ in $\mathbb{Z}_n$ such that $a^2+b^2\equiv z\pmod{n}$ if and only if all of the following hold: \begin{itemize} \item If $p\equiv 3\pmod{4}$ is a prime dividing $n$, then $\gcd(z,p)=1$. \item If $5$ divides $n$, then $z\not\equiv \pm 1\pmod{5}$. \item If $3$ divides $n$, then $z\equiv 2\pmod{3}$. \item If $2$ divides $n$ and $4$ does not, then $z\equiv 0\pmod{2}$. \item If $4$ divides $n$ and $8$ does not, then $z\equiv 2\pmod{4}$. \item If $8$ divides $n$, then $z\equiv 2\pmod{8}$. \end{itemize} \end{theorem} We again note that the requirement that $a$ and $b$ are units in $\mathbb{Z}_n$ ensures that $a^2$ and $b^2$ are non-zero in $\mathbb{Z}_n$. Since Question~\ref{qhjl} does not have the unit restriction, Theorem~\ref{main2} does not give a complete answer to the question. However, it does provide sufficient conditions in the setting of Question~\ref{qhjl}. Although the majority of this article focuses on the refined setting where $a$ and $b$ are units in $\mathbb{Z}_n$, we do briefly investigate the more general setting of Question~\ref{qhjl} and provide a result in this direction. \section{Preliminaries and notation} We will make use of the following results and definitions from classical number theory (see, for example \cite{hwnt}). \begin{theorem}[Dirichlet]\label{Dirichlet} Let $a,b$ be integers such that $\gcd(a,b)=1$. Then the sequence $\{ak+b\}$, over integers $k$, contains infinitely many primes. \end{theorem} \begin{definition} Let $p$ be an odd prime. The \emph{Legendre symbol} of an integer $a$ modulo $p$ is given by $$ \left(\frac{a}{p}\right) = \begin{cases} 1, & \text{if $a$ is a non-zero square modulo $p$}; \\ -1, & \text{if $a$ is not a square modulo $p$};\\ 0, & \text{if $a\equiv 0 \pmod{p}$.} \end{cases} $$ \end{definition} \begin{theorem}\label{consecutivesquares} Let $p\geq 7$ be a prime. There exist non-zero elements $t,u,v,$ and $w$ in $\mathbb{Z}_p$ such that $$\begin{array}{rclrcl} \left(\frac{u}{p}\right)&=&\left(\frac{u+1}{p}\right)=1,\qquad\qquad\qquad &\left(\frac{v}{p}\right)&=&\left(\frac{v+1}{p}\right)=-1,\\ \\ \left(\frac{w}{p}\right)&=&-\left(\frac{w+1}{p}\right)=1,\qquad\qquad\text{and}\qquad\qquad &\left(\frac{t}{p}\right)&=&-\left(\frac{t+1}{p}\right)=-1. \end{array}$$ \end{theorem} The following result can be found in a book of Suzuki's \cite{suzuki} and is originally due to Euler. \begin{theorem}\label{Euler} A positive integer $z$ can be written as the sum of two squares if and only if all prime factors $q$ of $z$ with $q \equiv 3 \pmod{4}$ occur with even exponent. \end{theorem} The following theorem, which follows immediately from the Chinese remainder theorem, appears in Harrington, Jones, and Lamarche's article. \begin{theorem}\label{hjlcrt} Suppose that $m_1,m_2,\ldots ,m_t$ are all pairwise relatively prime integers $\geq 2$, and set $M=m_1m_2\cdots m_k$. Let $c_1, c_2,\ldots , c_t$ be any integers, and let $x\equiv c \pmod{M}$ be the solution of the system of congruences $x \equiv c_i \pmod{m_i}$ using the Chinese remainder theorem. Then there exists a $y$ such that $y^2 \equiv c \pmod{M}$ if and only if there exist $y_1, y_2,\ldots , y_t$ such that $y_i^2 \equiv c_i \pmod{m_i}$. \end{theorem} \section{Sums of squares in $\mathbb{Z}_n$} We begin by examining when integers are a sum of two unit squares modulo $n$. Later we shall relax this condition and only require both squares to be non-zero modulo $n$. Let us first examine the case when the modulus is a power of $2$. \begin{theorem}\label{two} Let $k$ be a positive integer. For a fixed integer $z$, there exist units $a$ and $b$ in $\mathbb{Z}_{2^k}$ such that $a^2+b^2\equiv z\pmod{2^k}$ if and only if one of the following is true: \begin{itemize} \item $k=1$ and $z\equiv 0\pmod{2}$; \item $k=2$ and $z\equiv 2\pmod{4}$; \item $k\geq 3$ and $z\equiv 2\pmod{8}$. \end{itemize} \end{theorem} \begin{proof} We computationally check that the theorem is true for $k\leq 3$. Suppose $k>3$. If $a^2+b^2\equiv z\pmod{2^k}$, then $a^2+b^2\equiv z\pmod{8}$. Thus, we deduce that $z\equiv 2\pmod{8}$. Conversely, suppose that $z\equiv 2\pmod{8}$. We proceed with a proof by induction on $k$. We have already established the base case $k\le 3$. Suppose that the theorem holds for $k-1$ so that that there are units $a$ and $b$ in $\mathbb{Z}_{2^{k-1}}$ such that $a^2+b^2\equiv z\pmod{2^{k-1}}$. Then for some odd integer $t$ and some integer $r\geq k-1$ we can write $$a^2+b^2=z+t2^{r}.$$ If $r\geq k$, then $a^2+b^2\equiv z\pmod{2^k}$, as desired. So suppose that $r=k-1$. Then \begin{align*} a^2+(b+2^{k-2})^2 &=a^2+b^2+b2^{k-1}+2^{2k-4}\\ &=z+t2^{k-1}+b2^{k-1}+2^{2k-4}\\ &=z+2^{k-1}(t+b)+2^{2k-4}. \end{align*} Since $k\geq 4$, we know that $2^{2k-4}\equiv 0\pmod{2^k}$. Also, since $b$ was chosen to be a unit in $\mathbb{Z}_{2^{k-1}}$, then $b$ must be odd. Thus, $t+b$ is even and we deduce that $2^{k-1}(t+b)\equiv 0\pmod{2^k}$. Hence, $$a^2+(b+2^{k-2})^2\equiv z\pmod{2^{k}}.$$ It follows that $b+2^{k-2}$ is an odd integer and is therefore a unit in $\mathbb{Z}_{2^k}$, as desired. \end{proof} We next treat the case where the modulus is a power of an odd prime. The following is an application of Hensel's Lifting Lemma. We provide the proof here for completeness. \begin{lemma}\label{lifting} For an odd prime $p$ and integer $z$, suppose there are non-zero elements $a$ and $b_1$ in $\mathbb{Z}_p$ such that $a^2+b_1^2\equiv z\pmod{p}$. Then for any positive integer $k$, the integer $a$ is a unit in $\mathbb{Z}_{p^k}$ and there exists a unit $b_k$ in $\mathbb{Z}_{p^k}$ such that $a^2+b_k^2\equiv z\pmod{p^k}$. \end{lemma} \begin{proof} Suppose that $a^2+b_1^2\equiv z\pmod{p}$ for some non-zero elements $a$ and $b_1$ in $\mathbb{Z}_p$. Then for some integer $t_1$, $a^2+b_1^2=z+t_1p$. Let $b_2\equiv b_1-t_1p(2b_1)^{-1}\pmod{p^2}$, and note that $b_2$ is a unit in $\mathbb{Z}_{p^2}$. It follows that \begin{align*} a^2+b_2^2 &\equiv a^2+(b_1-t_1p(2b_1)^{-1})^2 \pmod{p^2}\\ &\equiv a^2+b_1^2-t_1p \pmod{p^2}\\ &\equiv z+t_1p-t_1p \pmod{p^2}\\ &\equiv z \pmod{p^2}. \end{align*} Since $a$ is also a unit modulo $p^2$, this proves the result for $k=2$. The remainder of the theorem now follows by induction on $k$ with $$a^2+b_{k+1}^2\equiv z\pmod{p^{k+1}},$$ where $b_{k+1}\equiv b_k-t_kp^k(2b_k)^{-1}\pmod{p^k}$ with $t_k$ satisfying $a^2+b_k^2=z+t_kp^k$. \end{proof} An appropriate converse for Lemma~\ref{lifting} can be stated, however the information contained in such a statement varies with the modulus. Specifically, we can easily prove the following two theorems after verifying the base case $k=1$ and applying Lemma \ref{lifting}. \begin{theorem}\label{three} Let $k$ be a positive integer. For a fixed integer $z$, there exist units $a$ and $b$ in $\mathbb{Z}_{3^k}$ with $a^2+b^2\equiv z\pmod{3^k}$ if and only if $z\equiv 2\pmod{3}$. \end{theorem} \begin{theorem}\label{five} Let $k$ be a positive integer. For a fixed integer $z$, there exist units $a$ and $b$ in $\mathbb{Z}_{5^k}$ with $a^2+b^2\equiv z\pmod{5^k}$ if and only if $z\not\equiv\pm 1\pmod{5}$. \end{theorem} For powers of primes that are $1$ modulo 4, we have the following theorem which is a bit more general then Lemma \ref{lifting}. \begin{theorem}\label{1mod4} Let $p\geq 13$ be a prime with $p\equiv 1\pmod{4}$ and let $k$ be a positive integer. For every integer $z$, there exist units $a$ and $b$ in $\mathbb{Z}_{p^k}$ such that $a^2+b^2\equiv z\pmod{p^k}$. \end{theorem} \begin{proof} We show that the result holds for $k=1$ and the remainder of the proof will follow from Lemma~\ref{lifting}. So let $k=1$. First suppose that $z\equiv 0\pmod{p}$. Since $p\equiv 1\pmod{4}$, we know that $-1$ is a square modulo $p$. Thus, we can let $$a^2\equiv 1\pmod{p}\qquad\qquad\text{and}\qquad\qquad b^2\equiv p-1\pmod{p}$$ so that $a^2+b^2\equiv z\pmod{p}$, where $a$ and $b$ are units modulo $p$. Now suppose that $z\not\equiv 0\pmod{p}$. Since $p\ge 7$, we can use Theorem~\ref{consecutivesquares} to choose $u$ such that $$\displaystyle\left(\frac{u}{p}\right)=\left(\frac{u-1}{p}\right)=\left(\frac{z}{p}\right).$$ It follows that $$\left(\frac{uz}{p}\right)=\left(\frac{-(u-1)z}{p}\right)=1.$$ Thus, letting $$a^2\equiv uz\pmod{p}\qquad\qquad\text{and}\qquad\qquad b^2\equiv-(u-1)z\pmod{p}$$ proves the result for $k=1$ since $u, u-1,$ and $z$ are all units modulo $p$. \end{proof} In the next corollary, which provides an extension of Theorem~\ref{hjl} to our new unit-setting, we piece together the information in Theorem~\ref{1mod4} using the Chinese remainder theorem as stated in Theorem~\ref{hjlcrt}. \begin{corollary}\label{1mod4cor} Let $n\geq 13$ be an odd integer not divisible by 5 and with all prime divisors congruent to 1 modulo 4. Then for any fixed integer $z$, there exist units $a$ and $b$ in $\mathbb{Z}_n$ with $a^2+b^2\equiv z\pmod{n}$. \end{corollary} We now turn our attention to primes that are 3 modulo 4. \begin{theorem}\label{3mod4} Let $p\geq 7$ be a prime with $p\equiv 3\pmod{4}$ and let $k$ be a positive integer. For a fixed integer $z$, there exist units $a$ and $b$ in $\mathbb{Z}_{p^k}$ with $a^2+b^2\equiv z\pmod{p^k}$ if and only if $z$ is a unit in $\mathbb{Z}_{p^k}$. \end{theorem} \begin{proof} First suppose that the $a$ and $b$ are units modulo $p^k$ with $a^2+b^2\equiv z\pmod{p^k}$. If $z$ is not a unit modulo $p^k$, then $z\equiv xp\pmod{p^k}$ for some integer $x$, whence $z\equiv 0\pmod{p}$. It follows that $a^2\equiv -b^2\pmod{p}$. However, this leads to a contradiction since $$\left(\frac{-b^2}{p}\right)=\left(\frac{-1}{p}\right)\cdot\left(\frac{b^2}{p}\right)=-1.$$ For the converse, we show that the result holds for $k=1$ and the remainder of the proof will follow from Lemma~\ref{lifting}. In this case, choose $u$ from Theorem~\ref{consecutivesquares} such that $$\displaystyle\left(\frac{u}{p}\right)=-\left(\frac{u-1}{p}\right)=\left(\frac{z}{p}\right).$$ It follows that $$\left(\frac{uz}{p}\right)=\left(\frac{-(u-1)z}{p}\right)=1.$$ Thus, letting $$a^2\equiv uz\pmod{p}\qquad\qquad\text{and}\qquad\qquad b^2\equiv-(u-1)z\pmod{p}$$ proves the result for $k=1$ since $u, u-1,$ and $z$ are all units modulo $p$. \end{proof} Piecing together Theorems~\ref{two},\ref{three},\ref{five},\ref{1mod4}, and \ref{3mod4} using the Chinese remainder theorem as stated in Theorem~\ref{hjlcrt} provides a proof for Theorem~\ref{main2}. We note once more that Theorem~\ref{main2} provides some insight in to Question~\ref{qhjl}. The following two corollaries are immediate consequences of Theorem~\ref{main2}. \begin{corollary}\label{unitscor} Suppose $n$ is odd and not divisible by $3$ or $5$. If $z$ is a unit modulo $n$, then there exist units $a$ and $b$ in $\mathbb{Z}_n$ such that $a^2+b^2\equiv z\pmod{n}$. \end{corollary} \begin{corollary} If $n$ is even, then no unit can be written as the sum of two square units.\end{corollary} To further address Question~\ref{qhjl}, in the following theorem we loosen the restriction that $a$ and $b$ are units in $\mathbb{Z}_{p^k}$ and instead only require $a^2$ and $b^2$ to be non-zero modulo $p^k$. \begin{theorem}\label{3mod4non-zero} Let $p\geq 7$ be a prime with $p\equiv 3 \pmod{4}$ and let $k$ be a positive integer. For a fixed non-zero element $z\in\mathbb{Z}_{p^k}$, there exist elements $a$ and $b$ with $a^2$ and $b^2$ each non-zero in $\mathbb{Z}_{p^k}$ such that $a^2+b^2\equiv z\pmod{p^k}$ if and only if $z\equiv xp^r\pmod{p^k}$ for some unit $x$ in $\mathbb{Z}_{p^k}$ and some non-negative even integer $r1$. Suppose that $d$ is unit-special in $\mathbb{Z}_{p^k}$. Then there exist units $a,b,$ and $c$ in $\mathbb{Z}_{p^k}$ such that $a^2+b^2-dc^2\equiv z\pmod{p^k}$ for all $z\in\mathbb{Z}_{p^k}$. It follows that $a^2+b^2-dc^2\equiv z\pmod{p}$. However, since $d$ is not unit-special in $\mathbb{Z}_p$, there is some element $z\in\mathbb{Z}_p$ that cannot be written in this form. Therefore $d$ cannot be unit-special in $\mathbb{Z}_{p^k}$. \end{proof} \begin{lemma}\label{special5} Let $k$ be a positive integer. An integer $d$ is unit-special in $\mathbb{Z}_{5^k}$ if and only if $d\equiv \pm 2\pmod{5}$. \end{lemma} \begin{proof} The theorem can be verified computationally for $k=1$. If $d$ is unit-special in $\mathbb{Z}_{5^k}$ for some $k>1$, then $d$ is also unit-special modulo 5 whence $d\equiv \pm 2\pmod{5}$. Conversely, suppose that $k>1$ and $d\equiv \pm 2\pmod{5}$. Let $m$ be any fixed integer. Then there exist units $a,b,$ and $c$ modulo $5$ such that $a^2+b^2-dc^2\equiv m\pmod{5}$. As such, by Lemma~\ref{lifting} there exists a unit $b_k\in\mathbb{Z}_{5^k}$ with $$a^2+b_k^2\equiv m+dc^2\pmod{5^k}.$$ Therefore the result holds for all positive integers $k$. \end{proof} \begin{lemma}\label{specialunits} For an odd positive integer $n$ not divisible by $3$ or $5$, if $d$ is a unit in $\mathbb{Z}_n$, then $d$ is unit-special in $\mathbb{Z}_n$. \end{lemma} \begin{proof} Let $d$ be a unit modulo $n$, and fix $m\in \mathbb{Z}_n$. We proceed with two cases as to whether or not $m+d$ is a unit modulo $n$. Suppose $m+d$ is a unit modulo $n$, then by Corollary~\ref{unitscor} we may obtain units $a$ and $b$ modulo $n$ such that $$a^2+b^2\equiv m+d\pmod{n}.$$ The result follows by choosing $c\equiv 1\pmod{n}$. Now suppose that $m+d$ is not a unit modulo $n$. Factor $n$ as $$n=\left(\prod_{i=1}^t p_i^{e_i}\right)\cdot\left(\prod_{j=1}^r q_j^{f_j}\right)$$ where each $p_i$ is distinct with $m+d\not\equiv 0 \pmod{p_i}$, and each $q_j$ is distinct with $m+d\equiv 0\pmod{q_j}$. Then it follows from Corollary~\ref{unitscor} that there exist units $a_i$ and $b_i$ in $\mathbb{Z}_{p^{e_i}}$ such that $a_i^2+b_i^2\equiv m+d\pmod{p_i}$. Now, notice that since $d$ is a unit modulo $n$, then $d$ is also a unit modulo ${q_j}$. We deduce that $m+4d\not\equiv 0\pmod{q_j}$, since otherwise $$m+d\equiv 0\pmod{q_j}\equiv m+4d\pmod{q_j}$$ would imply that $4\equiv 1\pmod{q_j}$. This cannot happen since $n$ is not divisible by 3. Thus, $m+4d$ is a unit in $\mathbb{Z}_{q_j}$. It follows from Corollary~\ref{unitscor} that there exist units $a'_i$ and $b'_i$ in $\mathbb{Z}_{q_j^{f_j}}$ such that $$(a'_i)^2+(b'_i)^2\equiv m+4d\pmod{q_j^{f_j}}.$$ Next, we use the Chinese remainder theorem to choose $a,b,$ and $c$ which satisfy the system of congruences $$a\equiv a_i\pmod{p_i^{e_i}}\qquad\qquad\qquad a\equiv a'_i\pmod{q_j^{f_j}}$$ $$b\equiv b_i\pmod{p_i^{e_i}}\qquad\qquad\qquad b\equiv b'_i\pmod{q_j^{f_j}}$$ and $$c\equiv 1\pmod{p_i^{e_i}}\qquad\qquad\qquad c\equiv 2\pmod{q_j^{f_j}}.$$ This ensures that $a,b,$ and $c$ are units in $\mathbb{Z}_n$ with $a^2+b^2-dc^2\equiv m\pmod{n}$. \end{proof} The following Corollary follows from Lemma~\ref{specialunits} and Theorem~\ref{iftrue}. \begin{corollary} Let $n$ be an odd positive integer with $n\not\in\{1,3,5,9,25\}$. Then every integer can be written as the sum of three non-zero squares in $\mathbb{Z}_n$.\end{corollary} \begin{proof} Write $n=3^r5^tm$ with $m$ relatively prime to $3$ and $5$. First suppose that $m\neq 1$. Since $-1$ is a unit in $\mathbb{Z}_m$, it follows from Lemma~\ref{specialunits} that for any integer $z$ there exist units $a_1$, $b_1$, and $c_1$ in $\mathbb{Z}_m$ such that $a_1^2+b_1^2+c_1^2\equiv z\pmod{m}$. Theorem~\ref{iftrue} implies that there exist integers $a_2,b_2,$ and $c_2$ such that $a_2^2+b_2^2+c_2^2\equiv z\pmod{3^r5^t}$. Using the Chinese remainder theorem as stated in Theorem~\ref{hjlcrt}, there exist $a,b,$ and $c$ such that $a^2+b^2+c^2\equiv z\pmod{n}$. Such a choice of $a$ ensures that $a^2\equiv a_1^2\pmod{m}$. Since $a_1$ is relatively prime to $m$ we see that $m$ does not divide $a^2$. Thus, $n$ does not divide $a^2$. This shows that $a^2$ is non-zero in $\mathbb{Z}_n$. Similar arguments show that $b^2$ and $c^2$ are non-zero in $\mathbb{Z}_n$. Now suppose that $m=1$ so that $n=3^r5^t$. Following the Hensel Lifting argument of Lemma~\ref{lifting}, it is easy to show that for a positive integer $k$, if $z$ can be written as the sum of three non-zero squares in $\mathbb{Z}_{3^{k-1}}$, then it can also be written as the sum of three non-zero squares in $\mathbb{Z}_{3^k}$. We check computationally that every integer can be written as the sum of three non-zero squares in $\mathbb{Z}_{3^3}$. Thus, for $k\geq 3$, we can write every integer as the sum of three non-zero squares in $\mathbb{Z}_{3^k}$. The same argument shows that we can also write every integer as the sum of three non-zero squares in $\mathbb{Z}_{5^3}$. Using an argument similar to the one in the first paragraph of the proof, it then follows that if $r\geq 3$ or $t\geq 3$, every integer can be written as the sum of three non-zero squares in $\mathbb{Z}_n$. The remaining finite number of cases can easily be confirmed computationally. \end{proof} We are now in a position to prove Theorem~\ref{main}. \begin{proof}[Proof of Theorem~\ref{main}] Lemma~\ref{special23} implies that if $d$ is unit-special in $\mathbb{Z}_n$, then $n$ is not divisible by 2 or 3. It follows from Lemma~\ref{special5} that if $5$ divides $n$, then $d\equiv \pm 2\pmod{5}$. Now suppose that $n$ is divisible by some prime $p\equiv 3\pmod{4}$. If $d$ is unit-special in $\mathbb{Z}_n$, then we may obtain units $a,b,c$ modulo $n$ such that $$a^2+b^2-dc^2\equiv 0\pmod{n}.$$ It would then follow that $$a^2+b^2-dc^2\equiv 0\pmod{p}.$$ If $d\equiv 0 \pmod{p}$, then this would contradict Theorem~\ref{3mod4}. As such, we conclude $\gcd(d,p)=1$. To prove the converse, we first show that if $n$ is odd, $5$ does not divide $n$, and $n$ is not divisible by any prime $p\equiv 3\pmod{4}$, then every integer is unit-special in $\mathbb{Z}_n$. To see this, let $m$ and $d$ be fixed integers. By Corollary~\ref{1mod4cor}, there exist units $a$ and $b$ in $\mathbb{Z}_n$ such that $a^2+b^2\equiv m+d\pmod{n}$. Since $m$ is chosen arbitrarily, this shows that $d$ is unit-special in $\mathbb{Z}_n$ since $$a^2+b^2-d\cdot (1)^2\equiv m\pmod{n}.$$ This observation together with Theorem~\ref{hjlcrt}, Lemma~\ref{special5}, and Lemma~\ref{specialunits} finishes the proof of the theorem. \end{proof} \section{Acknowledgments} The authors would like to thank the anonymous referee for suggestions that improved this article. \begin{thebibliography}{1} \bibitem{hwnt} G. H. Hardy and E. M. Wright, \emph{An Introduction to the Theory of Numbers}, fifth edition, Oxford University Press, 1979. \bibitem{hjl} J. Harrington, L. Jones, and A. Lamarche, Representing integers as the sum of two squares in the ring {$\Bbb Z_n$}, \emph{J. Integer Seq.} \textbf{17} (2014), \href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Jones/jones14.html}{Article 14.7.4}. \bibitem{Lam} P. C. Lam, Representation of integers Using $a^2+b^2-dc^2$, \emph{J. Integer Seq.} \textbf{18} (2015), \href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Lam/lam2.html}{Article 15.8.6}. \bibitem{Nowicki} A. Nowicki, The numbers $a^2+b^2-dc^2$, \emph{J. Integer Seq.} \textbf{18} (2015), \href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Nowicki/nowicki3.html}{Article 15.2.3}. \bibitem{suzuki} J. Suzuki, \emph{Euler and Number Theory: A Study in Mathematical Invention}, Leonhard Euler: Life, Work and Legacy, Studies in the History of Philosophy of Mathematics, {\bf 5}, Robert E. Bradley and C. Edward Sandifer, eds., Elsevier, 2007. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11E25; Secondary 11A07. \noindent \emph{Keywords: } sum of squares, ring of integers modulo $n$, congruence. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received August 1 2015; revised versions received September 18 2015; September 30 2015. Published in {\it Journal of Integer Sequences}, November 25 2015. Order of authors switched, January 11 2016. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}