# Division into $x(x-1)$

All variables involved are nonnegative integers.

Given a variable $g$, what is the largest $x$ where $g$ cleanly divides $x(x-1)$ and $x\lt g$? Do I only need prime factors of $g$?

-
If $g$ is a prime, then $x=1$. –  user17762 Dec 23 '12 at 21:30
<del>Also $g$ must be even...otherwise no such integer $x$ exists. So therefore $g\gt 2$, thanks to @Marvis' observation.</del> This is wrong, thanks to a simple counter-example $g=15$, $x=6$ (thanks @Marvis!). –  Alex Nelson Dec 23 '12 at 21:31
@AlexNelson Not necessarily. $g = 15$, $x=6, 10$. –  user17762 Dec 23 '12 at 21:32
Ah yes, well played, @Marvis! –  Alex Nelson Dec 23 '12 at 21:32
@Tomasz but $g=4$ doesn't cleanly divide $3(3-1)=6$ for $x=3$... –  Alex Nelson Dec 23 '12 at 21:55

For each prime $p$ dividing $g$, with $p^d$ the largest power of $p$ dividing $g$, we need either $p^d | x$ or $p^d | x - 1$. Thus we can write $g = u v$ where $\gcd(u,v) = 1$, $u | x$ and $v | x-1$. Say $x = u w$. Since $x < g$ we must have $w < v$. Now $u w \equiv 1 \mod v$, i.e. $w \equiv u^{-1} \mod v$. Thus here is a Maple program to find $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;


The first 30 values ($g = 1$ to $30$) are

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

It doesn't appear to be in the OEIS yet.

-
There is general theory that can be useful here. To make things simpler let $g$ be odd. We want to solve $x(x-1)\equiv 0\pmod{g}$, where there are some restrictions on $x$. So we would like to have $x^2-x\equiv 0\pmod{g}$, or equivalently $$4x^2-4x\equiv 0\pmod{g}.$$ Complete the square. We want to solve $$(2x-1)^2\equiv 1\pmod{g}.$$ Express $g$ as a product $p_0^{a_0}p_1^{a_1}\cdots p_k^{a_k}$ of prime powers. Now find $y_i$ such that $y_i\equiv \pm 1\pmod{p_i^{a_i}}$. If $g$ is not a prime power, we can always find a non-trivial solution where not all the $y_i$ are congruent to $1$ modulo $p_i^{a_i}$, and not all the $y_i$ are congruent to $-1$ modulo $p_i^{a_i}$. Then we find $x_i$ such that $2x_i-1\equiv y_i\pmod{p_i^{a_i}}$, and use the Chinese Remainder Theorem to construct the appropriate $x$.
With some care, the idea can be used for even $g$, by considering the congruence $(2x-1)^2\equiv 1\pmod{4g}$.