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

Klaus Dohmen and Mandy Lange-Geisler Fachgruppe Mathematik Hochschule Mittweida Technikumplatz 17 09648 Mittweida Germany

                    dohmen@hs-mittweida.de
                    mlange1@hs-mittweida.de

Abstract We present four combinatorial proofs of Morgado’s formula for the number ϱ(n) of non-congruent regular integers modulo n, corresponding to sequence \underline{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 ≡ m (mod n) has a solution x ∈ ℤ. 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.

1 Introduction

This work is motivated by a recent multi-prime, multi-power generalization of the RSA cryptosystem [3], where the modulus is an arbitrary integer n > 1 and the messages are regular integers modulo n. The number of regular integers m in ℤ_{n} = {0, …, n − 1} is crucial for estimating the probability of correct decryption in this generalized scheme for random messages m from the larger message space ℤ_{n}.

Throughout this work, ℕ denotes the set of positive integers. For n ∈ ℕ, the notion of a regular integer modulo n, introduced by Morgado [5], is closely related to the algebraic concept of a von Neumann regular element. Recall that, for a ring R, an element m ∈ R is called von Neumann regular if there exists an element x ∈ R such that mxm = m.

Definition 1 (Morgado [5]). For each n ∈ ℕ, an integer m is said to be regular modulo n if the congruence m^{2}x ≡ m (mod n) has a solution x ∈ ℤ.

For each n ∈ ℕ, we use ℤ_{n}^{reg} to denote the set of all m ∈ ℤ_{n} that are regular modulo n, and ϱ(n) to denote its cardinality. The sequence (ϱ(n))_{n≥1} appears as sequence \underline{A055653} in the On-Line Encyclopedia of Integer Sequences (OEIS) [6]. It was first studied by Morgado [5] and has since been investigated by several authors [1, 2, 8].

Recall that d ∈ ℕ is called a unitary divisor of n if d divides n and gcd(d, n/d) = 1. Following Morgado [5], we write d |^{∗}n, if d is a unitary divisor of n. Our focus is on the following formula, in which φ denotes Euler’s totient function.

Theorem 2 (Morgado [5]). For every n ∈ ℕ,

ϱ(n) = ∑_{d |^{∗}n} φ(d).  (1)

In this paper, we provide four proofs of (1). Unlike previously published proofs [1, 8], the proofs presented here are combinatorial in nature and do not rely on the multiplicativity of ϱ. Instead, we repeatedly use the bijection principle and, in our final proof, the inclusionexclusion principle. Continuing along this line of reasoning, the multiplicativity of ϱ follows naturally from (1).

The paper is organized as follows. In Section 2 we provide a concise proof of Morgado’s [5] characterization of regular integers modulo n, which we use in our proofs of Morgado’s formula (1) in Sections 3–6. 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 4 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 \underline{A055653}.

In Section 7, we relate this sequence and Morgado’s formula to the probability of correct decryption of a random message m ∈ ℤ_{n} in a multi-prime, multi-power generalization of the RSA cryptosystem, recently established by the present authors [3].

2 Preliminaries

The following proposition, which is due to Morgado [5], 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.

Proposition 3 (Morgado [5]). For all n ∈ ℕ and m ∈ ℤ, the following statements are equivalent:

(a) m is regular modulo n,

(b) gcd(m^{2}, n) = gcd(m, n), (c) gcd(m, n) |^{∗}n.

Proof.

(a) ⇔ (b): In general, for every a, b ∈ ℤ, the congruence ax ≡ b (mod n) has a solution x ∈ ℤ if and only if gcd(a, n) | b. Hence, m is regular modulo n if and only if gcd(m^{2}, n) | m, which in turn holds if and only if gcd(m^{2}, n) = gcd(m, n).

(b) ⇒ (c): Let d = gcd(m, n) and g = gcd(d, n/d). By induction on k we show that g^{k} | d for all k ≥ 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} | d. Then, g^{k} | dg = gcd(d^{2},dn/d) | gcd(m^{2},n) = gcd(m,n) = d.

