On the Number of Regular Integers Modulo $n$ and Its Significance for Cryptography

We present four combinatorial proofs of Morgado’s formula for the number $\varrho (n)$ of non-congruent regular integers modulo $n$, corresponding to sequence A055653 in the On-Line Encyclopedia of Integer Sequences (OEIS), where an integer $m$ is said to be regular modulo $n$ if the congruence $m^{2}x\equiv m(\mathrm{m}\mathrm{o}\mathrm{d}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.