2

The closest I could find was this archived reddit post. There I think they prove that $Z_n\setminus Z_n^{*}$ can be made isomorphic to $Z_m^{*}$.

Question: Let m|n. ($Z_n^{*} \mod m) = Z_m^{*}$ (as sets, not ring isomorphism or any other stronger requirement)?

The "obvious" inclusion is $(Z_n^* \mod m) \subseteq Z_m^{*}$, because if $k$ is coprime with $n$ then it is also coprime with $m$.

Simple true case: the factors of $n$ are all factors of $m$ then $(Z_n^* \mod m) \supseteq Z_m^{*}$, because if a number is coprime with $m$ then it is coprime with $n$ and the result follows from $Z_n^* \supseteq Z_m^{\ast}$.

General case: the problem is when $n/m$ has factors that are not factors of $m$, because then $Z_n^{*} \supseteq Z_m^{*}$ is false (for interesting cases such factors must be smaller than $m$). However, I could not find a counter example; integers $k>m$ in $Z_n^{*}$ always end up generating the integers $k'\in Z_m\setminus Z_n$ after the $\mod m$ operation. Minimal example: $n=6$ and $m=3$, then $Z_6^{*} = \{1,5\}$ and $Z_3^{*}=\{1,2\}$, $2$ is not directly in $Z_n^*$ but it exists as $5$.

Motivation: explaining the invertible cases of modular exponentiation, I recently claimed that finding all the pairs $(x,x^{-1}) \mod \varphi(n)$, the Euler function, and then taking $\mod \lambda(n)$, the Carmichael function, is the same as finding all the pairs $\mod \lambda(n)$ directly. This should be true because it should fall in the simple case, but I claimed it in general, and now I am stuck.

  • For $m | n$ the map $f: \Bbb{Z}_{n}^\times \to \Bbb{Z}_m^\times, f(a) =a \bmod m$ is a group morphism and it is surjective because $n = rs$ with $p | r\implies p | m$ and $p | s \implies p \nmid m$, for $b \in \Bbb{Z}_m^\times$ take $c \equiv b \bmod r, c\equiv 1 \bmod s$ you'll have $f(c) =b$. – reuns Jun 28 '19 at 17:29
  • @reuns Is $p$ implicitly $\mod m$ or prime? because for $m=6$ and $n=60$ I can always find an integer $p$ not satisfying your implications – dragomang87 Jun 28 '19 at 18:50
  • For $m=6,n=60$ then $r = 12,s=5$ the point is they are coprime and $\gcd(b,m) =1 \implies \gcd(b,r)=1$ – reuns Jun 28 '19 at 20:08

0 Answers0