\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \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} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \usepackage{enumerate} \usepackage{url} \newcommand{\udiv}{\,{\mid}^{\ast}} \newcommand{\reg}{\text{reg}} \newcommand{\znr}{\mathbb{Z}_n^\reg} \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} \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 On the Number of Regular Integers Modulo $n$ \\ \vskip .1in and Its Significance for Cryptography } \vskip 1cm \large Klaus Dohmen and Mandy Lange-Geisler \\ Fachgruppe Mathematik \\ Hochschule Mittweida \\ Technikumplatz 17\\ 09648 Mittweida\\ Germany \\ \href{mailto: dohmen@hs-mittweida.de}{\tt dohmen@hs-mittweida.de}\\ \href{mailto: mlange1@hs-mittweida.de}{\tt mlange1@hs-mittweida.de}\\ \end{center} \vskip .2 in \begin{abstract} We present four combinatorial proofs of Morgado's formula for the number $\varrho(n)$ of non-congruent regular integers modulo~$n$, corresponding to sequence \seqnum{A055653} in the On-Line Encyclopedia of Integer Sequences (OEIS), where an integer $m$ is said to be \emph{regular modulo~$n$} if the congruence $m^2 x \equiv m$ (mod $n$) has a solution $x\in\mathbb{Z}$. To illustrate the significance of the sequence and Morgado's formula, we relate them to a recent multi-prime, multi-power generalization of the RSA cryptosystem. \end{abstract} \section{Introduction} This work is motivated by a recent multi-prime, multi-power generalization of the RSA cryptosystem \cite{Dohmen-Lange2025}, where the modulus is an arbitrary integer $n>1$ and the messages are regular integers modulo~$n$. The number of regular integers $m$ in $\mathbb{Z}_n = \{0,\ldots,n-1\}$ is crucial for estimating the probability of correct decryption in this generalized scheme for random messages $m$ from the larger message space $\mathbb{Z}_n$. Throughout this work, $\mathbb{N}$ denotes the set of positive integers. For $n\in\mathbb{N}$, the notion of a regular integer modulo $n$, introduced by Morgado \cite{Morgado1972}, is closely related to the algebraic concept of a von Neumann regular element. Recall that, for a ring $R$, an element $m\in R$ is called \emph{von Neumann regular} if there exists an element $x\in R$ such that $mxm=m$. \begin{definition}[Morgado \cite{Morgado1972}] For each $n\in\mathbb{N}$, an integer $m$ is said to be \emph{regular modulo~$n$} if the congruence $m^2 x \equiv m$ (mod $n$) has a solution $x\in\mathbb{Z}$. \end{definition} For each $n\in\mathbb{N}$, we use $\znr$ to denote the set of all $m\in\mathbb{Z}_n$ that are regular modulo~$n$, and $\varrho(n)$ to denote its cardinality. The sequence $(\varrho(n))_{n\ge 1}$ appears as sequence \seqnum{A055653} in the On-Line Encyclopedia of Integer Sequences (OEIS) \cite{OEIS2026}. It was first studied by Morgado~\cite{Morgado1972} and has since been investigated by several authors \cite{Alkam2008,Apostol2013,Toth2008}. Recall that $d\in\mathbb{N}$ is called a \emph{unitary divisor} of~$n$ if $d$ divides $n$ and $\gcd(d, n/d)=1$. Following Morgado \cite{Morgado1972}, we write $d\udiv n$, if $d$ is a unitary divisor of~$n$. Our focus is on the following formula, in which $\varphi$ denotes Euler's totient function. \begin{theorem}[Morgado \cite{Morgado1972}] For every $n\in\mathbb{N}$, \begin{align} \label{eq:2} \varrho(n) & = \sum_{d\udiv n} \varphi(d) . \end{align} \end{theorem} In this paper, we provide four proofs of~\eqref{eq:2}. Unlike previously published proofs \cite{Alkam2008,Toth2008}, the proofs presented here are combinatorial in nature and do not rely on the multiplicativity of~$\varrho$. Instead, we repeatedly use the bijection principle and, in our final proof, the inclusion-exclusion principle. Continuing along this line of reasoning, the multiplicativity of $\varrho$ follows naturally from~\eqref{eq:2}. The paper is organized as follows. In Section~\ref{sec:preliminaries} we provide a concise proof of Morgado's~\cite{Morgado1972} characterization of regular integers modulo~$n$, which we use in our proofs of Morgado's formula \eqref{eq:2} in Sections~\ref{sec:proof-equiv-relat}--\ref{sec:proof-incl-excl}. Each of our four combinatorial proofs is self-contained and sheds a different light on the formula. From the authors' perspective, the purely bijective proof in Section~\ref{sec:proof-bijection} is particularly noteworthy, as it yields an encoding of the regular integers modulo~$n$ and may provide further insight into the study of the sequence \seqnum{A055653}. In Section~\ref{sec:application-rsa}, we relate this sequence and Morgado's formula to the probability of correct decryption of a random message $m\in\mathbb{Z}_n$ in a multi-prime, multi-power generalization of the RSA cryptosystem, recently established by the present authors \cite{Dohmen-Lange2025}. \section{Preliminaries} \label{sec:preliminaries} The following proposition, which is due to Morgado \cite{Morgado1972}, provides necessary and sufficient conditions for an integer $m$ to be regular modulo $n$. To keep this paper self-contained, we provide our own concise proof. \begin{proposition}[Morgado \cite{Morgado1972}] \label{sec:regul-numb-unit-2} For all $n\in\mathbb{N}$ and $m\in\mathbb{Z}$, the following statements are equivalent: \begin{enumerate}[(a)] \item $m$ is regular modulo $n$, \item $\gcd(m^2,n) = \gcd(m,n)$, \item $\gcd(m,n)\udiv n$. \end{enumerate} \end{proposition} \begin{proof} \ \\ \vskip -.15in $\text{(a)} \Leftrightarrow \text{(b)}$: In general, for every $a,b\in\mathbb{Z}$, the congruence $ax\equiv b$ (mod $n$) has a solution $x\in\mathbb{Z}$ if and only if $\gcd(a,n)\mid b$. Hence, $m$ is regular modulo $n$ if and only if $\gcd(m^2,n)\mid m$, which in turn holds if and only if $\gcd(m^2,n)=\gcd(m,n)$. \medskip $\text{(b)} \Rightarrow \text{(c)}$: Let $d=\gcd(m,n)$ and $g=\gcd(d,n/d)$. By induction on $k$ we show that $g^k\mid d$ for all $k\ge 0$, which implies $g=1$ and thus (c). The case $k=0$ is trivial. For the induction step, assume that $k>0$ and $g^{k-1}\mid d$. Then, {\setlength{\thinmuskip}{2mu} $g^k\mid d\,g = \gcd({d}^{\,2}, d\,n/d) \mid \gcd(m^2,n) = \gcd(m,n)=d$. } \medskip $\text{(c)} \Rightarrow \text{(a)}$: From the assumption we have $\gcd(\gcd(m,n), n/\gcd(m,n))=1$, that is, $\gcd(m,n/\gcd(m,n))=1$. By Bezout's lemma, there exist $x,y\in\mathbb{Z}$ such that $m^2x + \frac{nm}{\gcd(m,n)}y = m$, whence $m^2x \equiv m$ (mod $n$). \end{proof} \section{Proof by equivalence relation} \label{sec:proof-equiv-relat} Our first proof of (\ref{eq:2}) is inspired by Morgado's original proof \cite{Morgado1972}, but is considerably more formal and combinatorial, as it makes explicit use of an equivalence relation and the bijection principle on the resulting equivalence classes. Recall that $\mathbb{Z}_n^\ast = \{m\in\mathbb{Z}_n\mid \gcd(m,n)=1\}$. \begin{proof} For $m_1,m_2\in\znr$, let $m_1\sim m_2$ if $\gcd(m_1,n)=\gcd(m_2,n)$; this defines an equivalence relation on $\znr$. By Proposition~\ref{sec:regul-numb-unit-2}, $m\in\znr$ if and only if $\gcd(m,n)\udiv n$, so the equivalence classes are of the form $C_{n,d}$ with $d\udiv n$, where \begin{gather*} C_{n,d} = \left\{ m\in\znr\mathrel| \gcd(m,n)=d \right\}. \end{gather*} Using the bijection principle, we show that for every unitary divisor $d$ of~$n$, \begin{gather} \label{cnd} |C_{n,d}| = |\mathbb{Z}_{n/d}^\ast| . \end{gather} To this end, for $d\udiv n$ define $h_{n,d} : C_{n,d}\rightarrow \mathbb{Z}_{n/d}^\ast$ by $h_{n,d}(m) = m \bmod (n/d)$. This map is well defined, since $\gcd(m \bmod (n/d),n/d) = \gcd(m,n/d) = \gcd(m,n,n/d) = \gcd(d,n/d)=1$. It remains to show that $h_{n,d}$ is bijective. \medskip \emph{Injectivity.} Suppose that $h_{n,d}(m_1) = h_{n,d}(m_2)$. Then, $m_1 \equiv m_2$ (mod $n/d$). Since $m_1,m_2\in C_{n,d}$, we have $\gcd(m_1,n) = \gcd(m_2,n)=d$, which implies $m_1 \equiv m_2$ (mod $d$). Because $d$ and $n/d$ are coprime, combining both congruences gives $m_1\equiv m_2$ (mod $n$), and hence $m_1=m_2$. \medskip \emph{Surjectivity.} Let $d'\in\mathbb{Z}_{n/d}^\ast$, and define $m = d ((d'\/i) \bmod (n/d))$, where $i$ denotes an inverse of $d$ modulo $n/d$. We claim the following: \begin{enumerate}[(i)] \item \label{first} $m\in C_{n,d}$\,; \item \label{second} $h_{n,d}(m)=d^\prime$. \end{enumerate} For \eqref{first}, it suffices to show that $\gcd(m,n)=d$. Indeed, since $d\mid m$ and $d\mid n$, and since $\gcd(d',n/d)=1$ and $\gcd(i,n/d)=1$, we have \[ \gcd(m,n) = d \gcd(d'\/i \bmod (n/d), n/d) = d \gcd(d'\/i, n/d) = d \gcd(i, n/d) = d. \] Part~\eqref{second} follows immediately, since \[ h_{n,d}(m) = m \bmod (n/d) = (d\/i \bmod (n/d))(d' \bmod (n/d))=d'. \] From \eqref{cnd} and the disjointness of the equivalence classes, we conclude that \begin{gather*} \label{eq:8} \varrho(n) = \sum_{d\udiv n} \, |C_{n,d}| = \sum_{d\udiv n} \, |\mathbb{Z}_{n/d}^\ast| =\sum_{d\udiv n} \, \varphi\left( \frac{n}{d} \right) = \sum_{d\udiv n} \varphi(d) , \end{gather*} which proves~\eqref{eq:2}. \end{proof} \section{A purely bijective proof} \label{sec:proof-bijection} Our next proof is purely bijective. The idea is to establish a bijection between $\znr$ and the set of pairs $(d,d')$ with $d\udiv n$ and $d'\in\mathbb{Z}_d^\ast$ that are counted by the right-hand side of (\ref{eq:2}). This bijection yields an encoding of $\znr$ that may prove useful beyond this proof. \begin{proof} Let $U_n$ denote the set of unitary divisors of~$n$. Consider the map \begin{gather*} \label{eq:3} f_n : \znr \rightarrow \left\{ (d,d')\mathrel| d\in U_n, d'\in\mathbb{Z}_d^\ast \right\}, \end{gather*} defined by \begin{gather*} \label{eq:6} f_n(m) := \left( \frac{n}{\gcd(m,n)}, m\bmod \frac{n}{\gcd(m,n)} \right) . \end{gather*} We first show that $f_n$ is well defined. Let $d = n/\gcd(m,n)$. Then $d\in U_n$, and hence $\gcd(d, m \bmod d) = \gcd(d, m) = \gcd(d,m,n) = \gcd(d,\gcd(m,n)) = \gcd(d,n/d)=1$, which implies $m\bmod d\in\mathbb{Z}_d^\ast$. To apply the bijection principle, we show that $f_n$ is bijective. \medskip \emph{Injectivity.} Suppose that $f_n(m_1) = f_n(m_2)$. Then, $\gcd(m_1,n) = \gcd(m_2,n)$, which we denote by~$d$. Evidently, $m_1\bmod n/d = m_2\bmod n/d$, which means that $m_1\equiv m_2$ (mod $n/d$). From $\gcd(m_1,n)=d$ we can write $m_1=d m_1'$, $m_2=d m_2'$, and $n=d n'$ with $\gcd(m_1',n')=\gcd(m_2',n')=1$. Therefore, $m_1-m_2 = d(m_1'-m_2')$, so $d\mid m_1-m_2$, which gives $m_1\equiv m_2$ (mod $d$). Since $d$ and $n/d$ are coprime (because $d\udiv n$), combining the congruences $m_1\equiv m_2$ (mod $d$) and $m_1\equiv m_2$ (mod $n/d$) gives $m_1\equiv m_2$ (mod $n$), and hence $m_1=m_2$. \medskip \emph{Surjectivity.} Let $d\in U_n$ and $d'\in\mathbb{Z}_d^\ast$. We define $m$ as \begin{gather} \label{eq:1} m = \frac{n}{d} \big(( d'\/j ) \bmod d \big), \end{gather} where $j$ is an inverse of $n/d$ modulo~$d$. We claim the following: \begin{enumerate}[(i)] \item \label{firstclaim} $m\in\znr$\,; \item \label{secondclaim} $f_n(m)=(d,d')$. \end{enumerate} Since $n/d$ divides both $m$ and $n$, and since $\gcd(d',d)=1$ and $\gcd(j,d)=1$, we have \begin{gather} \label{eq:5} \gcd(m,n) = \frac{n}{d} \gcd\left( \left( d'\/j \right) \bmod d, d\right) = \frac{n}{d} \gcd\left( d'\/j , d\right) = \frac{n}{d} \gcd\left( j, d\right) = \frac{n}{d}. \end{gather} Hence $\gcd(m,n)\udiv n$, and by Proposition~\ref{sec:regul-numb-unit-2}, $m\in\znr$, as claimed in \eqref{firstclaim}. For part \eqref{secondclaim}, we note that $d = n/\gcd(m,n)$ follows from \eqref{eq:5}, and $d'=m\bmod d$ follows from \eqref{eq:1}, since $j$ is an inverse of $n/d$ modulo~$d$. Thus, \eqref{firstclaim} and \eqref{secondclaim} are shown, and the proof is complete. \end{proof} To illustrate the proof, we list the assignments $m\mapsto f_{20}(m)$ for $m\in\mathbb{Z}_{20}^{\text{reg}}$: \begin{alignat*}{5} 0 & \mapsto (1,0), & \quad 4 & \mapsto (5,4), & \quad 8 & \mapsto (5,3), & \quad 12 & \mapsto (5,2), & \quad 16 & \mapsto (5,1), \\ 1 & \mapsto (20,1), & \quad 5 & \mapsto (4,1), & \quad 9 & \mapsto (20,9), & \quad 13 & \mapsto (20,13), & \quad 17 & \mapsto (20,17), \\ 3 & \mapsto (20,3), & \quad 7 & \mapsto (20,7), & \quad 11 & \mapsto (20,11), & \quad 15 & \mapsto (4,3), & \quad 19 & \mapsto (20,19). \end{alignat*} \begin{remark} In view of \eqref{eq:1}, the inverse of $f_n$ takes the form $f_n^{-1}(d,d') = \frac{n}{d} ( ( ( n/d \bmod d)^{-1} d' ) \bmod d )$ for every $d\in U_n$ and $d'\in\mathbb{Z}_d^\ast$. \end{remark} \begin{remark} The proof can be restated by defining $f_n(m) := ( \gcd(m,n), m\bmod n/\gcd(m,n))$, which maps from $\znr$ to $\{ (d,d')\mathrel| d\in U_n, d'\in\mathbb{Z}_{n/d}^\ast \}$. In this setting, $f_n^{-1}(d,d') = d(((d \bmod (n/d))^{-1}d')\bmod (n/d))$. \end{remark} \section{Proof by reduced fractions} \label{sec:proof-reduced-fractions} Our third proof is inspired Gauss's formula $n = \sum_{d\mid n} \varphi(d)$, as reproduced in the textbook by Graham, Knuth, and Patashnik \cite[pp.\ 134--135]{Graham1994}. The key idea is to establish a bijection between $\znr$ and the set of reduced fractions of the form $k/d$, where $d\udiv n$ and $k