Un enfoque de teoría numérica (algorítmica):
Ignoraré las restricciones [matemáticas] a \ leq b [/ matemáticas] y [matemáticas] a, b, c> 0 [/ matemáticas] ya que si obtenemos las soluciones sin ellas, podemos eliminar fácilmente las soluciones que no satisfacen ellos.
1 – Problema
En primer lugar, definamos [matemática] F (n) [/ matemática] como el número de módulos triples pitagóricos [matemática] n [/ matemática], es decir, en [matemática] Z_n [/ matemática]. En otras palabras, el número de soluciones a la ecuación:
[matemáticas] a ^ 2 + b ^ 2 \ equiv c ^ 2 (mod n) [/ matemáticas]
2 – Reducción del problema a [matemáticas] Z_ {p ^ k} [/ matemáticas]
Comenzamos usando el Teorema del resto chino para reducir el problema de contar triples pitagóricos en [matemáticas] Z_n [/ matemáticas] al problema de contar triples pitagóricos en [matemáticas] Z_ {p ^ k} [/ matemáticas], para algunos números primos [matemáticas] p [/ matemáticas] y enteros positivos [matemáticas] k [/ matemáticas].
- Física: ¿Cómo se desvanece el pseudo tensor de Einstein [matemáticas] t_u {} ^ v [/ matemáticas] en la solución de Schwarzschild?
- Dado N, ¿cuál es el valor de [matemáticas] \ sum_ {k = 1} ^ {N} \ frac {k} {gcd (k, N)} [/ matemáticas]?
- ¿Cuántos conjuntos de dos factores de N = 360 serán coprimos entre sí?
- ¿Cómo explicarías la hipótesis de Riemann y la función zeta como lo harías con un estudiante de décimo grado?
- ¿La divisibilidad se define solo para enteros o también se define para racionales e irracionales?
Deje que [math] n = p_1 ^ {e_1}… p_r ^ {e_r} [/ math] sea la descomposición principal de [math] n [/ math], con [math] p_i \ ne p_j \ forall i, j [/ matemáticas]. Tenemos:
- [matemáticas] F (n) = \ prod_ {i = 1} ^ r F (p_i ^ {e_i}) [/ matemáticas]
3 – Contando en [matemáticas] Z_ {p ^ k} [/ matemáticas]
Para contar los triples pitagóricos en [matemáticas] Z_ {p ^ k} [/ matemáticas] procederemos utilizando el análisis de casos. Comencemos por definir [math] qr (i) [/ math] como el número de residuos cuadráticos congruentes con [math] i [/ math] módulo [math] p ^ k [/ math].
3.1 – Caso # 1: [matemática] a \ en Z_ {p ^ k} ^ * [/ matemática]
Comenzamos con:
- [matemáticas] a ^ 2 + b ^ 2 \ equiv c ^ 2 (mod p ^ k) [/ matemáticas]
Porque [matemática] a \ en Z_ {p ^ k} ^ * [/ matemática] obtenemos:
- [matemáticas] (\ frac {a} {a}) ^ 2 + (\ frac {b} {a}) ^ 2 \ equiv (\ frac {c} {a}) ^ 2 (mod p ^ k) [/ matemáticas]
Al usar [math] X = \ frac {b} {a} [/ math] y [math] Y = \ frac {c} {a} [/ math] obtenemos:
- [matemáticas] 1 + X ^ 2 \ equiv Y ^ 2 (mod p ^ k) [/ matemáticas]
Y obtenemos el número de soluciones con [math] a \ en Z_ {p ^ k} ^ * [/ math]:
- [matemáticas] \ sum_ {i = 0} ^ {p ^ k – 1} qr (i) * qr ((i + 1) \% p ^ k) * (p ^ k – p ^ {k – 1}) [/matemáticas]
Tenga en cuenta que [matemática] i [/ matemática] representa [matemática] X ^ 2 [/ matemática], [matemática] i + 1 [/ matemática] representa [matemática] Y ^ 2 [/ matemática] y necesitamos multiplicar por [ math] (p ^ k – p ^ {k – 1}) [/ math] que son el número de posibilidades para [math] a [/ math].
3.2 – Caso # 2: [matemáticas] a \ notin Z_ {p ^ k} ^ *, b \ en Z_ {p ^ k} ^ * [/ matemáticas]
Comenzamos con:
- [matemáticas] a ^ 2 + b ^ 2 \ equiv c ^ 2 (mod p ^ k) [/ matemáticas]
Porque [matemáticas] b \ en Z_ {p ^ k} ^ * [/ matemáticas] obtenemos:
- [matemáticas] (\ frac {a} {b}) ^ 2 + (\ frac {b} {b}) ^ 2 \ equiv (\ frac {c} {b}) ^ 2 (mod p ^ k) [/ matemáticas]
Al usar [math] X = \ frac {a} {b} [/ math] y [math] Y = \ frac {c} {b} [/ math] obtenemos:
- [matemáticas] X ^ 2 + 1 \ equiv Y ^ 2 (mod p ^ k) [/ matemáticas]
Y obtenemos el número de soluciones con [math] a \ notin Z_ {p ^ k} ^ *, b \ in Z_ {p ^ k} ^ * [/ math]:
- [matemáticas] \ sum_ {i = 0} ^ {p ^ {k – 1} – 1} qr (p * i) * qr ((p * i + 1) \% p ^ k) * (p ^ k – p ^ {k – 1}) [/ matemáticas]
Tenga en cuenta que [matemática] p * i [/ matemática] representa [matemática] X ^ 2 [/ matemática], [matemática] p * i + 1 [/ matemática] representa [matemática] Y ^ 2 [/ matemática] y necesitamos multiplicar por [matemáticas] (p ^ k – p ^ {k – 1}) [/ matemáticas], que son el número de posibilidades para [matemáticas] b [/ matemáticas].
3.3 – Caso # 3: [matemáticas] a, b \ notin Z_ {p ^ k} ^ *, c \ en Z_ {p ^ k} ^ * [/ matemáticas]
Esto no es realmente un caso ya que [math] a, b \ notin Z_ {p ^ k} ^ * [/ math] implica [math] c \ notin Z_ {p ^ k} ^ * [/ math].
3.4 – Caso # 4: [matemáticas] a, b, c \ notin Z_ {p ^ k} ^ * [/ matemáticas]
Dado que [matemática] a, b, c \ notin Z_ {p ^ k} ^ * [/ matemática] implica que [matemática] a = pa ‘, b = pb’, c = pc ‘[/ matemática]. Además, podemos escribir: [matemáticas] a ‘= \ alpha * p ^ {k – 2} + \ alpha’, b ‘= \ beta * p ^ {k – 2} + \ beta’, c ‘= \ delta * p ^ {k – 2} + \ delta ‘[/ math].
Ahora demostramos que [matemática] a, b, c [/ matemática] es una solución en [matemática] Z_ {p ^ k} [/ matemática] si y solo si [matemática] \ alpha ‘, \ beta’, \ delta ‘[/ math] es una solución en [math] Z_ {p ^ {k – 2}} [/ math]:
- [matemáticas] a ^ 2 + b ^ 2 \ equiv c ^ 2 (mod p ^ k) [/ matemáticas]
- [matemática] \ Leftrightarrow (pa ‘) ^ 2 + (pb’) ^ 2 \ equiv (pc ‘) ^ 2 (mod p ^ k) [/ math]
- [math] \ Leftrightarrow (pa ‘) ^ 2 + (pb’) ^ 2 – (pc ‘) ^ 2 \ equiv 0 (mod p ^ k) [/ math]
- [Matemáticas] \ Leftrightarrow p ^ 2 * (a ‘^ 2 + b’ ^ 2 – c ‘^ 2) \ equiv 0 (mod p ^ k) [/ math]
- [matemáticas] \ Leftrightarrow p ^ 2 * (a ‘^ 2 + b’ ^ 2 – c ‘^ 2) = \ phi * p ^ k [/ math]
- [matemática] \ Leftrightarrow (a ‘^ 2 + b’ ^ 2 – c ‘^ 2) = \ phi * p ^ {k – 2} [/ math]
- [matemáticas] \ Leftrightarrow a ‘^ 2 + b’ ^ 2 – c ‘^ 2 \ equiv 0 (mod p ^ {k – 2}) [/ math]
- [matemáticas] \ Leftrightarrow (\ alpha * p ^ {k – 2} + \ alpha ‘) ^ 2 + (\ beta * p ^ {k – 2} + \ beta’) ^ 2 – (\ delta * p ^ { k – 2} + \ delta ‘) ^ 2 \ equiv 0 (mod p ^ {k – 2}) [/ math]
- [matemática] \ Leftrightarrow \ alpha ‘^ 2 + \ beta’ ^ 2 – \ delta ‘^ 2 \ equiv 0 (mod p ^ {k – 2}) [/ math]
- [matemáticas] \ Leftrightarrow \ alpha ‘^ 2 + \ beta’ ^ 2 \ equiv \ delta ‘^ 2 (mod p ^ {k – 2}) [/ math]
Y obtenemos el número de soluciones con [matemáticas] a, b, c \ notin Z_ {p ^ k} ^ * [/ matemáticas]:
- [matemáticas] F (p ^ {k – 2}) * p ^ 3 [/ matemáticas]
Todavía no hemos terminado ya que faltan los casos base.
Tenemos [matemáticas] F (p ^ 1) = F (p) = p ^ 2 [/ matemáticas] por Jacobi Sums (consulte [1] para una prueba de esto) y [matemáticas] F (p ^ 0) = F (1) = 1 [/ math], que es la solución trivial solamente.
4 – Resultado
Después de analizar todos los casos obtenemos:
- [matemáticas] F (p ^ 0) = 1 [/ matemáticas]
- [matemáticas] F (p ^ 1) = p ^ 2 [/ matemáticas]
- [matemáticas] F (p ^ k) = \ sum_ {i = 0} ^ {p ^ k – 1} qr (i) * qr ((i + 1) \% p ^ k) * (p ^ k – p ^ {k – 1}) + \ sum_ {i = 0} ^ {p ^ {k – 1} – 1} qr (p * i) * qr ((p * i + 1) \% p ^ k) * (p ^ k – p ^ {k – 1}) + F (p ^ {k – 2}) * p ^ 3 [/ matemáticas]
- [matemáticas] F (n) = \ prod_ {i = 1} ^ r F (p_i ^ {e_i}) [/ matemáticas]
5 – Análisis de complejidad
En primer lugar, debemos considerar la complejidad para factorizar [matemáticas] n [/ matemáticas], que necesitamos para reducir el problema de [matemáticas] Z_n [/ matemáticas] a [matemáticas] Z_ {p ^ k} [/ matemáticas]. Se puede hacer en [math] \ mathcal {O} (\ sqrt {n} * \ log {} n) [/ math].
Luego consideramos el tiempo para resolver el problema en [math] Z_ {p ^ k} [/ math], que es [math] \ mathcal {O} (n) [/ math].
Entonces, tenemos una complejidad de tiempo de [math] \ mathcal {O} (n) [/ math] y una complejidad espacial de [math] \ mathcal {O} (n) [/ math] ya que solo necesitamos calcular [matemáticas] qr [/ matemáticas].
6 – Implementación
Una implementación en C ++:
#include
#define X primero
#definir Y segundo
#define MAX_N 600000
usando el espacio de nombres estándar;
typedef long long int lld;
typedef par pii;
typedef vector vpii;
int qr [MAX_N];
int fastexp (int b, int e) {
int res = 1;
mientras que (e) {
si (e & 1)
res * = b;
e >> = 1;
b * = b;
}
volver res;
}
vpii factorizar (int n) {
factores vpii;
para (int p = 2; p * p <= n; p ++)
if (n% p == 0) {
int e = 0;
mientras que (n% p == 0)
e ++, n / = p;
factores.push_back (pii (p, e));
}
si (n! = 1)
factores.push_back (pii (n, 1));
factores de retorno;
}
vacío compute_qr (int P) {
memset (qr, 0, sizeof (qr));
para (int i = 0; i <P; i ++)
qr [(lld) (i * i)% P] ++;
}
lld count (int p, int e) {
if (e == 0) devuelve 1;
if (e == 1) return (p * p);
int P = fastexp (p, e);
compute_qr (P);
// un invertible
lld res1 = 0;
para (int i = 0; i <P; i ++)
res1 + = qr [i] * qr [(i + 1)% P];
res1 * = P - (P / p);
// a no invertible, b invertible
lld res2 = 0;
para (int i = 0; i c no invertible
// lld res3 = 0;
// a, b, c no invertible
lld res4 = cuenta (p, e - 2) * (p * p * p);
return (res1 + res2 + res4);
}
lld resolver (int n) {
lld res = 1;
factores vpii = factorizar (n);
para (int i = 0; i <(int) factor.size (); i ++)
res * = cuenta (factores [i] .X, factores [i] .Y);
volver res;
}
int main (int argc, char ** argv) {
int n;
while (scanf ("% d", & n)! = EOF)
printf ("% lld \ n", resolver (n));
devuelve 0;
}
Referencias
[1] K. Ireland y M. Rosen, “Una introducción clásica a la teoría moderna de números”