Permutation polynomial

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Permutation polynomial

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

10618 posts

#1 h Apr 11, 2025, 11:16 AM

Y by

Let $n$ be a positive integer. Prove that $f=x^3+x$ is a permutation polynomial mod $n$ iff $n$ is a power of 3.
Note: we call $f$ a permutation polynomial mod $n$ iff the induced map $f:Z_n\rightarrow Z_n$ is bijective.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

10618 posts

#3 h Apr 11, 2025, 7:19 PM

Y by

I found this problem a few days ago on AOPS, unfortunately it was deleted while I was typing the second half of the solution. Since I liked the problem I reposted it. Here is my solution.
For $n=1$ it is clear, now suppose that $n=3^k,k\ge 1$ and that $x^3+x\equiv y^3+y(n)$ where $x\not\equiv y$ . Then $(x-y)(x^2+xy+y^2+1)\equiv 0(n)$ . If $x\equiv y(3)$ then the second factor is coprime to 3, hence $x\equiv y(n)$ , contradiction. Otherwise we have $x^2+xy+y^2\equiv -1(3)\iff (x+2y)^2\equiv -1(3)$ , impossible. Hence $f$ is injective and bijective.
Now suppose that $n$ has a prime factor $p\not=3$ and write $n=p^ka$ where $k\ge 1,(a,p)=1$ . First suppose that $p>3$ .

Lemma. The equation $x^2+xy+y^2\equiv -1(p^k)$ has a solution $x,y\in Z$ .
Proof. First we show that $x^2+xy+y^2\equiv -1(p)$ has a solution. We can rewrite as $(2x+y)^2+3y^2\equiv -4(p)$ , hence $s^2+3t^2\equiv -4(p)$ . The sets $\{s^2\},\{-4-3t^2\}\subset F_p$ have ${{p+1}\over 2}$ elts, hence they cannot be disjoint. We find a solution $s,t\in Z$ and we can solve $2x+y\equiv s, y\equiv t(n)$ .
Now suppose that $x^2+xy+y^2=tp^k-1$ and we want to modify this solution to find a solution mod $p^{k+1}$ .
This is similar to Hensel's lemma. Try $Y=y+\lambda p^k$ then $x^2+xY+Y^2\equiv -1(p^{k+1})\iff \lambda (x+2y)\equiv -t(p)$ . We can solve for $\lambda$ unless when $x+2y\equiv 0(p)$ . Symmetrically we can find a solution mod $p^{k+1}$ unless when $x+2y\equiv 0(p)$ . If both cases apply then $x\equiv y\equiv 0(p)$ . This is impossible and we have proved the lemma.

I leave it to the reader to prove the lemma when $p=2$ , actually the proof is a bit easier.
To apply the lemma we will need a solution with $x\not\equiv y(p^k)$ . Note that $(x,-x-y)$ is also a solution. If $x\equiv y, -x-y (p^k)$ then $y\equiv -2x\implies x\equiv -2x\implies x\equiv 0\implies x\equiv y\equiv 0$ , which again is impossible.

Finally, find $x,y\in Z$ with $x^2+xy+y^2\equiv -1(p^k)$ and $x\not\equiv y(p^k)$ . Pick $X\in Z$ with $X\equiv y(a), X\equiv x(p^k)$ . Then $X^3+X\equiv y^3+y(n)$ and $X\not\equiv y(n)$ .

Thanks djmathman below for the link. Like I said it was posted a few days ago (by Chandru I think), and I didn't know it had appeared before.

This post has been edited 2 times. Last edited by alexheinis, Apr 11, 2025, 9:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7938 posts

#4 h Apr 11, 2025, 8:11 PM

Y by

This is APMO 2014 Problem 3.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a