How many maps of Z/NZ preserve multiplication? A counting formula for OEIS sequence A117986

Abstract

Sequence A117986 of the On-Line Encyclopedia of Integer Sequences (OEIS) gives the number N(n) of maps f: Z/nZ → Z/nZ with f(xy) = f(x)f(y) for all x and y. The entry lists 56 terms and no proved formula; its only formula line, added in 2019, says that "apparently" N(p) = p + 1 for every prime p. This paper confirms that remark with a short proof and gives a formula for N(n) for every n. By the Chinese remainder theorem the count splits into local numbers T(pa, qb), the numbers of multiplicative maps g: Z/paZ → Z/qbZ with g(1) = 1, and N(n) = ∏i (1 + ∏j T(qj, qi)), where q1, ..., qr are the prime powers in the factorisation of n. Each local number is a finite sum of counts of solutions of explicit congruences; the prime 2 is treated separately, because the units modulo 2k do not form a cyclic group for k ≥ 3. This gives N(pk) = p2k−2(p − 1) + 2 for odd p, N(2k) = 3·22k−2 + 2 for k ≥ 3, and a closed formula for square-free n. The formula agrees with all 56 published terms and with exhaustive search for every n ≤ 72, and it gives 16 new terms. The maps between prime-power monoids had already been described in a 2026 doctoral thesis by J. Atalaye (Stellenbosch University), whose explicit forms imply the local counts in many cases; for Z/8Z, however, one of its corollaries implies 65 maps with g(1) = 1, while a direct enumeration gives 49. The contribution of this paper is an element-by-element count of these maps for every pair of prime powers, checked against direct counts, the resulting formula for N(n), and its connection to A117986.

Keywords: multiplicative map, residue ring, monoid homomorphism, Chinese remainder theorem, integer sequence, OEIS A117986

Список литературы

1. Sequence A117986: Number of functions f:[n]->[n] such that f[(x*y) mod n]=[f(x)*f(y)] mod n for all x,y in [n] // The On-Line Encyclopedia of Integer Sequences. OEIS Foundation Inc. URL: https://oeis.org/A117986 (accessed: 24.10.2026).
2. Atalaye J. Exploring the multiplicative structure of Z/nZ: PhD dissertation. Stellenbosch: Stellenbosch University, 2026. 120 p. URL: https://scholar.sun.ac.za/server/api/core/bitstreams/34ac3e49-a014-49c7-b376-84aa27df66cc/content (accessed: 24.10.2026).
3. Atalaye J., Baker L., Marques S. On the automorphism group of the monoid of the integers modulo a prime power // arXiv. 2024. arXiv:2408.06278. URL: https://arxiv.org/abs/2408.06278 (accessed: 24.10.2026).
4. Atalaye J., Baker L., Marques S. Automorphism groups of direct products of multiplicative monoids of certain rings // arXiv. 2026. arXiv:2605.06119. URL: https://arxiv.org/abs/2605.06119 (accessed: 24.10.2026).
5. Ireland K., Rosen M. A Classical Introduction to Modern Number Theory. 2nd ed. New York: Springer, 1990. (Graduate Texts in Mathematics; Vol. 84). DOI: 10.1007/978-1-4757-2103-4.

Как цитировать

Bilim-Innovation Lyceum No. 1, Karagandy, Kazakhstan How many maps of Z/NZ preserve multiplication? A counting formula for OEIS sequence A117986 // Central Asian Scientific Journal. – 2026. – No. 4(32), Vol. 2. – Pp. 94–100. – DOI: 10.5281/zenodo.23772145.