(c) ⇒ (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 ∈ ℤ such that m^{2}x + \frac{nm}{gcd(m,n)}y = m, whence m^{2}x ≡ m (mod n).

3 Proof by equivalence relation

Our first proof of (1) is inspired by Morgado’s original proof [5], 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 ℤ_{n}^{∗} = {m ∈ ℤ_{n} | gcd(m, n) = 1}.

Proof. For m_{1}, m_{2} ∈ ℤ_{n}^{reg}, let m_{1} ∼ m_{2} if gcd(m_{1}, n) = gcd(m_{2}, n); this defines an equivalence relation on ℤ_{n}^{reg}. By Proposition 3, m ∈ ℤ_{n}^{reg} if and only if gcd(m, n) |^{∗}n, so the equivalence classes are of the form C_{n,d} with d |^{∗}n, where

C_{n,d} = {m ∈ ℤ_{n}^{reg} | gcd(m, n) = d} .

Using the bijection principle, we show that for every unitary divisor d of n,

|C_{n,d}| = |ℤ_{n/d}^{∗}|.  (2)

To this end, for d |^{∗}n define h_{n,d} : C_{n,d} → ℤ_{n/d}^{∗} by h_{n,d}(m) = m mod (n/d). This map is well defined, since gcd(m mod (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.

Injectivity. Suppose that h_{n,d}(m_{1}) = h_{n,d}(m_{2}). Then, m_{1} ≡ m_{2} (mod n/d). Since m_{1}, m_{2} ∈ C_{n,d}, we have gcd(m_{1}, n) = gcd(m_{2}, n) = d, which implies m_{1} ≡ m_{2} (mod d). Because d and n/d are coprime, combining both congruences gives m_{1} ≡ m_{2} (mod n), and hence m_{1} = m_{2}.

Surjectivity. Let d′ ∈ ℤ_{n/d}^{∗}, and define m = d((d′i) mod (n/d)), where i denotes an inverse of d modulo n/d. We claim the following:

(i) m ∈ C_{n,d}; (ii) h_{n,d}(m) = d′.

For (i), it suffices to show that gcd(m, n) = d. Indeed, since d | m and d | n, and since gcd(d′, n/d) = 1 and gcd(i, n/d) = 1, we have

gcd(m, n) = d gcd(d′i mod (n/d), n/d) = d gcd(d′i, n/d) = d gcd(i, n/d) = d.

Part (ii) follows immediately, since

h_{n,d}(m) = m mod (n/d) = (di mod (n/d))(d′ mod (n/d)) = d′.

From (2) and the disjointness of the equivalence classes, we conclude that

ϱ(n) = ∑_{d |^{∗}n} |C_{n,d}| = ∑_{d |^{∗}n} |ℤ_{n/d}^{∗}| = ∑_{d |^{∗}n} φ (\frac{n}{d}) = ∑_{d |^{∗}n} φ(d),

which proves (1).

4 A purely bijective proof

Our next proof is purely bijective. The idea is to establish a bijection between ℤ_{n}^{reg} and the set of pairs (d, d′) with d |^{∗}n and d′ ∈ ℤ_{d}^{∗} that are counted by the right-hand side of (1). This bijection yields an encoding of ℤ_{n}^{reg} that may prove useful beyond this proof.

Proof. Let U_{n} denote the set of unitary divisors of n. Consider the map

f_{n} : ℤ_{n}^{reg} → {(d, d′) | d ∈ U_{n}, d′ ∈ ℤ_{d}^{∗}} ,

defined by

f_{n}(m) := (\frac{n}{gcd(m, n)}, m mod \frac{n}{gcd(m, n)}) .

We first show that f_{n} is well defined. Let d = n/ gcd(m, n). Then d ∈ U_{n}, and hence gcd(d, m mod d) = gcd(d, m) = gcd(d, m, n) = gcd(d, gcd(m, n)) = gcd(d, n/d) = 1, which implies m mod d ∈ ℤ_{d}^{∗}. To apply the bijection principle, we show that f_{n} is bijective.

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} mod n/d = m_{2} mod n/d, which means that m_{1} ≡ m_{2} (mod n/d). From gcd(m_{1}, n) = d we can write m_{1} = dm′_{1}, m_{2} = dm′_{2}, and n = dn′ with gcd(m′_{1}, n′) = gcd(m′_{2}, n′) = 1. Therefore, m_{1} − m_{2} = d(m′_{1} − m′_{2}), so d | m_{1} − m_{2}, which gives m_{1} ≡ m_{2} (mod d). Since d and n/d are coprime (because d |^{∗}n), combining the congruences m_{1} ≡ m_{2} (mod d) and m_{1} ≡ m_{2} (mod n/d) gives m_{1} ≡ m_{2} (mod n), and hence m_{1} = m_{2}.

Surjectivity. Let d ∈ U_{n} and d′ ∈ ℤ_{d}^{∗}. We define m as

m = \frac{n}{d}((d′j) mod d),  (3)

where j is an inverse of n/d modulo d. We claim the following:

(i) m ∈ ℤ_{n}^{reg} ;

(ii) f_{n}(m) = (d, d′).

Since n/d divides both m and n, and since gcd(d′, d) = 1 and gcd(j, d) = 1, we have

gcd(m, n) = \frac{n}{d} gcd ((d′j) mod d, d) = \frac{n}{d} gcd (d′j, d) = \frac{n}{d} gcd (j, d) = \frac{n}{d}.  (4)

Hence gcd(m, n) |^{∗}n, and by Proposition 3, m ∈ ℤ_{n}^{reg}, as claimed in (i). For part (ii), we note that d = n/ gcd(m, n) follows from (4), and d′ = m mod d follows from (3), since j is an inverse of n/d modulo d. Thus, (i) and (ii) are shown, and the proof is complete.

To illustrate the proof, we list the assignments m ↦ f_{20}(m) for m ∈ ℤ_{20}^{reg}:

0 ↦ (1, 0), 4 ↦ (5, 4), 8 ↦ (5, 3), 12 ↦ (5, 2), 16 ↦ (5, 1),
1 ↦ (20, 1), 5 ↦ (4, 1), 9 ↦ (20, 9), 13 ↦ (20, 13), 17 ↦ (20, 17),
3 ↦ (20, 3), 7 ↦ (20, 7), 11 ↦ (20, 11), 15 ↦ (4, 3), 19 ↦ (20, 19).

Remark 4. In view of (3), the inverse of f_{n} takes the form f_{n}^{−1}(d, d′) = \frac{n}{d}(((n/d mod d)^{−1}d′) mod d) for every d ∈ U_{n} and d′ ∈ ℤ_{d}^{∗}. Remark 5. The proof can be restated by defining f_{n}(m) := (gcd(m, n), m mod n/ gcd(m, n)), which maps from ℤ_{n}^{reg} to {(d, d′) | d ∈ U_{n}, d′ ∈ ℤ_{n/d}^{∗}}. In this setting, f_{n}^{−1}(d, d′) = d(((d mod (n/d))^{−1}d′) mod (n/d)).

5 Proof by reduced fractions

Our third proof is inspired Gauss’s formula n = ∑_{d|n} φ(d), as reproduced in the textbook by Graham, Knuth, and Patashnik [4, pp. 134–135]. The key idea is to establish a bijection between ℤ_{n}^{reg} and the set of reduced fractions of the form k/d, where d |^{∗}n and k < d.

Proof. Consider the fractions m/n with m ∈ ℤ_{n}^{reg}. Reducing these fractions to lowest terms yields fractions of the form

k/d = (m/ gcd(m, n))/(n/ gcd(m, n)).

By Proposition 3, m is regular modulo n if and only if gcd(m, n) |^{∗}n, or equivalently, if and only if n/ gcd(m, n) |^{∗}n. Hence, the denominators of these reduced fractions are precisely the unitary divisors d of n. Each reduced fraction k/d with d |^{∗}n and k < d arises in this way by reducing (kn/d)/n to lowest terms. To complete the argument, we show that kn/d ∈ ℤ_{n}^{reg}. Because k and d, as well as d and n/d, are coprime,

gcd(kn/d, n) = gcd(k(n/d), d(n/d)) = n/d |^{∗}n.

Hence, by Proposition 3, kn/d ∈ ℤ_{n}^{reg}. Thus, the ϱ(n) reduced fractions can be grouped according to their denominator d |^{∗}n, with φ(d) reduced fractions for each denominator d.

To illustrate the proof, consider the ϱ(20) fractions m/20 for m ∈ ℤ_{20}^{reg}:

\frac{0}{20} , \frac{1}{20} , \frac{3}{20} , \frac{4}{20} , \frac{5}{20} , \frac{7}{20} , \frac{8}{20} , \frac{9}{20} , \frac{11}{20} , \frac{12}{20} , \frac{13}{20} , \frac{15}{20} , \frac{16}{20} , \frac{17}{20} , \frac{19}{20} .

Grouping the reduced fractions by their denominators yields

\frac{0}{1} , \frac{1}{4} , \frac{3}{4} , \frac{1}{5} , \frac{2}{5} , \frac{3}{5} , \frac{4}{5} , \frac{1}{20} , \frac{3}{20} , \frac{7}{20} , \frac{9}{20} , \frac{11}{20} , \frac{13}{20} , \frac{17}{20} , \frac{19}{20} ,

with φ(1) = 1 fraction having denominator 1, φ(4) = 2 fractions having denominator 4, φ(5) = 4 fractions having denominator 5, and φ(20) = 8 fractions having denominator 20. Hence ϱ(20) = 1 + 2 + 4 + 8 = 15. Remark 6. There is an obvious connection with the proof in Section 4: a fraction a/b appears in the list of reduced fractions if and only if f_{n}(m) = (b, a) for some m ∈ ℤ_{n}^{reg}.

6 Proof by inclusion-exclusion

Our final proof of (1) is based on a combined application of the inclusion-exclusion principle, the bijection principle, and the multiplicativity of Euler’s totient function φ(n).

Proof. For every integer m ≥ 0 and every prime p, let ν_{p}(m) denote the multiplicity of p in the prime factorization of m. For every m ∈ ℤ_{n}, we have m ∈ ℤ_{n}^{reg} if and only if ν_{p}(m) = 0 or ν_{p}(m) ≥ ν_{p}(n) for each prime divisor p of n, as follows from Proposition 3. Let P (n) denote the set of prime divisors of n, and for each p ∈ P (n), define

A_{p} = {m ∈ ℤ_{n} | 0 < ν_{p}(m) < ν_{p}(n)} .

Then by the inclusion-exclusion principle,

ϱ(n) = | ⋂_{p∈P (n)} \overline{A_{p}}| = ∑_{I⊆P (n)}(−1)^{|I|} |⋂_{i∈I} A_{i}| .  (5)

In this formula, m ∈ ⋂_{i∈I} A_{i} if and only if m = k ∏_{i∈I} i for some k ≤ \frac{n}{∏_{i∈I} i} such that j^{ν_{j}(n)−1} ∤ k for each j ∈ I; that is, if and only if k ∈ ⋂_{j∈I} \overline{B_{j}}, where

B_{j} = \{1 ≤ k ≤ \frac{n}{∏_{i∈I} i} | j^{ν_{j}(n)−1} | k\} (j ∈ I).

Clearly, m ↦ \frac{m}{∏_{i∈I} i} defines a bijection from ⋂_{i∈I} A_{i} to ⋂_{j∈I} \overline{B_{j}}. Therefore, by the bijection principle and another application of the inclusion-exclusion principle, we have

|⋂_{i∈I} A_{i}| = ∑_{J⊆I}(−1)^{|J|} |⋂_{j∈J} B_{j}| = ∑_{J⊆I}(−1)^{|J|} \frac{n}{∏_{i∈I} i ∏_{j∈J} j^{ν_{j}(n)−1}} .  (6)

Combining (5) and (6) and then changing the order of summation, we obtain

ϱ(n) = ∑_{I⊆P (n)} ∑_{J⊆I}(−1)^{|I|+|J|} \frac{n}{∏_{i∈I\J} i ∏_{j∈J} j^{ν_{j}(n)}} = ∑_{J⊆P (n)} ∏_{j∈J} \frac{n}{j^{ν_{j}(n)}} ∑_{I⊇J}(−1)^{|I|+|J|} ∏_{i∈I\J} \frac{1}{i}.

Replacing J by its complement in P (n), and factoring the inner sum, it follows that

ϱ(n) = ∑_{J⊆P (n)} ∏_{j∈J} j^{ν_{j}(n)} ∑_{I⊆J}(−1)^{|I|} ∏_{i∈I} \frac{1}{i} = ∑_{J⊆P (n)} ∏_{j∈J} j^{ν_{j}(n)} (1 − \frac{1}{j}) .

Using Euler’s totient function and its multiplicativity, we obtain

ϱ(n) = ∑_{J⊆P (n)} ∏_{j∈J} φ(j^{ν_{j}(n)}) = ∑_{J⊆P (n)} φ (∏_{j∈J} j^{ν_{j}(n)}) .

We finally observe that the last sum ranges over all positive divisors d = ∏_{j∈J} j^{ν_{j}(n)} of n that are coprime to n/d, i.e., over all unitary divisors d of n, thus proving (1).

7 Significance for cryptography

The authors [3] encountered regular integers modulo n while developing a generalization of the RSA scheme [7] to arbitrary multi-prime, multi-power moduli. For such a generalized modulus n = p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}} with distinct primes p_{1}, …, p_{r} and exponents e_{1}, …, e_{r} ∈ ℕ, the public key (n, e) and the private key (n, d) are established in the same way as in the classical RSA scheme: choose 1 < e < φ(n) such that gcd(e, φ(n)) = 1, and compute 1 < d < φ(n) such that ed ≡ 1 (mod φ(n)). As in classical RSA, a message m ∈ ℤ_{n} is encrypted by raising m to the e-th power modulo n and decrypted by raising m to the d-th power modulo n.

