# Is there other homomorphisms from $\mathbb{Z}_q^*$ to $\mathbb{Z}_{pq}^*$?

For given two distinct primes p and q, is there other homomorphisms from the multiplicative group $\mathbb{Z}_q^*$ to the multiplicative group $\mathbb{Z}_{pq}^*$, except the following two maps:

1. $h(r\bmod q)=1$ for all $r\in\mathbb{Z}_q^*$;
2. $h(r\bmod q)=r^{p-1} \bmod pq$ for all $r\in\mathbb{Z}_q^*$.
-
Have you tried to brute force this for example in the case $q=3$ and $p=5$? Please list the outcomes of some such attempts in your question body. Others will then be convinced that you are working on this yourself, and may actually benefit from being given pointers. Hint: what common divisors might $p-1$ and $q-1$ have? – Jyrki Lahtonen Jun 17 '13 at 10:43
And another hint for working out the case $q=3$. We have $\mathbb{Z}_3^*=\{\overline{1},\overline{2}\}$. We have no choice for the image of $\overline{1}$, why? So the game is all about choices for the image of $\overline{2}$. What constraints do we have in selecting that image? Hint: $2^2\equiv1\pmod3$. – Jyrki Lahtonen Jun 17 '13 at 10:45
Is there a systematical method for list all homomorphisms between two small groups, say via Maple or other tools? – Pigmann Jun 17 '13 at 15:38
Writing down the homomorphisms explicitly may sometimes require that we have an explicit generator for the groups $\mathbb{Z}_p^*$ and $\mathbb{Z}_q^*$. Proving that they exist is easy, but exhibiting one less so. How large are your $p$ and $q$ typically? – Jyrki Lahtonen Jun 17 '13 at 15:48
Okay. We can explicitly get the required generators by using Maple command g_p:=primroot(p) and g_q:=primroot(q). My true intention is to design a non-trivial homomorphism from $\mathbb{Z}_q^*$ to $\mathbb{Z}_{pq}^*$ in the sense of excluding the given two cases (see above). The first case is trivial since it maps all elements in $\mathbb{Z}_q^*$ to a constant 1. Although the second map maps all elements in $\mathbb{Z}_q^*$ to different images in $\mathbb{Z}_{pq}^*$, these images are congruent to 1 mod p, since each of them takes the form h:=x^{p-1} mod n. This implies that h mod p = 1. – Pigmann Jun 18 '13 at 2:48

Assuming that we know a generator $g_1$ (resp. $g_2$) for $\mathbb{Z}_p^*$ (resp. $\mathbb{Z}_p^*$) we can describe all the homomorphisms as follows. By the Chinese Remainder Theorem we know that $$\mathbb{Z}_p^*\times\mathbb{Z}_q^*\cong\mathbb{Z}_{pq}^*.$$ Let $d=\gcd(p-1,q-1)$, and let $f:\mathbb{Z}_p^*\to\mathbb{Z}_p^*\times\mathbb{Z}_q^*$ be an arbitrary homomorphism. If we know the image $f(g_1)$, we have fully described $f$, as then $f(g_1^i)=f(g_1)^i$ for all integers $i$, and all the elements of $\mathbb{Z}_p^*$ are of the form $g_1^i$ for some integer $i$.
The constraint is that $f$ has to respect the relation $g_1^{p-1}=1$, so we need to have $f(g_1)^{p-1}=(1,1)$. If $f(g_1)=(a,b)$, this translates to the requirement $b^{p-1}=1$, as the other equation $a^{p-1}=1$ is automatic. Here $b=g_2^j$ for some $j, 0\le j<q-1,$ so $b^{p-1}=1$ holds, if and only if $(q-1)\mid j(p-1)$. Here the help from factor $p-1$ is exactly the gcd, so this holds, iff $j$ is divisible by $(q-1)/d$. So we have exactly $d$ choices for $j$, namely $j=k(q-1)/d$ for some $k$ in the range $0\le k<d$. Let us write $z=g_2^{(q-1)/d}$. If $j=k(q-1)/d$, we then have $$b=(g_2)^{k(q-1)/d}=z^k.$$ Putting this altogether we get that $$f(g_1^i)=(a^i,z^{ki}).$$ There are $p-1$ choices for $a$ and $d$ choices for $k$, so altogether we have $d(p-1)$ distinct homomorphisms.
If you want to take into account the isomoprhism given by CRT, then you would need to find the images of the pairs $(g_1,1)$ and $(1,z)$ in $\mathbb{Z}_{pq}^*$. Alternatively you can just try and find the $d(p-1)$ elements $w=w_j, j=1,2,\ldots,d(p-1),$ of $\mathbb{Z}_{pq}^*$ that satisfy the equation $w^{p-1}=1$. Then you get all the homomorphisms from the recipe $$f(g_1^i)=w_j^i.$$
Almost done. I believe $\mathbb{Z}_p^*\times\mathbb{Z}_q^*\cong\mathbb{Z}_{pq}^*$. But what can I do if I want to explicitly enumerate all these isomorphisms? Any suggestion is appreciated. – Pigmann Jun 18 '13 at 17:06
What if I want to perform this homomorphic transformation blindly, i.e., to work out $f(g_1^i)=(a^i,z^{ki})$ without calculating $i$ at first? – Pigmann Jun 19 '13 at 2:55