\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 $r<k$.
\end{theorem} 

\begin{proof}  Suppose that $a^2$ and $b^2$ are non-zero elements in $\mathbb{Z}_{p^k}$ with 
$a^2+b^2\equiv z\pmod{p^k}$.  If $z$ is a unit in $\mathbb{Z}_{p^k}$, then we may
write $z\equiv zp^0\pmod{p^k}$ which proves the result.  
Suppose, then, that $z$ is not a unit in
$\mathbb{Z}_{p^k}$.  Since $z\not\equiv 0\pmod{p^k}$, then we can write $z\equiv xp^r\pmod{p^k}$ 
for some unit $x\in\mathbb{Z}_{p^k}$ and some positive integer $r<k$.  Thus, 
$$a^2+b^2=xp^r+cp^k=p^r(x+cp^{k-r}),$$ 
for some $c\in\mathbb{Z}$.
It follows that $p$ divides $a^2+b^2$, but $p$ does not divide $x+cp^{k-r}$ since $x$ is a 
unit in $\mathbb{Z}_{p^k}$.  Hence, $p^r$ divides $a^2+b^2$, but $p^{r+1}$ does not.   Since 
$p\equiv 3\pmod{4}$, it follows by Theorem~\ref{Euler} that $r$ must be even.

Conversely, suppose that $z\equiv xp^r\pmod{p^k}$ for some unit $x\in\mathbb{Z}_{p^k}$ and some 
non-negative even integer $r<k$.  Since $x$ is a unit in $\mathbb{Z}_{p^k}$, it follows by 
Theorem~\ref{3mod4} that there exist units $u$ and $v$ such that $u^2+v^2\equiv x\pmod{p^k}$.  
Since $r$ is an even integer, we may define $a\equiv up^{r/2}\pmod{p^k}$ and $b\equiv vp^{r/2}\pmod{p^k}$.  
Notice that $a^2$ and $b^2$ are non-zero in $\mathbb{Z}_{p^k}$ since $r<k$.  Furthermore, 

\begin{align*}
a^2+b^2&\equiv \left(up^{r/2}\right)^2+\left(vp^{r/2}\right)^2\pmod{p^k}\\
&\equiv u^2p^r + v^2p^r \pmod{p^k}\\
&\equiv xp^r\pmod{p^k}.
\end{align*}
This completes the proof of the theorem.
\end{proof}

The Chinese remainder theorem as stated in 
Theorem~\ref{hjlcrt} along with Theorems~\ref{hjl} and \ref{3mod4non-zero} partially answers Question~\ref{qhjl} when $n$ is not divisible by 2 or 3.  




\section{Special numbers in $\mathbb{Z}_n$}\label{section4}

For convenience and completeness, we restate and prove Theorem~\ref{iftrue}.
\begin{theoremrestate}  
For any 
odd integer $n\geq 3$, any unit $d$ in $\mathbb{Z}_n$, and any integer $m$, there exist integers $a,b,$ and $c$ such that $a^2+b^2-dc^2\equiv m\pmod{n}$.
\end{theoremrestate}

\begin{proof}  
Let $n\geq 3$ be an integer and let $d$ be a unit in $\mathbb{Z}_n$.  By the 
Chinese remainder theorem and Theorem~\ref{Dirichlet} there exists some prime $p$ 
satisfying 
$$p\equiv 1\pmod{4}\qquad\qquad\text{and}\qquad\qquad p\equiv d\pmod{n}.$$
It follows from Theorem~\ref{nowickilam} that such a prime must be a special number.  Therefore, for any integer $m$, there exist integers 
$a,b,$ and $c$ such that $a^2+b^2-pc^2=m$.  In this case $a,b,$ and $c$ will satisfy
$$a^2+b^2-dc^2\equiv m\pmod{n}.$$
This proves the theorem.
\end{proof}

Our main goal in this section is to prove Theorem~\ref{main}.  To do this, we first establish three lemmas.





\begin{lemma}\label{special23}  Let $k$ be a positive integer. Then there are no
unit-special numbers modulo $2^k$ or $3^k$.
\end{lemma}

\begin{proof}  
The theorem can be checked computationally for $k=1$.  Let $p\in\{2,3\}$ and $k>1$. 
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}

                                                                                


.
