División en $x(x-1)$

Question

Todas las variables implicadas son números enteros no negativos.

Dada una variable $g$ ¿Cuál es la mayor $x$ donde $g$ divide limpiamente $x(x-1)$ y $x\lt g$ ? ¿Sólo necesito factores primos de $g$ ?

Answer 1

Para cada primo $p$ dividiendo $g$ con $p^d$ la mayor potencia de $p$ dividiendo $g$ necesitamos $p^d | x$ o $p^d | x - 1$ . Así, podemos escribir $g = u v$ donde $\gcd(u,v) = 1$ , $u | x$ y $v | x-1$ . Diga $x = u w$ . Desde $x < g$ debemos tener $w < v$ . Ahora $u w \equiv 1 \mod v$ es decir $w \equiv u^{-1} \mod v$ . He aquí un programa Maple para encontrar $x$ .

xmax := proc (g::posint) 
   max(map(u -> u*modp(1/u,g/u),
                  map(t -> mul(s[1]^s[2],s = t),
                      combinat[powerset](ifactors(g)[2])))) 
end proc;

Los 30 primeros valores ( $g = 1$ a $30$ ) son

0, 1, 1, 1, 1, 4, 1, 1, 1, 6, 1, 9, 1, 8, 10, 1, 1, 10, 1, 16, 15, 12, 1, 16, 1, 14, 1, 21, 1, 25

Parece que aún no está en la OEIS.

Answer 2

Hay una teoría general que puede ser útil en este caso. Para simplificar las cosas $g$ ser impar. Queremos resolver $x(x-1)\equiv 0\pmod{g}$ donde hay algunas restricciones sobre $x$ . Así que nos gustaría tener $x^2-x\equiv 0\pmod{g}$ o, de forma equivalente $$4x^2-4x\equiv 0\pmod{g}.$$ Completa el cuadrado. Queremos resolver $$(2x-1)^2\equiv 1\pmod{g}.$$ Express $g$ como producto $p_0^{a_0}p_1^{a_1}\cdots p_k^{a_k}$ de las primeras potencias. Ahora halle $y_i$ tal que $y_i\equiv \pm 1\pmod{p_i^{a_i}}$ . Si $g$ no es una potencia prima, siempre podemos encontrar una solución no trivial en la que no todas las $y_i$ son congruentes con $1$ modulo $p_i^{a_i}$ y no todos los $y_i$ son congruentes con $-1$ modulo $p_i^{a_i}$ . Entonces encontramos $x_i$ tal que $2x_i-1\equiv y_i\pmod{p_i^{a_i}}$ y utilizar el Teorema del Resto Chino para construir el $x$ .

Con un poco de cuidado, la idea puede utilizarse incluso para $g$ considerando la congruencia $(2x-1)^2\equiv 1\pmod{4g}$ .