Relación entre diferentes sucesiones generadas a través de la aritmética del módulo.

Question

Relación entre diferentes sucesiones generadas a través de la aritmética del módulo.

Matemáticas
auto aprendizaje
secuencias y series
teoría-de-números-elemental

dcdo

No estoy seguro de la terminología / notación matemática formal para tratar con secuencias generadas a partir de la aritmética de módulo entero. En primer lugar, ¿alguien podría recomendar un libro que se centre en las secuencias generadas a partir de operaciones aritméticas en conjuntos finitos de números enteros? Compré un libro de teoría de números elemental y un libro de álgebra abstracta, pero nunca discutí secuencias.

Ahora la pregunta más explícita. Considerar:

F [norte] = a norte (modificación norte) gramo [norte] = b norte (modificación norte)

$f \left[ n \right] = a n \left( \text{mod} \; N \right) \\ g\left[n\right] = b n \left( \text{mod} \; N \right)$ dónde

a, b \in Z

$a,b \in \mathbb{Z}$ ,

n \in {0, 1, 2, \dots}

$n \in \{0, 1, 2, \ldots \}$ ,

N \in {2, 3, 4, \dots}

$N \in \{2, 3, 4, \ldots\}$ y

a (mod N)

$a \left( \text{mod} \; N \right)$ es el resto de

a / N

$a / N$ . Quiero probar que a veces la secuencia

g [n]

$g[n]$ "generado" (puede que no sea un término correcto) por una elección de

b

$b$ es una "permutación" (puede que no sea un término correcto) de la secuencia

f [n]

$f[n]$ generado por

a

$a$ si

N

$N$ es lo mismo los dos. También quiero mostrar que la nueva permutación puede ser generada por

gramo [norte] = F [k norte]

$g \left[ n \right] = f \left[ k n \right]$ para algunos

k \in Z

$k \in \mathbb{Z}$ siempre que exista tal permutación. tengo la sospecha de que si

a

$a$ y

b

$b$ son relativamente primos para

N

$N$ entonces tal permutación existe por lo poco que sé de las relaciones de congruencia ~~, pero también puedo pensar en casos en los que $a$ es relativamente primo para $N$ y $b$ No es que esto todavía funcione~~ .

André Nicolás

Si

b

$b$ no es relativamente primo para

N

$N$ , entonces habrá periodicidad con período

< N

$\lt N$ . Si

a

$a$ es relativamente primo para

N

$N$ entonces el periodo sera

N

$N$ . Así que no parece haber un sentido claro en el que una secuencia sea una permutación de la otra.

dcdo

Lo que estaba pensando era algo a lo largo de las líneas

f [n] = n (mod 8)

$f[n] = n (\text{mod} \; 8)$ y

g [n] = 2 n (mod 8)

$g[n] = 2n ( \text{mod} \; 8)$ . Entonces

f [n] = \[0, 1, 2, 3, 4, 5, 6, 7 \]

$f[n] = \[0, 1, 2, 3, 4, 5, 6, 7\]$ y

g [n] = \[0, 2, 4, 6 \]

$g[n] = \[0, 2, 4, 6 \]$ , pero

f [2 n] = \[0, 2, 4, 6 \]

$f[2n] = \[0, 2, 4, 6 \]$ . Una vez más, la permutación podría ser la palabra incorrecta.

André Nicolás

Acerca de las referencias, por un tiempo, si está investigando este tipo de secuencias, las herramientas ordinarias de la aritmética modular deberían ser suficientes. Tienes razón sobre lo que sucede cuando

a

$a$ y

b

$b$ son relativamente primos para

N

$N$ . Cada una de las secuencias tiene un período.

N

$N$ , y va en algún orden a través de los números

0

$0$ a

N - 1

$N-1$ .

Respuestas (1)

Relación entre diferentes sucesiones generadas a través de la aritmética del módulo.

Si $b$ no es relativamente primo para $N$ , entonces habrá periodicidad con período $\lt N$ . Si $a$ es relativamente primo para $N$ entonces el periodo sera $N$ . Así que no parece haber un sentido claro en el que una secuencia sea una permutación de la otra.
Lo que estaba pensando era algo a lo largo de las líneas $f[n] = n (\text{mod} \; 8)$ y $g[n] = 2n ( \text{mod} \; 8)$ . Entonces $f[n] = \[0, 1, 2, 3, 4, 5, 6, 7\]$ y $g[n] = \[0, 2, 4, 6 \]$ , pero $f[2n] = \[0, 2, 4, 6 \]$ . Una vez más, la permutación podría ser la palabra incorrecta.
Acerca de las referencias, por un tiempo, si está investigando este tipo de secuencias, las herramientas ordinarias de la aritmética modular deberían ser suficientes. Tienes razón sobre lo que sucede cuando $a$ y $b$ son relativamente primos para $N$ . Cada una de las secuencias tiene un período. $N$ , y va en algún orden a través de los números $0$ a $N-1$ .

joriki · Answer 1

Como se indica en los comentarios, si $a$ y $b$ son coprimos de $N$ , entonces cada una de las sucesiones tiene periodo $N$ . En este caso $g[n]=f[kn]$ con $k=a^{-1}b$ , dónde $a^{-1}$ es el inverso multiplicativo de $a\pmod N$ . Esto también funciona si solo $a$ es coprimo de $N$ (pero en este caso $g[n]$ tiene un período más corto).

Más generalmente, si $d:=\gcd(a,N)\mid b$ , luego con $a'=a/d$ , $b'=b/d$ y $N'=N/d$ tenemos $g[n]=f[kn]$ con $k=a'^{-1}b'$ , donde se toma el inverso multiplicativo $\bmod{N'}$ .

Si $d\nmid b$ , entonces $g[n]$ toma valores que $f[n]$ no toma, por lo que no puede haber $k$ con $g[n]=f[kn]$ .

Relación entre diferentes sucesiones generadas a través de la aritmética del módulo.

dcdo

André Nicolás

dcdo

André Nicolás

Respuestas (1)

joriki

Suma de recíprocos de números impares que suman 222

Una propiedad interesante de los números de Fibonacci

Buscando la mejor manera de encontrar triples pitagóricos donde B−A=±1B−A=±1B-A=\pm1.

Encuentra tres números enteros en la progresión armónica

Generar números primos de la forma ⌊3–√⋅n⌋⌊3⋅n⌋\lfloor \sqrt{3} \cdot n \rfloor

Número de ocurrencias de un número nnn en ⌊0–√⌋,⌊1–√⌋,⌊2–√⌋,…⌊0⌋,⌊1⌋,⌊2⌋,…\lfloor \sqrt{0} \rfloor, \lpiso \sqrt{1} \rpiso, \lpiso \sqrt{2} \rpiso, \puntos

Vladímir Zorich contra Rudin/Pugh/Abbott

Teorema 3.55 en Baby Rudin: ¿Cómo dar sentido a la demostración?

Demuestre esta identidad utilizando la identidad de producto triple de Jacobi

¿Existen huecos primos arbitrariamente largos en los que cada número tiene al menos tres factores primos distintos?