EE.UU. TST 2018/P1: Demuestre que la $n^{\text{th}}$ menor número entero positivo relativamente primo a $n$ es como mínimo $\sigma(n)$

Question

Sea $n \ge 2$ sea un número entero positivo y $\sigma(n)$ denotan la suma de los divisores positivos de $n$ . Demostrar que el $n^{\text{th}}$ menor número entero positivo relativamente primo a $n$ es como mínimo $\sigma(n)$ y determinar para qué $n$ la igualdad se mantiene.

Mi progreso: ¡¡¡Problema realmente difícil!!!

Obviamente, he mirado ejemplos.

Para n=2, $\sigma(2)=3$ y el segundo positivo relativamente primo de 2 era 3.

Para n=3, $\sigma(3)=4$ y el tercer positivo relativamente primo de 3 era 4.

Para n=4, $\sigma(4)=1+2+4=7$ y el cuarto positivo relativamente primo de 4 era 7.

Para n=5, $\sigma(5)=1+5=6$ y el quinto positivo relativamente primo de 5 era 6.

Para n=6, $\sigma(6)=3\cdot 4=12$ pero el sexto positivo relativamente primo a 6 era 17.

Entonces, a partir de aquí conjeturé que el caso de igualdad es cierto si y sólo si $n =$ potencia perfecta de un primo.

---

En primer lugar $S(n)$ sea el $n^{\text{th}}$ menor número entero positivo relativamente primo a $n$ .

Ahora, para $n=$ funciona, ya que $\sigma(n)=p+1$ y $S(n)=p+1$ ya que sólo $p$ no es relativamente primo de $p$ y $p+1$ es .

Antes de continuar, me gustaría exponer la fórmula que he obtenido y que se puede demostrar por inducción o simplemente por aritmética modular.

Para un número entero dado $x$ y una potencia perfecta de primo $"l^k"$ . Conseguimos que $x$ es el $[x-Q(x,l)]^{\text{th}}$ número que es relativamente primo de $l^k$ . donde $Q(x,l)$ es el cociente cuando $x$ se divide por $l$ .

Ahora $n=p^k$ para algún primo $p$ y $k>1$ .

Así que lo entendemos, $\sigma(p^k)= 1+p^2+\dots +p^k$ .

Afirmamos que $S(p^k)=1+p^2+\dots +p^k$ . podemos demostrarlo utilizando el hecho de que $S(n)$ es única o, en otras palabras, podemos demostrar que $1+p^2+\dots +p^k$ es el ${p^k}^{\text{th}}$ número relativamente primo en lugar de encontrar el ${p^k}^{th}$ número relativamente primo .

Pero por la fórmula que hemos indicado, obtenemos que $1+p^2+\dots +p^k$ es el $[1+p^2+\dots +p^k - Q(1+p^2+\dots +p^k,p)]=[1+p^2+\dots +p^k -(1+p^2+\dots +p^{k-1})]= p^k$

¡Y ya está!

Estoy atascado en demostrar que el caso de igualdad no para múltiplos primos .

El folleto que estoy utilizando daba estas pistas para el problema general:

$1$ . $\sum_{d|n} \phi(d)=n$ .

$2$ . Básicamente construimos a la inversa el $\sigma(n$ ) como la suma de los divisores y construir intervalos que tengan cada uno un $d_i$ número de números relativamente primos.

Ni siquiera podía entender el $2^{\text{nd}}$ insinuar.

Por favor, inténtelo con este hermoso problema y espero que alguien me pueda dar pistas para este problema.

Gracias de antemano.

Answer 1

La segunda pista es una pista preciosa. Sólo añadiré eso:

$\phi(m)$ es el número de enteros coprimos a $m$ en cualquier $m$ enteros consecutivos.

y utilizar la primera pista para cubrir el intervalo $n+1,n+2,\dots,\sigma(n)$ . Obsérvese que cualquier número coprimo a $n$ debe ser coprimo a todos los divisores de $n$ .

Answer 2

Su $2^{nd}$ puede escribirse como sigue

Reclamación: Si $k$ y $m$ son enteros positivos entonces el número de enteros en el intervalo $[k,k+m-1]$ que son coprimos de $m$ es exactamente $\varphi(m)$ donde $\varphi$ es la función Totiente de Euler.

