# How to find a such function $f:3\mathbb{N}+1\to 4\mathbb{N}+1$

How to find a bijective function $f: 3\mathbb{N}+1\to 4\mathbb{N}+1$ such that $$f(xy)=f(x)f(y),\forall x,y\in 3N+1$$

If i let $x,y\in 3\mathbb{N}+1$ then there exists $n,m\in \mathbb{N}$ such that $x=3n+1,y=3m+1$

but I have no idea how I can find a such $f$, Is there a method please ?

• Is $1 \in 3\mathbb{N} + 1$ in your definition?
– orlp
Commented Feb 16, 2018 at 21:11
• Yes @orlp we suppoe that $N=\{0,1,...\}$ Commented Feb 16, 2018 at 21:13
• @keoxkeox Is not a bijection for the full domain.
– orlp
Commented Feb 16, 2018 at 21:15
• Hint: the prime factorization of an element of $3 \mathbb{N} + 1$ is some number of primes $\equiv 1 \pmod{3}$, and an even number of primes $\equiv 2 \pmod{3}$. Similarly, the prime factorization of an element of $4 \mathbb{N} + 1$ is some number of primes $\equiv 1 \pmod{4}$, and an even number of primes $\equiv 3 \pmod{4}$. Commented Feb 16, 2018 at 21:55

Note $P_{a,b}$ the set of primes congruent to $a$ mod $b$.

Since all those sets are countably infinite, you have bijections $f_1 : P_{1,4} \to P_{1,3}$ and $f_2 : P_{3,4} \to P_{2,3}$.

The free commutative monoid generated by $P_{1,4} \cup P_{3,4}$ is the set of odd numbers, and the one generated by $P_{1,3} \cup P_{2,3}$ is the set of integers coprime with $3$, so those bijections induce a monoid isomorphism $f$ from the set of odd integers to the set of numbers coprime with $3$.

Then the restriction of $f$ to $1+4\Bbb N$ gives a monoid isomorphism to $1+3\Bbb N$.
(a number is in $1+4\Bbb N$ when it has an even number of primes from $P_{3,4}$ (counted with multiplicity), and likewise a number is in $1+3\Bbb N$ if it has an even number of primes form $P_{2,3}$).

Something like that should work between $1+a\Bbb N$ and $1+b\Bbb N$ whenever the groups $(\Bbb Z/a\Bbb Z)^*$ and $(\Bbb Z/b\Bbb Z)^*$ are isomorphic

• How do you get an isomorphism? Commented Feb 16, 2018 at 22:02
• You mean all the sets $P_{a,b}$ where $\gcd(a,b)=1$, right? Commented Feb 16, 2018 at 22:03
• somehow I am only seeing now your comment from 20 minutes ago ... ._. i guess you wrote it while i was writing this Commented Feb 16, 2018 at 22:16
• What can be the form if the function an example please $f(x)=$? Commented Feb 16, 2018 at 22:18
• @mercio please can you answer me , can you give me an example about $f$ ? Commented Feb 17, 2018 at 18:47

I think a constructive approach like this might work:

First look at the integers of the form $3k+1$: They are $1,4,7,10,13,16, 19, 22, 25, 28, \dots$. Factor each of these, as far as possible, into smaller elements of $3\mathbb Z+1$. So $1=1,4=4,7=7,10=10,13=13,16=4^2, 19=19, 22=22, 25=25, 28=4\cdot7, \dots$. Enumerate the “prime-ish” elements of $3\mathbb Z+1$ — those that don’t factor into smaller elements: $a_1=1, a_2=4, a_3=7, a_4=10, a_5=13, a_6=19, \dots$.

Do the same thing for $4\mathbb Z+1$: $b_1=1, b_2=5, b_3=9,\dots$.

Let $f(a_i)=b_i$ and extend the definition of $f$ to all of $3\mathbb Z+1$ by requiring $f$ to be multiplicative.

I haven’t thought through whether there can be non-unique factorizations into the “prime-ish” numbers, so there are still details to work out or show.