A key observation, proved by the present authors [3], is that decryption reverses encryption if and only if the message is regular modulo n. Consequently, by (1), the probability of correct decryption of a random message from ℤ_{n} is given by

\frac{ϱ(n)}{n} = \frac{1}{n} ∑_{d |^{∗}n} φ(d),

which illustrates the significance of the sequence \underline{A055653} and Morgado’s formula (1) in the context of cryptography. As further shown by the present authors [3],

\frac{ϱ(n)}{n} ≥ 1 − \frac{r}{2^{k−1}} ,

where n = p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}} with distinct k-bit primes p_{1}, …, p_{r}. Therefore, even for today’s standard choices of k, such as k = 1024, almost all messages in ℤ_{n} are decrypted correctly, and the restriction to regular messages is negligible. Although this conclusion is satisfactory from a practical point of view, there remains potential for sharper bounds on the correctness probability. Asymptotic results on ϱ(n) and related quantities such as ϱ(n)/φ(n), as obtained by Apostol and Petrescu [2] and by Tóth [8], may prove crucial in this regard.

References

[1] O. Alkam and E. A. Osba, On the regular elements in ℤ_{n}, Turkish J. Math. 32 (2008), 31–39.

[2] B. Apostol and L. Petrescu, Extremal orders of certain functions associated with regular integers (mod n), J. Integer Sequences 16 (2013), Article 13.7.5.

[3] K. Dohmen and M. Lange-Geisler, General multi-prime multi-power RSA—a generalization of RSA and CRT-RSA to regular integers modulo n, preprint, Cryptology ePrint Archive 2025/1157, 2025. Available at https://eprint.iacr.org/2025/1157.

[4] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd edition, 1994.

[5] J. Morgado, Inteiros regulares módulo n, Gazeta de Matematica (Lisboa) 33 (1972), 1–5.

[6] N. J. A. Sloane and The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2026. Available at https://oeis.org.

[7] R. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM 21 (1978), 120–126.

[8] L. Tóth, Regular integers modulo n, Ann. Univ. Sci. Budapest. Sect. Comput. 29 (2008), 263–275.

2020 Mathematics Subject Classification: Primary 11B83; Secondary 05A15, 11A25, 11T71. Keywords: regular integer modulo n, unitary divisor, totient function, RSA cryptosystem.

(Concerned with sequence \underline{A055653}.)

Received October 9 2025; revised versions received March 13 2026; March 18 2026. Published in Journal of Integer Sequences, April 21 2026.

Return to Journal of Integer Sequences home page.