1

Let $p$ be a prime and let $a$ and $d$ be integers such that $0\leq a<d$. Each $x\in\mathbb{Z}_{p^d}$ can be written uniquely as $$ x=j+k\,p^a $$ for some integers $0\leq j < p^a$ and $0\leq k < p^{d-a}$.

Let $b$ and $c$ be nonnegative integers such that $a+b\leq d$ and $c<p^b$. Prove that $$ j+k\, p^a \mapsto j+k p^a + ck p^{d-b} \, (\text{mod }p^d) $$ is a permutation of $\mathbb{Z}_{p^d}\rightarrow \mathbb{Z}_{p^d}$.

I need to prove that the mapping is injective, so suppose $j,j',k,k'$ are integers such that $$ j+k p^a + ck p^{d-b} \equiv j'+k' p^a + ck' p^{d-b}\, (\text{mod }p^d). $$ That is, $$ j-j'\equiv (k'-k) (p^a + cp^{d-b})\, (\text{mod }p^d). $$ How does one know that this can happen if and only if $j=j'$ and $k=k'$?

a882345
  • 13

1 Answers1

0

First note that $p^a\mid p^{ d-b} $ thus by reducing modulo $p^a$ we get $j-j'\equiv 0\pmod{p^a}$ that $j\equiv j'\pmod {p^a} $ and since $\Bbb N\ni j,j'<p^a$ we get $ j=j'$. Consequently, $(k'-k)(p^a+cp^{d-b})\equiv 0\pmod{p^d}$; dividing by $p^a$ we get $$(k'-k)(1+cp^{d-a-b})\equiv 0\pmod {p^{d-a}}$$ If $d>a+b$ then $p\nmid(1+cp^{d-a-b})$, hence $k'-k\equiv 0\pmod{p^{d-a}}$ from which $k=k'$.

If $d=a+b$ we have $(k'-k)(1+c)\equiv 0\pmod {p^b}$ and for $c\not\equiv -1\pmod p$ you get again $k=k'$.

It remains the case $d=a+b$ and $c\equiv -1\pmod p$ for which the statement is false. Take, for example, $d=2$, $a=b=c=1$ and $p=2$. Then your function satisfy: $$0=0+2\cdot 0\mapsto 0+2\cdot 0+2\cdot 0=0$$ $$2=0+2\cdot 1\mapsto 0+2\cdot 1+2\cdot 1\equiv 0\pmod 4$$ hence it's no injective.

Fabio Lucchini
  • 16,054