Prueba (croquis): Es fácil observar que $\{k,k+1,\ldots,k+m-1\}$ es una clase completa de residuos módulo $m$ . Por lo tanto, existe una correspondencia uno a uno entre los enteros positivos en $\{0,1,2,\ldots,m-1\}$ que son coprimos de $m$ y los enteros positivos en $\{k,k+1,\ldots,k+m-1\}$ que son coprimos de $m$ . Por lo tanto, se deduce la alegación.

Para demostrar que la $n^{th}$ número entero positivo más pequeño que es relativamente primo de $n$ es como mínimo $\sigma(n)$ basta con demostrar que el número de enteros en el intervalo $[1,\sigma(n)]$ que son relativamente primos de $n$ es como máximo $n$ . Sea $\tau(n)=k$ donde $\tau(n)$ denota el número de divisores positivos de $n$ incluyendo $n$ y $1$ . Sea $$1=d_1<d_2<\cdots<d_k=n$$ sea el $k$ divisores. Entonces $$\sigma(n)=d_1+d_2+\cdots+d_k$$ Particionamos el intervalo $[1,\sigma(n)]$ de la siguiente manera,

$$[1,\sigma(n)]=I_1\cup I_2\cup\cdots\cup I_k$$

donde,

$$I_1=[1,d_1]\\I_2=[d_1+1,d_1+d_2]\\I_3=[d_1+d_2+1,d_1+d_2+d_3]\\\vdots\\I_k=[d_1+d_2+\cdots+d_{k-1}+1,d_1+d_2+\cdots+d_k]=[d_1+d_2+\cdots+d_{k-1}+1,\sigma(n)]$$

Tenga en cuenta que $I_j$ tiene longitud $d_j$ para $1\leq j\leq k$ . Ahora, por la afirmación anterior, el número de enteros positivos en el intervalo $I_j$ que son coprimos de $d_j$ es exactamente $\varphi(d_j)$ . Dado que los intervalos, $I_j$ son disjuntos y los números enteros positivos que son relativamente primos de $n$ son exactamente aquellos que son coprimos a todos sus divisores, tenemos el número de enteros positivos en el intervalo $[1,\sigma(n)]$ es como máximo $$\sum_{j=1}^{k}\varphi(d_j)=\sum_{d\mid n}\varphi(d)=n$$ Por lo tanto, ¡hemos terminado!

Answer 3

¡Por fin tengo la prueba! Me llevó casi 2 días resolverlo. La pista era casi todo .

Aquí está la solución completa que conseguí.

Prueba : Sea $1<d_1<d_2<\dots<d_k<n$ sean los divisores de $n$ .

Tenga en cuenta que $\sigma (n) = 1+d_1+\dots + n $ .

Consideremos ahora las siguientes particiones

$P_1= [1,d_1]$

$P_2= [1+d_1,\cdots , d_1+d_2]$

.

.

.

$P_{k+1}= [1+d_1+d_2 +\cdots d_k, \cdots, 1+d_1+d_2 +\cdots d_k+n]= [1+d_1+d_2 +\cdots d_k, \cdots, \sigma (n)]$

Obsérvese que en cada partición $P_i$ es de longitud $d_i$ .

Tenga en cuenta también que hay como máximo $\phi (d_i)$ números en la partición $P_i$ que son relativamente primos de $n$ . ( ya que $\phi(m)$ es el número de enteros coprimo a $m$ en cualquier $m$ números enteros consecutivos )

Por lo tanto, entre $1$ a $d_1+d_2\cdots d_k=\sigma(n)$ hay como máximo $ \sum_{d \mid n} \varphi(d) = n $ números que son relativamente primos de $n$ .

Esto demuestra la parte principal del problema.

Ahora, el caso de la igualdad .

Afirmamos que el caso de igualdad se cumple si y sólo si $n=$ potencia perfecta de un primo.

En primer lugar, demostraremos que $n=$ potencia perfecta de un primo.

deje $S(n)$ sea el $n^{\text{th}}$ menor número entero positivo relativamente primo a $n$ .

Ahora, para $n=$ de primera. Funciona, ya que $\sigma(n)=p+1$ y $S(n)=p+1$ ya que sólo $p$ no es relativamente primo de $p$ y $p+1$ es .

Consideremos la siguiente proposición, que puede demostrarse por inducción o aritmética modular.

Para un número entero dado $x$ y una potencia perfecta de primo $"l^k"$ . Conseguimos que $x$ es el $[x-Q(x,l)]^{\text{th}}$ número que es relativamente primo de $l^k$ donde $Q(x,l)$ es el cociente cuando $x$ se divide por $l$ .

