$p$ is a prime. Let $K_p$ be the set of all polynomials with coefficients from the set $\{0,1,\dots ,p-1\}$ and degree less than $p$. Assume that for all pairs of polynomials $P,Q\in K_p$ such that $P(Q(n))\equiv n\pmod p$ for all integers $n$, the degrees of $P$ and $Q$ are equal. Determine all primes $p$ with this condition.
Problem
Source: Turkey TST 2016 P9
Tags: number theory, polynomial
MathPanda1
10.04.2016 18:45
Is it assuming $P, Q \in K_p$?
Eray
10.04.2016 18:47
Edited! Thank you
shinichiman
12.04.2016 14:45
This problem seems wrong to me, or maybe I'm mistaken somewhere. I can prove that if $P(Q(n)) \equiv n \pmod{p}$ for all integers $n$ then degrees of $P$ and $Q$ are $1$. I used the fact that: A polynomial $A(x) \equiv 0 \pmod{p}$ for all integers $x$ then its coefficients are all divisible by $p$. I applied this to consider the coefficient of the highest degree of $P(Q(n))$, which is $p_kq_l^{k}$ where $P(x)= \sum_{i=0}^k p_ix^i, \; Q(x)= \sum_{i=0}^lq_ix^i$ if $\max \{ \text{deg }P(x), \text{deg Q(x)} \} \ge 2$. I find $p \mid p_kq_l^k$ and since $q_i,p_i \in \{ 0, \cdots, p-1 \}$ we find a contradiction. Thus, $\max \{ \text{deg }P(x), \text{deg Q(x)} \} \le 1$.
fattypiggy123
12.04.2016 15:07
shinichiman wrote: A polynomial $A(x) \equiv 0 \pmod{p}$ for all integers $x$ then its coefficients are all divisible by $p$. This is only true when the degree of the polynomial is $\leq p-1$. For instance $x^p - x$ satisfies the statement. The correct version would be that sum of the coefficients of powers which share the same residue mod $p-1$ are divisible by $p$.
fractals
13.04.2016 04:54
A finite list of values which we are mostly too lazy to check.
Suppose that $a\not\equiv b\pmod{p - 1}$ satisfied $ab\equiv 1\pmod{p - 1}$. Then $P(x) = x^a, Q(x) = x^b$ would have $P(Q(n)) = n^{ab}\equiv n\pmod{p}$ for all integers $n$ and the degrees of $P, Q$ are unequal and less than $p$ when considering $a, b$ as least residues.
Thus, for $p$ to work, $\pmod{p - 1}$ must have the property that if $\gcd(a, p - 1) = 1$ then $a^2\equiv 1\pmod{p - 1}$. Then all of $p - 1$'s constituent prime powers have the same property, by CRT.
But $\pmod{q^k}$ clearly does not have this property if $q \ge 3$ - unless $q = 3, k = 1$. For otherwise, $\gcd(2, q) = 1$ yet $2^2\not\equiv 1\pmod{q^k}$ - and then we have serious problems.
Also, $\pmod{2^k}$ has this property only when $k \le 3$, else $3^2\not\equiv 1\pmod{2^k}$ while $\gcd(3, 2) = 1$. So $p - 1\in\{1, 2, 4, 8, 3, 6, 12, 24\}$ and thus $p\in\{2, 3, 5, 9, 4, 7, 13, 25\}$ and thus $p\in\{2, 3, 5, 7, 13\}$.
But now we must check the original condition, which we are too lazy to do. However, $p = 2, 3, 5$ clearly work, since $\deg P, \deg Q$ must clearly be bijections and thus cannot have degrees dividing $p - 1$, unless they is linear - but that last case is trivial to dispose of, as then both must be linear.
$p = 7$ probably falls to the same trick, as this restricts us then to only $P, Q$ of degrees $4, 5$.
We're not too sure about $p = 13$, but this does let us only check $P, Q$ of degree $5, 7, 8, 9, 10, 11$ - not a drastic improvement, but still.
crazyfehmy
28.05.2016 16:10
fractals wrote:
A finite list of values which we are mostly too lazy to check.
Suppose that $a\not\equiv b\pmod{p - 1}$ satisfied $ab\equiv 1\pmod{p - 1}$. Then $P(x) = x^a, Q(x) = x^b$ would have $P(Q(n)) = n^{ab}\equiv n\pmod{p}$ for all integers $n$ and the degrees of $P, Q$ are unequal and less than $p$ when considering $a, b$ as least residues.
Thus, for $p$ to work, $\pmod{p - 1}$ must have the property that if $\gcd(a, p - 1) = 1$ then $a^2\equiv 1\pmod{p - 1}$. Then all of $p - 1$'s constituent prime powers have the same property, by CRT.
But $\pmod{q^k}$ clearly does not have this property if $q \ge 3$ - unless $q = 3, k = 1$. For otherwise, $\gcd(2, q) = 1$ yet $2^2\not\equiv 1\pmod{q^k}$ - and then we have serious problems.
Also, $\pmod{2^k}$ has this property only when $k \le 3$, else $3^2\not\equiv 1\pmod{2^k}$ while $\gcd(3, 2) = 1$. So $p - 1\in\{1, 2, 4, 8, 3, 6, 12, 24\}$ and thus $p\in\{2, 3, 5, 9, 4, 7, 13, 25\}$ and thus $p\in\{2, 3, 5, 7, 13\}$.
But now we must check the original condition, which we are too lazy to do. However, $p = 2, 3, 5$ clearly work, since $\deg P, \deg Q$ must clearly be bijections and thus cannot have degrees dividing $p - 1$, unless they is linear - but that last case is trivial to dispose of, as then both must be linear.
$p = 7$ probably falls to the same trick, as this restricts us then to only $P, Q$ of degrees $4, 5$.
We're not too sure about $p = 13$, but this does let us only check $P, Q$ of degree $5, 7, 8, 9, 10, 11$ - not a drastic improvement, but still.
For $p=13$, the following satisfies \[ f(x)=x^5+5x^3+5x \quad \text{and} \quad g(x)=12x^9+4x^7+6x. \]
sholly
24.08.2017 13:15
crazyfehmy wrote: For $p=13$, the following satisfies \[ f(x)=x^5+5x^3+5x \quad \text{and} \quad g(x)=12x^9+4x^7+6x. \] May you explain how to find such an example? Since it is a math contest problem, I wonder is there any insight to find such an example by hand. I know that your $f(x) = D_{5}(x,-1) = x^5+5x^3+5x$ is a Dickson polynomial, but it seems not easy to compute its inverse polynomial by hand.