¿Por qué es $f(x) = x \phi (x)$ uno a uno?

Question

Me di cuenta de que $f(x) = x \phi (x)$ parece ser uno a uno, donde $ \phi (x)$ es la función Phi de Euler.

En particular, estoy escribiendo un código numérico de pitón y la línea que tengo parece algo así como

sorted([n*phi(n) for n in range(1,1000)])

y no hay duplicados en la lista.

Primero, ¿es un uno a uno?

Segundo, si es así, ¿hay un simple boceto de prueba?

Answer 1

Para probar que $x \phi (x)=y \phi (y)$ implica $x=y$ muestran que la mayor división primaria $xy$ debe dividir a ambos $x$ y $y$ a la misma potencia, y luego inducir.

Answer 2

Se puede probar esto por inducción en el número de primos que dividen $x.$

Comencemos con el caso de dos números $p^n$ y $q^m$ tal $p$ y $q$ son primos y

$$p^n \phi (p^n) = q^m \phi (q^m). \mbox { (1)}$$

Luego $p$ es el mayor primo que divide el lado izquierdo de $(1)$ y $q$ es el mayor primo que divide el lado derecho de $(1)$ . Sigue $p = q.$ Y así como,

$$q^m \phi (q^m) = q^{2m-1}(q-1),$$

Debe ser el caso que $2m -1 = 2n -1.$ Por lo tanto, $n = m.$ De ello se deduce que la función $x \mapsto x \phi (x)$ es inyectable en el conjunto de no unidades positivas divisibles como máximo por $1$ de primera clase.

A continuación, supongamos que la función $x \mapsto x \phi (x)$ es inyectada en el set $S_k$ de no unidades positivas divisibles como máximo por $k$ primos. Deje que $x,y$ ser positivo no unidades divisibles por a lo sumo $k +1$ primos tales que $x \phi (x) = y \phi (y).$ Luego $x = x_0p^n$ y $y= y_0q^m$ donde $x_0,y_0 \in S_k,$ $p$ y $q$ son los primos más grandes que dividen $x$ y $y,$ respectivamente, y $(x_0,p) = 1 =(y_0, q).$ Por lo tanto, $p$ y $q$ son los primos más grandes que dividen $x \phi (x)$ y $y \phi (y);$ sigue $p =q.$

Por lo tanto,

\begin {alineado*} x_0 \phi (x_0)q^{2n -1}(q-1) & = x_0 \phi (x_0)q^n \phi (q^n) \\ &= x_0q^n \phi (x_0q^n) \\ &= x \phi (x) \\ &= y \phi (y) \\ &= y_0 \phi (y_0)q^{2m -1}(q-1). \end {alineado*}

Como cualquier división primaria $x_0$ o $y_0$ es estrictamente menor que $q,$ la primera $q$ no divide $x_0 \phi (x_0)$ o $y_0 \phi (y_0).$ De ello se deduce que el exponente de $q$ en ambos lados de la igualdad es $2m -1 = 2n -1.$ Por lo tanto, $n = m.$ Dividiendo ambos lados por $q^n \phi (q^n).$ Obtenemos $x_0 \phi (x_0) = y_0 \phi (y_0)$ lo que implica $x_0 = y_0$ por la hipótesis de la inducción. Se sigue

$$x = x_0p^n = y_0q^m = y,$$

y la reclamación sigue por inducción.