Skip to main content
4 of 5
fix misleading formatting
Emil Jeřábek
  • 47.9k
  • 4
  • 151
  • 210

Does there exists a polynomial that extracts the highest digit of an integer in base p?

Given an odd prime $p$, a positive integer $1 \lt n$, and an integer $x \in \mathbb{Z}/p^n\mathbb{Z}$, does there exist an an integer-coefficient polynomial that extracts the highest digit of $x$?

The extracted digit can be either $\bmod p^n$ or $\bmod p$.

  1. For example, if the result is $\bmod p^n$, $$ f(x)=x-(x\bmod {p^{n-1}})\bmod p^n. $$ This $f(x)$ actually clears the lower digits of $x$. Suppose $x=\sum_{i=0}^{n-1}x_ip^i$ where $x_i \in \mathbb{Z}/p\mathbb{Z}$ is each digit of $x$, then $f(x)$ maps $x=(x_{n-1},x_{n-2},\ldots,x_1,x_0)$ to $(x_{n-1},0,\ldots,0,0)$.

  2. If the result is $\bmod p$, then $f(x)$ maps $x=(x_{n-1},x_{n-2},\ldots,x_1,x_0)$ to $x_{n-1}$.

Does either of these polynomials $f(x)$ exist? Thanks in advance.

fofo
  • 31
  • 4