如何构造满足乘性的双射函数$f:3\mathbb{N}+1\to4\mathbb{N}+1$？

Great question! Let's walk through this step by step—we'll use basic number theory and properties of multiplicative monoids to build the function you need.

First, let's align on the sets we're working with:

• $3\mathbb{N}+1$ is all positive integers congruent to 1 mod 3: ${1,4,7,10,13,25,...}$. Under multiplication, this is a commutative monoid (closed under multiplication, has an identity element 1), and every element factors uniquely into "irreducible" elements (things you can't split into two smaller elements of the set).
• Similarly, $4\mathbb{N}+1$ is all positive integers congruent to 1 mod 4: ${1,5,9,13,17,29,...}$, which is also a commutative multiplicative monoid with unique factorization into irreducibles.

Step 1: Identify the "Building Blocks" of Each Set #

The core insight is that both sets are generated by their irreducible elements. Let's define those clearly:

• For $3\mathbb{N}+1$, irreducible elements are:
  • Primes congruent to 1 mod 3 (like 7, 13, 31—these can't be split into smaller elements of the set because their only factors are 1 and themselves)
  • Squares of primes congruent to 2 mod 3 (like $2^2=4$, $5^2=25$, $11^2=121$—their square roots aren't in $3\mathbb{N}+1$, so you can't write them as a product of two non-1 elements from the set)
• For $4\mathbb{N}+1$, irreducible elements are:
  • Primes congruent to 1 mod 4 (like 5,13,17—same logic as above)
  • Squares of primes congruent to 3 mod 4 (like $3^2=9$, $7^2=49$, $11^2=121$—again, square roots aren't in the set, so they can't be split further)

Crucially, both sets of irreducibles are countably infinite (there are infinitely many primes in each congruence class, so their squares are also infinite, and countable overall).

Step 2: Map the Building Blocks Bijectively #

Since both irreducible sets are countably infinite, we can create a bijection between them. For example:

1. List the irreducibles of $3\mathbb{N}+1$ in increasing order: $4,7,13,25,31,49,...$
2. List the irreducibles of $4\mathbb{N}+1$ in increasing order: $5,9,13,17,21,29,...$
3. Pair them one-to-one: map the first element of the first list to the first of the second, second to second, etc.

You can also get more intentional—for example, map every prime ≡1 mod3 to a prime ≡1 mod4 (in sorted order), and every square of a prime ≡2 mod3 to a square of a prime ≡3 mod4 (in sorted order). Either way, just ensure the mapping hits every irreducible in the target set exactly once.

Step 3: Extend the Mapping to the Entire Set #

Now that we have a bijection $g$ between the irreducibles of $3\mathbb{N}+1$ and $4\mathbb{N}+1$, we can extend it to the whole set using unique factorization:

• Take any element $x \in 3\mathbb{N}+1$. Factor it into irreducibles: $x = s_1^{k_1} s_2^{k_2} ... s_n^{k_n}$ (each $s_i$ is irreducible in $3\mathbb{N}+1$, $k_i$ are positive integers)
• Define $f(x) = g(s_1)^{k_1} g(s_2)^{k_2} ... g(s_n)^{k_n}$

Why This Works #

Let's verify the two required properties:

1. Multiplicative Homomorphism: If $x = \prod s_i^{k_i}$ and $y = \prod s_j^{l_j}$, then $xy = \prod s_i^{k_i + l_i}$ (combining like factors). Then $f(xy) = \prod g(s_i)^{k_i + l_i} = \prod g(s_i)^{k_i} * \prod g(s_i)^{l_i} = f(x)f(y)$. It preserves multiplication perfectly.
2. Bijection:
   • Injective: If $f(x)=f(y)$, their factorizations into $4\mathbb{N}+1$ irreducibles are identical (thanks to unique factorization). Since $g$ is a bijection, the original factorizations of $x$ and $y$ must also be identical, so $x=y$.
   • Surjective: Take any $z \in 4\mathbb{N}+1$, factor it into irreducibles: $z = t_1^{m_1} ... t_p^{m_p}$. Since $g$ is a bijection, each $t_i$ maps back to a unique irreducible $s_i$ in $3\mathbb{N}+1$. Then $x = \prod s_i^{m_i}$ is in $3\mathbb{N}+1$, and $f(x)=z$.

Example of a Concrete Construction #

Here's a simple explicit version:

• Map every prime ≡1 mod3 to the next prime ≡1 mod4: $7 \to 5$, $13 \to13$, $31 \to17$, $37 \to29$, etc.
• Map every square of a prime ≡2 mod3 to the next square of a prime ≡3 mod4: $2^2=4 \to3^2=9$, $5^2=25 \to7^2=49$, $11^2=121 \to11^2=121$, etc.

This gives you a fully functional bijective multiplicative function that meets all your requirements.

内容的提问来源于stack exchange，提问作者Vrouvrou