$m+1$ generates the kernel of $Z_n^\times\to Z_m^\times$ where $m\mid n$ with the same prime factors

Question

Suppose $m\mid n$. Using the First Isomorphism Theorem with respect to the homomorphism $$\begin{array}{rccc}f:&\mathbb{Z}_n^\times&\to&\mathbb{Z}_m^\times \\&x&\mapsto &x\bmod m \end{array}$$ we know $\mathbb{Z}_n^\times/K_m\cong\mathbb{Z}_m^\times$, where $K_m=\{x\in\mathbb{Z}_n^\times:x\equiv1\bmod m\}\subseteq\mathbb{Z}_n^\times$.

Suppose $m$ and $n$ also share the same prime factors. We can show $|K_m|=\phi(n)/\phi(m)=n/m$. I would like to prove that $K_m=\left<m+1\right>$.

Clearly $\left<m+1\right>\subseteq K_m$, but I don't know how to begin proving in the other direction. I only know to look at the coefficients of powers of $m+1$, and this isn't helping. In particular, expanding $(m+1)^t$ we get $$ (m^t+\dots+tm)+1 $$ If $t=n/m$ then $n$ divides the term in parentheses and we get $(1\bmod n)$, but it could be that $n$ divides the sum in parentheses without dividing $tm$, or at least it seems that's a possibility...

Answer 1

Not true if $m=2$ and $n=8$

$\Bbb Z_8^\times=\{\bar1, \bar3,\bar5,\bar7\}$.
$\Bbb Z_2^\times=\{\bar1\}$.
$T_m=\Bbb Z_8^\times$. However, in $\Bbb Z_8^\times$, $\langle\overline{m+1}\rangle=\langle\overline{2+1}\rangle=\langle\bar3\rangle=\{\bar1, \bar3\}$ since $\bar3^3=\bar9=\bar1$. $$|T_m|=4\not=2=\langle\overline{m+1}\rangle$$.

Answer 2

Here's a proof for the special case that $n=2^s$ is a power of 2 and $m=2^t$ with $2\leq t\leq s$. Since $\left<m+1\right>$ is a subgroup of $K_m$, we know it has order dividing $n/m=2^{s-t}$. We will now show it has order at least $2^{s-t}$ by showing $(m+1)^{2^{s-t-1}} \bmod n \neq 1$.

Power $2^r$ of $(m+1)$ for $r\geq0$ takes the form $2^{t+r}d+1$ for some odd $d$. As the base case, $m+1$ takes this form with $r=0$ and $d=1$. For induction, we square $(2^{t+r}d+1)$ to get power $2^{r+1}$ of $(m+1)$ $$ (2^{t+r}d+1)^2 = 2^{2t+2r}d^2+2^{t+r+1}d+1 = 2^{t+(r+1)}(2^{t+r-1}d^2+d)+1 $$ where $2^{t+r-1}d^2+d$ is odd since $d$ and $d^2$ are odd while $2^{t+r-1}d^2$ is even (note $t+r-1>0$ since $t>1$).

Thus $(m+1)^{2^{s-t-1}}$ takes the form $2^{s-1}d+1$ so with $d$ odd $$ 2^{s-1}d+1\bmod 2^s\neq 1 $$

Answer 3

To generalize the case of $n$ a power of 2, here's a proof for the special case that $n=p^s$ is a prime power and $m=p^t$ with $2\leq t\leq s$. Since $\left<m+1\right>$ is a subgroup of $K_m$, we know it has order dividing $n/m=p^{s-t}$. We will now show it has order at least $p^{s-t}$ by showing $(m+1)^{p^{s-t-1}} \bmod n \neq 1$.

Power $p^r$ of $(m+1)$ for $r\geq0$ takes the form $p^{t+r}d+1$ for some $d$ with $(d,p)=1$. As the base case, $m+1$ takes this form with $r=0$ and $d=1$. For induction, we raise $(p^{t+r}d+1)$ to $p$ to get power $p^{r+1}$ of $(m+1)$ as $$ (p^{t+r}d+1)^p = \sum_{k=0}^p {p \choose k}(p^{t+r}d)^k \\ = 1 + pp^{t+r}d + \sum_{k=2}^p {p \choose k} d^k p^{t+r+1} p^{(k-1)(t+r)-1} \\ = 1 + p^{t+(r+1)}\left(d + \sum_{k=2}^p {p \choose k} d^k p^{(k-1)(t+r)-1}\right) $$ where $(d',p)=1$ for $$ d' = d + \sum_{k=2}^p {p \choose k} d^k p^{(k-1)(r+t)-1} $$ Each term of $d'-d$ is divisible by $p$ since $t\geq2$ by assumption. On the other, hand $(d,p)=1$, and therefore $(d',p)=1$.

Thus $(m+1)^{p^{s-t-1}}$ takes the form $p^{s-1}d+1$ so with $(d,p)=1$ $$ p^{s-1}d+1\bmod p^s\neq 1 $$

Answer 4

