2

Let $X = \{1,2,\dots,pq-1\}$ where $p,q$ are distinct large primes and suppose neither $p-1$ nor $q-1$ is divisible by 3.

$$ P(x)=x^{3} \ (\text{mod} \ pq). $$ Show mapping $P: X \to X$ is a bijection where $x \in X$.

I had verified results by taking some values of $p,q$.But unable to infer due to randomness of function $P(x)$.

qualcuno
  • 17,121
ABHISHEK YADAV
  • 21

1 Answers1

1

Note that by the Chinese Remainder Theorem, the map $$\mathbf{Z} / pq \mathbf{Z} \to\mathbf{Z} / p \mathbf{Z} \times \mathbf{Z} / q \mathbf{Z}, \; x \mapsto (x \mod p, \; x \mod q)$$ is an isomorphism. Now consider the map $$f: (\mathbf{Z} / p \mathbf{Z})^\times \times (\mathbf{Z} / q \mathbf{Z})^\times \to (\mathbf{Z} / p \mathbf{Z})^\times \times (\mathbf{Z} / q \mathbf{Z})^\times, \; (x, y) \mapsto (x^3, y^3).$$

Consider the group-homomorphism $$(\mathbf{Z} / p \mathbf{Z})^\times \to (\mathbf{Z} / p \mathbf{Z})^\times, x \mapsto x^3.$$

As shown in this answer: Solve $x^3 \equiv 1 \pmod p$ for $x$, the homomorphism is injective for $p - 1$ not divisible by $3$ (use quadratic reciprocity). This, of course, works for $q$ as well.

This readily implies that $f$ is injective. Since $P$ is a map $X \to X$ and $X$ is finite, any injective function is surjective.

It seems, however, like there should be an easier answer...

Steven
  • 4,543