Ahora $n=p^k$ para algún primo $p$ y $k>1$ .

Así que lo entendemos, $\sigma(p^k)= 1+p^2+\dots +p^k$ .

Afirmamos que $S(p^k)=1+p^2+\dots +p^k$ . podemos demostrarlo utilizando el hecho de que $S(n)$ es única o, en otras palabras, podemos demostrar que $1+p^2+\dots +p^k$ es el ${p^k}^{\text{th}}$ número relativamente primo en lugar de encontrar el ${p^k}^{th}$ número relativamente primo .

Pero por la fórmula que hemos indicado, obtenemos que $1+p^2+\dots +p^k$ es el $[1+p^2+\dots +p^k - Q(1+p^2+\dots +p^k,p)]=[1+p^2+\dots +p^k -(1+p^2+\dots +p^{k-1})]= p^k$

Y hemos terminado por esta parte .

Ahora, mostraremos que si n es un producto de múltiples primos distintos , entonces el caso de igualdad no se cumple.

Sea $n={p_1}^{\alpha_1}\cdot{p_2}^{\alpha_2}\cdot X$ donde gcd $(p_1,X)=1$ y gcd $(p_2,X)=1$ y $p_1$ y $p_2$ son primos .

Procediendo por la construcción similar como lo hicimos para la prueba principal,

deje $1<d_1<d_2<\dots<d_k<n$ sean los divisores de $n$ .

Tenga en cuenta que $\sigma (n) = 1+d_1+\dots + n $ .

Consideremos ahora las siguientes particiones

$P_1= [1,d_1]$

$P_2= [1+d_1,\cdots ,d_1+d_2]$

.

.

.

$P_{k+1}= [1+d_1+d_2 +\cdots d_k, \cdots, 1+d_1+d_2 +\cdots d_k+n]= [1+d_1+d_2 +\cdots d_k, \cdots, \sigma (n)]$

Tenga en cuenta que aquí, $d_1=p_1$ y $d_2=p_2$ .

Veamos ahora la partición $P_2=[1+p_1,\cdots , p_1+p_2]$ . Desde $p_1<p_2$ Obsérvese que $2p_1$ también estará allí en esta partición, . Así que tenemos como máximo $\phi(p_2)-1$ números de $P_2$ que son relativamente primos de $n$ .

Por lo tanto, entre $1$ a $d_1+d_2\cdots d_k=\sigma(n)$ hay como máximo $ \sum_{d \mid n} \varphi(d)-1 = n-1 $ números que son relativamente primos de $n$ .

De ahí que el $n^{\text{th}}$ número primo real a $n$ será estrictamente mayor que $\sigma (n)$ si $n$ es múltiplo de $2$ o más primos.

¡Y ya está!

Answer 4

Así que aquí está mi solución sin ninguna pista :

Sea $T[x]$ denotan el $x^{th}$ coprimo natural más pequeño de $x$ .

En primer lugar, demostraremos que para $n = p^k$ la igualdad se mantiene.

En este caso, $T[x] - \lfloor T[x]/p \rfloor = p^k$ . Vemos que $\sigma (p)$ satisface esta ecuación pero, además, sabemos que si $T_{k}[x]$ denota el número de naturales que son al menos $k$ y son coprimos a $x$ alors $T_{k}[x]$ es único ya que $k$ varía, lo que acaba con nuestra primera afirmación.

Ahora, una parte agradable. Vamos a demostrar que $T_{\sigma (x)}[x] \leq x$ . Sea $d_1, d_2 \dots d_k$ sean divisores de $x$ . Vemos que entre los primeros $d_1$ naturales, exactamente $\phi (d_1)$ son coprimos a $d_1$ por lo que como máximo $\phi ( d_1)$ coprima a $x$ . Entonces consideramos $[d_1 + 1, d_1 + d_2]$ para $d_2$ etc. Por lo tanto $T_{\sigma (x)}[x] \leq \sum_{p \mid x} \phi (p) = x$ y claramente la igualdad se mantendrá si y sólo si $\Omega (x) = 1$ . ¿Por qué? Piensa si $d_t$ es un primo menor que $d_j$ que es otro primo y ambos dividiendo a $x$ y considerar el intervalo de $d_j$ en el intervalo, como máximo $\phi (d_j) - 1$ naturales serán coprimeros a $x$ y ya está.