(I've posted three proofs in increasing generality. This is the third and final.)

To generalize the case that $n$ is a prime power, suppose $n=\prod_i p_i^{s_i}$ and $m=\prod_i p_i^{t_i}$ with the conditions:

1. If $p_i=2$, then $s_i\geq t_i\geq2$. This is our additional assumption not granted in the question. But given the counter examples where $m$ has prime factor 2 with multiplicity only $1$, it is the weakest assumption for which the proposition holds.
2. If $p_i\neq2$, then $s_i\geq t_i\geq1$.

Since $\left<m+1\right>$ is a subgroup of $K_m$ we know it has order dividing $n/m=\prod_i p_i^{s_i-t_i}$. We will now show it has order at least $\prod_i p_i^{s_i-t_i}$ by showing that raising $(m+1)$ to any of the powers $\prod_i p_i^{r_i}$ for $r_i=s_i-t_i$ or $r_i=s_i-t_i-1$ and taking the result modulo $n$ results in a residue not equal to $1$, except for the case that $\forall i, r_i=s_i-t_i$ as we'd expect.

We will prove that $\prod_i p_i^{r_i}$ of $(m+1)$ for $r_i\geq0$ takes the form $$ 1+d\prod_i p_i^{t_i+r_i} $$ with $(d,\prod_i p_i)=1$. As the base case for induction, $(m+1)$ takes this form with $\forall i, r_i=0$ and $d=1$. For induction, we raise $(1+d\prod_i p_i^{t_i+r_i})$ to the power $p_j$ to get power $p_j^{t_j+(r_j+1)}\prod_{i\neq j}p_i^{t_i+r_i}$ of $(m+1)$ demonstrating it indeed takes the form $$ 1+d'\left(p_j^{t_j+(r_j+1)}\prod_{i\neq j}p_i^{t_i+r_i}\right) $$

We expand as follows $$ \left(1+d\prod_i p_i^{t_i+r_i}\right)^{p_j} \\ = \sum_{k=0}^{p_j} {p_j \choose k}\left(d\prod_i p_i^{t_i+r_i}\right)^k \\ = 1 + p_j\left(d p_j^{t_j+r_j}\prod_{i\neq j} p_i^{t_i+r_i}\right) + \sum_{k=2}^{p_j} {p_j \choose k}d^k p_j^{t_j+r_j+1}\left(p_j^{(k-1)(t_j+r_j)-1}\prod_{i\neq j} p_i^{k(t_i+r_i)}\right) \\ = 1 + p_j^{t_j+(r_j+1)}\left(d \prod_{i\neq j} p_i^{t_i+r_i} + \sum_{k=2}^{p_j} {p_j \choose k}d^k \left(p_j^{(k-1)(t_j+r_j)-1}\prod_{i\neq j} p_i^{t_i+r_i}\prod_{i\neq j} p_i^{(k-1)(t_i+r_i)}\right)\right) \\ = 1 + p_j^{t_j+(r_j+1)}\prod_{i\neq j} p_i^{t_i+r_i} \left(d + \sum_{k=2}^{p_j} {p_j \choose k}d^k p_j^{(k-1)(t_j+r_j)-1}\prod_{i\neq j} p_i^{(k-1)(t_i+r_i)}\right) \\ = 1 + d'\left(p_j^{t_j+(r_j+1)}\prod_{i\neq j} p_i^{t_i+r_i}\right) $$ for $$ d' = d + \sum_{k=2}^{p_j} {p_j \choose k}d^k p_j^{(k-1)(t_j+r_j)-1}\prod_{i\neq j} p_i^{(k-1)(t_i+r_i)} $$ Now we must argue that $(d',\prod_i p_i)=1$. Write $d'=d+T$ for $T$ the second term of $d'$. Recall that by induction $d$ is coprime with $\prod_i p_i$. On the other hand, $T$ is a sum consisting of $p_j-1$ terms, and each term is divisible by $p_i$ for $i\neq j$ because $(k-1)(t_i+r_i)\geq1$ as $k\geq2$, $t_i\geq1$, and $r_i\geq0$. We also argue each term of $T$ is divisible by $p_j$. First note that this holds for all terms $k\geq3$. For the case $k=2$, note the term is $$ \frac{p_j(p_j-1)}{2} d^2 p_j^{t_j+r_j-1} \prod_{i\neq j} p_i^{(t_i+r_i)} $$ and we split analysis by condition on $p_j$.

1. Suppose $p_j=2$. Then $t_j+r_j-1\geq1$ as $t_j\geq2$ by assumption, thus the term is divisible by $p_j$.
2. Suppose $p_j\neq2$. Then $p_j$ is odd, so $(p_j-1)/2$ is a whole number, and thus the binomial coefficient $p_j(p_j-1)/2$ is divisible by $p_j$.

Thus for every prime $p_i$ (including $i=j$), $d$ is coprime with $p_i$ while $T$ is divisible by $p_i$. We wish to conclude that $(d',p_i)=1$ for all $i$. Suppose $T=p_iq_i$ with quotient $q_i$, so $d'=d+p_iq_i$. Suppose for sake of contradiction that $d'=Q_ip_i$. Then $p_i(Q_i-q_i)=d$, contradicting $(d,p_i)=1$, and therefore $(d',p_i)=1$. As such, we have $d'$ coprime with $\prod_i p_i$, that is $(d',\prod_i p_i)=1$ as promised.

Therefore any power of $(m+1)$ of the form $\prod_i p_i^{r_i}$ for $r_i=s_i-t_i$ or $r_i=s_i-t_i-1$ results in $$ 1+d\prod_i p_i^{t_i+r_i} $$ In the case that $\forall i, r_i=s_i-t_i$ this reduces to $$ 1+d\prod_i p_i^{s_i} = 1 + dn $$ which has residue $1$ modulo $n$. In all other cases, however, there exists at least one $j$ such that $r_j=s_j-t_j-1$ in which case the expression becomes $$ 1+d p_j^{s_j-1} \prod_{i\neq j} p_i^{t_i+r_i} $$ Now as $p_j^{s_j-1} \prod_{i\neq j} p_i^{t_i+r_i}$ is not divisible by $n$, and $d$ is coprime with $n$, this expression has residue not equal to $1$ modulo $n$.