El número de combinaciones $(a,b) \in \mathbb{Z}_n \times \mathbb{Z}_n$ tal que $a \cdot b = 0$

Question

Esta pregunta es acerca de un anillo para algunos escogidos $n \in \mathbb{N}$

Yo quería encontrar el número de $M_n$ de las combinaciones de $(a,b) \in \mathbb{Z}_n \times \mathbb{Z}_n$ se puede encontrar tal que $a \cdot b = 0$$a\neq 0 \neq b$. Esperaba encontrar una fórmula que funciona para cualquier $n \in \mathbb{N}$, de manera que podemos maximizar el cociente $\frac{M_n}{n}$

---

Lo que yo hice

Primero de todo, podemos encontrar un atado de una manera muy brusca, a saber. $$ (n - \phi(n))^2 \quad = \quad n^2 \left(1 - \prod_{p |n}(1-\frac 1p) \right) $$ Otra cosa que he pensado es que si $(a,b)$ es una combinación, entonces también tenemos: $$ (a,-b) \ , \ (-a,b) \ , \ (-a,-b) \ , \ (b,a) \ , \ (b,-a) \ , \ (-b,a) \ , \ (-b,-a) $$ De manera que cada par nos íbamos a encontrar daría un conjunto de en la mayoría de los otros siete pares.

Si queremos contar en el más sencillo, creo que un cero divisor $a$, y buscar un valor de $b$ tal que $a\cdot b = 0$. Pero si queremos encontrar los valores de $b$, tenemos que hacer uso de la factorización en números primos de $n$.

---

Yo podría usar su ayuda. (Si usted quiere que yo trate de hacer de la I gran fórmula de lo que podría ser el número de la combinación busco, dime por favor. Pensé que sería inútil aquí.)

Answer 1

Cada $a \in \mathbb Z_n$, $a \cdot b = 0 \iff ab \equiv 0 \pmod n$ %. Esto ocurrirá exactamente cuando $$\frac n {(a,n)} \big\vert\ b$$which can happen exactly $\big ((a,n)-1\big) $ times: since we must have $0 < b < n $, possible values for $b $ are $% $ $\frac{n}{(a,n)},\frac{2n}{(a,n)},\frac{3n}{(a,n)},\ldots,\frac{\big((a,n)-1\big)n}{(a,n)}$

Por lo tanto, usted está buscando para calcular $$\sum_{a=1}^{n-1}\big((a,n)-1\big)=\operatorname P(n)-(2n-1)$ $ $\operatorname P(n)=\displaystyle\sum_{a=1}^n\operatorname{gcd}(a,n)$ Dónde está la función aritmética de Pillai.