Prueba de bijección de una función entre enteros positivos y enteros positivos no primarios.

Question

Ejercicio 4.39 en Concreto de las Matemáticas se menciona una función de $S(m)$:

Deje $S(m)$ ser el más pequeño entero positivo $n$ para los que existe un aumento de la secuencia de enteros $$ m = a_1 < a_2 < \cdots < a_t = n$$ tal que $a_1a_2...a_t$ es un cuadrado perfecto.

...

Tenemos: $$ \begin{array}{c|cc} m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ \hline S(m) & 1 &6&8&4&10&12&14&15&9&18&22&20 \end{array}$$

Este ejercicio demostró que $S(i)≠S(j)$ diferentes $i$, $j$ y deja un comentario de que "la secuencia de $S(1),\ S(2),\ S(3),\ ...$ contiene cada nonprime entero positivo exactamente una vez" en el apéndice "Respuestas a los Ejercicios", pero no dio ninguna señal o en referencia a él. No tengo ni idea sobre que es la prueba.

Answer 1

Muy interesante pregunta!

Primero vamos a probar que S(m) puede no ser la mejor. Esto se deduce del hecho de que dicha secuencia no puede terminar en una de las mejores, como el producto sólo sería divisible una vez por este primer.

Para probar que es un bijection de todos los enteros mayores que $1$ a todos los compuestos de números, le damos a la inversa. El inverso $S^{-1}(n)$ es el mayor $m$ tal que dicha secuencia existe. Tenga en cuenta que esto está bien definido para el compuesto de números como usted puede tomar la secuencia de todos los números primos dividiendo en $n$ un número impar de veces.

Para probar esto da una relación inversa, debemos mostrar $S^{-1}(S(m))=m$ tiene para todos los $m$. Esto es debido a que, si una secuencia que termina con $S(m)$ existe un mayor número de partida de $m$, tomando luego la diferencia simétrica con la secuencia que comienza con $m$ y terminando con $S(m)$ da una secuencia que comienza con $m$ y con menor número final de $S(m)$.

Answer 2

Deje $n$ ser un número compuesto. A continuación, hay secuencias de $a_1<a_2<\cdots <a_r = n$ tal que $a_1a_2\cdots a_s$ es un cuadrado. Por ejemplo, si $n = ab$ con $a<b<n$ (lo cual es posible desde $n$ es compuesto), tenemos $a\cdot b \cdot n = n^2$.

Ya que hay secuencias, y todos ellos tienen puntos de partida inferior o igual a $n$, hay un alto punto de partida, decir $m$. Deje $m = b_1<b_2<\cdots b_s = n$ ser uno de esos secuencia.

Claramente $S(m)\leq n$, como la secuencia de $b_i$ muestra. Me dicen que tenemos la igualdad. Supongamos por contradicción que $S(m) < n$. Deje $m = c_1\cdot c_2\cdots c_s = S(m)$ ser una secuencia tal que $c_1c_2\cdots c_s$ es un cuadrado. Entonces $$ b_1b_2\cdots b_s\cdot c_1c_2\cdots c_t $$ es un cuadrado. Queda una plaza si quitamos a todos los términos que aparecen dos veces. $m = b_1 = c_1$ aparece dos veces, por lo que el más pequeño factor en el despojada del producto es mayor que $m$. Y el factor más importante todavía es $n$, desde el $b_s = n$ pero $c_t<n$.

Lo que conseguimos es una secuencia de distintos números enteros que si multiplicamos ellos juntos podemos conseguir una plaza, la más grande de ellas es $n$ y el más pequeño es mayor que $m$, contradiciendo la definición de $m$.

Esto demuestra que $S(m) = n$.

Answer 3

Para un compuesto entero positivo $n$, definir $T(n)$ a ser el mayor entero positivo $m$ para los que existe un aumento de la secuencia de enteros $ m = a_1 < a_2 < \cdots < a_t = n$ tal que $a_1a_2\cdots a_t$ es un cuadrado perfecto. (Trivialmente $T(n)=n$ si $n$ es un cuadrado perfecto; si $n$ no es un cuadrado perfecto, entonces $n$ factores $n=ab$ con $a<b$, en cuyo caso $T(n) \ge a$ y, en particular, es bien definidos).

La prueba de que $S$ es uno-a-uno puede adaptarse rápidamente para mostrar que $T=S^{-1}$ (a darle una oportunidad!). Esto es suficiente para mostrar que la secuencia de $S(1), S(2), S(3),\dots$ contiene cada nonprime entero positivo exactamente una vez.