Demostrar que una función es multiplicativa.

Question

Deje $f(x)$ ser un polinomio con coeficientes enteros, y deje $\psi(n)$ denotar el número de valores de $f(0), f(1), ..., f(n-1)$ cuales son coprime a $n$.

Debo mostrar que $\psi$ es multiplicativo, en el sentido que: $$\psi(mn) = \psi(m) \cdot \psi(n)$$ asumiendo $\gcd(m,n)=1$.

Además, me debe demostrar que $$\psi(p^\alpha) = p^{\alpha-1} \cdot (p-b_p)$$ donde $b_p$ es el número de enteros $f(0), f(1), ..., f(p-1)$ que son divisibles por el primer $p$.

Pensé que esta prueba sería similar a la prueba de la multiplicidad de Euler totient función, pero no he sido capaz de hacer la conexión. Creo que una vez que se encuentra una prueba de la primera parte, tal vez voy a ser capaz de entender mejor la segunda parte. Cualquier ayuda es muy apreciada.

Answer 1

Empezamos con un lexema.

Lema: Vamos a $p$ ser un número primo. A continuación, para cada $f(x)\in \mathbb{Z}[x]$ y $k\in \mathbb{Z}$ $$f(p+k)\equiv f(k) \pmod p.$$

Prueba: supongamos que $f(x)=c_{0}x^n+\ldots +c_{1}x+c_{n}$, $$f(p+k)=c_{0}(p+k)^n+\ldots c_{1}(p+k)+c_{n}\equiv c_{0}k^n+\ldots c_{1}k+c_{n}=f(k) \pmod p. \tag*{$\blacksquare$}$$

En primer lugar, echemos $n=p^a$, podemos hacer $p^a/p=p^{a-1}$ grupos de $p$ elementos del conjunto $\{f(0), f(1),\ldots, f(p-1), f(p),\ldots, f(2p-1),\ldots, f(p^a-p),\ldots, f(p^a-1)\}$. Por el lema de que cada grupo ha $b_{p}$ números que son divisibles por $p$. Entonces, en total tenemos $p^a-p^{a-1}\cdot b_{p}=p^{a-1}(p-b_{p})$ números que no son divisibles por $p$, es decir, coprime con $p^a$. Por eso, $\psi(p^a)=p^{a-1}(p-b_{p})$.

Ahora, supongamos que $n=p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}$, la idea es aplicar el anterior razonamiento para cada factor primordial $p_{i}$, pero a fin de evitar repeticiones, es decir, números que son múltiples de más de un factor primo, te sucesivamente se resta de la cantidad de $p_{i}$, a partir de con $p_{1}$.

Set $n=n_{0}$, y recoger $p_{1}$, el número de múltiplos de $p_{1}$ es $$m_{1}=(p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}/p_{1})\cdot b_{p_{1}}=p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}}b_{p_{1}},$$ then we put $n_{1}=n_{0}-m_{1}=p_{1}^{a_{1}}\cdots p_{r}^{a_{r}}-p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}}b_{p_{1}}=p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}}(p_{1}-b_{p_{1}})$.

Ahora, para $n_{1}$ contamos el número de múltiplos de $p_{2}$. Como en el caso de $p_{1}$ tenemos $m_{2}=p_{1}^{a_{1}-1}p_{2}^{a_{2}-1}\cdots p_{r}^{a_{r}}(p-b_{p_{1}})b_{p_{2}}$, y por lo tanto $$n_{2}=n_{1}-m_{2}=p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}}(p-b_{p})-p_{1}^{a_{1}-1}p_{2}^{a_{2}-1}\cdots p_{r}^{a_{r}}(p-b_{p_{1}})b_{p_{2}}=$$ $$p_{1}^{a_{1}-1}p_{2}^{a_{2}-1}\cdots p_{r}^{a_{r}}(p-b_{p_{1}})(p_{2}-b_{p_{2}}).$$

Después de aplicar el mismo proceso de $r-2$ más de veces, podemos deducir que $$\psi(n)=n_{r}=n_{r-1}-m_{r}=$$ $$=p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}}(p_{1}-b_{p_{1}})\ldots (p_{r-1}-b_{p_{r-1}})-p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}-1}(p_{1}-b_{p_{1}})\ldots (p_{r-1}-b_{p_{r-1}})b_{p_{r}}=$$ $$=p_{1}^{a_{1}-1}\cdots p_{r}^{a_{r}-1}(p_{1}-b_{p_{1}})\ldots (p_{r}-b_{p_{r}}).$$

Por último, la aplicación de la última fórmula es fácil deducir que si $\gcd(m,n)=1$, $$\psi(mn)=\psi(m)\psi(n).$ $

Nota: Si el proceso no es muy clara, recomendamos aplicar a $n=30$.

Answer 2

Sugerencia:

Utilice el hecho de que $\psi(m)$ es igual a la cantidad de unidades en el grupo multiplicativo $Z_m^{\times}$ $|Z_m^{\times}|=m$. Desde $m$ y $n$ son coprimos, $ Z_ {mn} ^ {\times} \cong Z_m ^ {\times} \times Z_n ^ {\times} $. Por lo tanto hay $ \psi(mn)=\psi(m)\psi(n)$.