Skip to main content
edited title
Link
Michael Hardy
  • 1
  • 12
  • 85
  • 126

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

fix misleading formatting
Source Link
Emil Jeřábek
  • 47.9k
  • 4
  • 151
  • 210

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 $1\bmod p^n$$\bmod p^n$ or $2\bmod p$$\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.

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 $1\bmod p^n$ or $2\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.

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.

Minor Math Jaxing and formatting
Source Link
Daniele Tampieri
  • 6.4k
  • 7
  • 30
  • 45

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 (1) $\bmod p^n$$1\bmod p^n$ or (2) $\bmod p$.

(1) For example, if the result is $\bmod p^n$, $f(x)=x-(x\mod {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},...,x_1,x_0)$ to $(x_{n-1},0,...,0,0)$$2\bmod p$.

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

  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.

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 (1) $\bmod p^n$ or (2) $\bmod p$.

(1) For example, if the result is $\bmod p^n$, $f(x)=x-(x\mod {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},...,x_1,x_0)$ to $(x_{n-1},0,...,0,0)$.

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

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

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 $1\bmod p^n$ or $2\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.

Source Link
fofo
  • 31
  • 4
Loading