Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
3  
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
1  
@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

2 Answers 2

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}$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.