¿Por qué es la función de $f(x)=x^3 \pmod{10}$ periódico con esta extraña propiedad?

Question

Me he dado cuenta de que la función de $f(x)=x^3 \pmod{10}$ es periódica. Por ejemplo, listado de mod(x^3,10) obtenemos:

0,1,8,7,4,5,6,3,2,9,0,1,8,7,4,5,6,3,2,9,0,1,8,7,4,5,6,3,2,9,0,1,8,7,4,5,6,3,2,9,0,1,8,7,4,5,6,3,2,9

Lo que es raro, sin embargo, que el período contiene todos los números de la imagen de la función de la exactamente una vez. ¿Por qué ocurre eso?

Answer 1

Respuesta corta: porque $10$ es squarefree y $3$ es relativamente primer a $\phi(10) = \phi(5\cdot 2) = 4$.

Si $m = p^2q$ no es squarefree, a continuación, $x^3$ nunca será congruente a $p$ mod $m$, ya que si $m\vert (x^3-p)$,$p\vert x$, que conduce a una contradicción ya que el $p^2\nmid (x^3-p)$.

Si $m$ es squarefree y 3 es primo relativo a $\phi(m)$, $f(x)=x^3$ es un bijection; es suficiente para demostrar que todos los $0\leq a < m$ tiene una raíz cúbica de mod $m$.

Como Quiochu sugiere, si $m$ es el primer y el 3 es primo relativo a $\phi(m)$, entonces no existen números enteros no negativos $x,y$$3x = \phi(m)y+1$. Por lo tanto, para todos los $0\leq a < m$, $$(a^x)^3 = (a^{\phi(m)})^ya = a,$$ así que cada $a$ tiene una raíz cúbica $a^x$.

Ahora supongamos $m=p_1 p_2\ldots p_k$ es squarefree pero compuesto. Desde el 3 es primo relativo a $\phi(m)$, es relativamente primos a todos los $\phi(p_i)$. A continuación, para cada $0\leq a < m$, por lo anterior, usted puede encontrar una raíz cúbica de a $a$ mod $p_i$.

Por el teorema del resto Chino, existe, entonces, una $b$ con $$b^3 \equiv a \pmod {p_i}$$ para cada $p_i$, e $b^3 \equiv a \pmod m$.

Answer 2

Tiene período de dividir 10 porque son la reducción de las cosas modulo 10. Modulo 10, es una congruencia lo que significa que cuando las operaciones aritméticas (suma, resta, multiplicación, división por invertible cosas) se utilizan con el argumento de que son equivalentes modulo 10, los resultados son también equivalentes modulo 10. por ejemplo,

$$ a \equiv a' \mod 10 \qquad \text{and} \qquad b \equiv b' \mod 10 $$

imply

$$ a + b \equiv a' + b' \mod 10 $$

The fact your function takes every value modulo 10 can be thought of as a mild coincidence. It could have happened that way, or it could have happened otherwise, and it happened to happen that way for 10.

However, we can analyze when it happens. Consider

$$ f(x) = x^n \mod m$$

and we want this to take on every value modulo $m$.

One important idea is the Chinese Remainder Theorem; in this case, if $m = pq$ where $p$ and $p$ are relatively prime, then $f(x)$ has the property we desire if and only if both

$$ x^n \mod p \qquad \text{and} \qquad x^n \mod q $$

have the property. In this case, you can check:

• $x^3 \mod 2 = 0, 1, 0, 1, \cdots$
• $x^3 \mod 5 = 0, 1, 3, 2, 4, 0, 1, 3, 2, 4, \cdots$

Ahora, si $m = p^k$ donde $p$ es un número primo, entonces necesitamos $k = 1$ o $n = 1$. Si tanto $k > 1$$n>1$, $p^n$ es divisible por $p^2$, y así es $p^n \bmod m$. Por lo tanto, nunca podemos tener $x^n \equiv p \bmod m$.

Ahora, considere el caso donde $m$ es primo. Un argumento que implican el teorema de Euler implica que $f(x)$ tiene la propiedad que desea, si y sólo si $\gcd(n, m-1) = 1$.

Resulta que podemos combinar la información anterior en una sola prueba: para $n > 1$ hemos

• $f(x) = x^n \bmod m$ tiene la propiedad deseada iff $m$ es squarefree y $\gcd(n, \varphi(m)) = 1$.

Ahora, vamos a construir un ejemplo! Deje $m = 3 \cdot 5 \cdot 7$. Necesitamos $n$ a ser relativamente primos a $2$, $4$, y $6$. El menor valor de $n$ más grande que la de $1$ que podemos elegir es de 5: yo creo que la función

$$ f(x) = x^5 \bmod 105 $$

has the same property you observed: it has period 105, and it also takes every value modulo $105$.

Este corto comando python pruebas de mi afirmación de que toma cada valor:

>>> len({ pow(x,5,105) for x in range(105) }) == 105
True

y que un valor menor no funciona:

>>> len({ pow(x,3,105) for x in range(105) })
45

Answer 3

Oblicua a la pregunta original, pero puede ayudar si usted desea explorar más a fondo.

Los enteros modulo $10$ formar un anillo. Esto es cierto sea cual sea el módulo. Básicamente, significa que la suma, la resta, la multiplicación y funciona correctamente, incluyendo la propiedad distributiva. No puede ser $ab=0$ sin $a=0$ o $b=0$. Ser un anillo significa que $x^3 \pmod {10}=(x \pmod {10})^3 \pmod {10}$ o, informalmente, puede quitar todos los dígitos, excepto las unidades antes de cubicación, a continuación, tira de ellos después. Lo que he observado es que la función de $x^3 \pmod {10}$ es inyectiva.