We present four combinatorial proofs of Morgado's formula for the number ϱ(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² x ≡ m (mod n) has a solution x ∈ 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.