\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
Joshua Harrington\\
Department of Mathematics\\
Cedar Crest College\\
Allentown, PA 18104 \\
USA \\
\href{mailto:joshua.harrington@cedarcrest.edu}{\tt Joshua.Harrington@cedarcrest.edu}\\
\ \\
Samuel S. Gross \\
Noblis, Inc.\\
Falls Church, VA 22042 \\
USA \\
\href{Samuel.Gross@noblis-nsp.com}{\tt samuel.gross@noblis-nsp.com}\\
\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.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}