Explicación de OEIS: A000236 - Clases de Residuos

Question

Estoy buscando en OEIS:A000236, cuya definición establece:

Máximo en m tal que no hay dos elementos adyacentes pertenecientes a la misma n-ésima potencia de residuos de la clase modulo algunos de los mejores p en la secuencia 1,2,...,m (equivalentemente, no es la n-ésima potencia de residuos modulo p en la secuencia de 1/2,2/3,...,(m-1)/m).

No acabo de entender esto. He aquí lo que tengo hasta ahora:

• El poder de residuos de la clase $b=[a]_m$ representa a todos los $b$ que $a=b \pmod m$ (gracias a la Inceptio la respuesta). Esto representa todos los posibles restos de $a \div m$.
• Una condición necesaria y suficiente para $t \in R$ donde $R$ se compone de la $n$th poder residuos de $\pmod p$ es que el $x^k \equiv t \mod p$ soluble ($x$ existe). Fuente: CMS
• Si $z$ es el máximo valor tal que no hay dos elementos adyacentes en 1, 2, ..., m pertenecientes a la misma potencia de residuos de la clase, entonces eso significa que el $z$ $z+1$ pertenecen a la misma potencia de residuos de la clase

Esto me lleva a creer que si dos números de $z_1, z_2$ están en el mismo $n$th poder de residuos de la clase $\pmod p$, significa que no existe $y_1, y_2$ tal que $y_1^n \equiv z_1 \pmod p$ $y_2^n \equiv z_2 \pmod p$

Si esto es correcto, genial. Si es incorrecto, es posible que alguien me explique donde mis ideas están mal y lo que esta secuencia? Gracias!

Answer 1

La respuesta de @EpsilonNeighborhoodWatch no es del todo correcta.

En primer lugar, se hace una impresión de que prime $p$ es seleccionado de forma independiente para cada par de $x,y$, mientras que en la realidad prime $p$ debe ser el mismo para todos los elementos de la $1,2,\dots,m$.

Segundo, el $n$-ésima potencia de residuos de la clase se define como sigue. Dos dos-cero residuos $x$ $y$ modulo $p$ pertenecen a la misma $n$-ésima potencia de residuos de la clase iff $x/y\equiv z^n\pmod{p}$ algunos $z$ (en otras palabras, $x/y$ $n$- ésima potencia de residuos modulo $p$).

Equivalentemente, el $n$-ésima potencia de residuos de la clase puede ser definida a través de una raíz primitiva $r$ modulo $p$ como sigue. Deje $x\equiv r^k\pmod{p}$ (es decir, $k$ es el discreto registro de $x$ base $r$ modulo $p$). A continuación, el $n$-ésima potencia de residuos de la clase de $x$ está determinada únicamente por el valor de $k\bmod\gcd(p-1,n)$. En particular, existen exactamente $\gcd(p-1,n)$ diferentes $n$-ésima potencia de residuos clases modulo $p$. Para maximizar el número de clases para un determinado $n$, se necesita un primer $p$ tal que $n\mid p-1$, dando un total de $n$ $n$-th poder de residuos clases modulo $p$.

Answer 2

Esta respuesta no es totalmente correcta, como se ha señalado por @HyperNeutrino. Yo no sé cuál es la lectura correcta es así que voy a dejar esto para la posteridad. Max Alekseyev otra respuesta aquí que puede ser correcta, sin embargo no entiendo su explicación.

Vamos a romper este un poco.

Se le da $n$ como la colocación en la secuencia y usted está buscando para algunos $m$. $m$ es el número más grande tal que no hay dos miembros de la secuencia de $1, 2, 3, 4, ... , m-1, m$ satisfacer una propiedad específica, $P(x,y)$.

$P(x,y)$ es verdadera si $x$ $y$ pertenecen a una potencia de residuos de la clase mod de algunos de los mejores. Parece que en tu pregunta ha confundido residuo de clases y el poder de residuos de clases. En general, los residuos de la clase de alguna función mod $p$ es todos los valores que la función se puede expresar mod $p$, o todos los restos que función puede tener cuando se divide por $p$. Para una potencia de residuos de la clase que la función es $n$th poderes (nuestro índice) que significa que $f:\mathbb{N}\mapsto\mathbb{N} : f(x) = x^n$.

La definición también dispone de una variedad específica de energía de residuos de clases. Clases donde nuestra $p$ es primo.

Esto significa que $P(x,y)$ es verdadero si existe alguna prime $p$ tal que existe una $a$ $b$ tal que

\begin{equation} x \equiv a^n \mod p \end{equation}

y

\begin{equation} y \equiv b^n \mod p \end{equation}

---

A este estado en una manera que me parece más intuitiva:

Para algunos $n$, $m$ es el menor número tal que $P(m,m+1)$.

No sé por qué la OEIS sale de su camino para definir una secuencia cuando está bastante claro que la primera secuencia junto con los miembros de la satisfacción de la propiedad debe cumplir siempre con las últimas dos miembros, por lo que sólo se preocupan realmente de la $m$$m+1$.

Espero que esta ayuda.