Let $p$ be a prime number. Determine the maximal degree of a polynomial $T(x)$ whose coefficients belong to $\{ 0,1,\cdots,p-1 \}$, whose degree is less than $p$, and which satisfies \[T(n)=T(m) \; \pmod{p}\Longrightarrow n=m \; \pmod{p}\] for all integers $n, m$.
Problem
Source:
Tags: algebra, polynomial, modular arithmetic, function, Congruences
25.05.2007 03:24
As $ T(x) = x^{p - 2}$ shows, there is a polynomial of degree $ p - 2$ with the required property. Thus we only have to exclude ones with degree $ p - 1$: Let $ T(x) = \sum_{k = 0}^{p - 1} a_k x^k$. Define $ s_k = \sum_{i = 1}^p i^k$, then it's known that $ p|s_k$ if $ 0\leq k \leq p - 2$ (posted by me on PEN somewhere) and $ s_{p - 1} \equiv - 1 \mod p$ (simply little Fermat). As $ T$ is supposed to be injective as a function $ \mathbb Z / p \mathbb Z \to \mathbb Z / p \mathbb Z$, it is bijective. Especially $ 0 \equiv \sum_{i = 1}^p i \equiv \sum_{i = 1}^p T(i) = \sum_{i = 1}^p \sum_{k = 0}^{p - 1} a_k i^k \mod p$. Using what we know, we get $ 0 \equiv \sum_{k = 0}^{p - 1} a_k \sum_{i = 1}^p i^k = \sum_{k = 0}^{p - 1} a_k s_k \equiv - a_{p - 1} \mod p$. This gives $ p|a_{p - 1}$, thus $ a_{p - 1} = 0$, in other words: $ T$ has degree strictly less than $ p - 1$. [thanks ZeTaX for rewriting nicely]
14.12.2007 23:01
You have probably finished learning the English meanwhile, can you please write your solution in good english now? I get what you mean, but as it stands there it's quite confusing for people unfamiliar with the matter.