Thread: A pretty good challenge View Single Post
2021-05-08, 02:18   #2
Dr Sardonicus

Feb 2017
Nowhere

12D016 Posts

Quote:
 Originally Posted by Charles Kusniec A PGC (pretty good challenge). Given: x=(y^2-(n^2-n))/(2n-1)=(y^2-Oblong)/Odd To prove, 1. If n>0, there will be Integer solution for x iff (2n-1) are the numbers that are divisible only by primes congruent to 1 mod 4 (http://oeis.org/A004613, https://oeis.org/A008846, https://oeis.org/A020882). 2. If n≤0, there will be Integer solution for x iff n=-|2m| negative Even (negative sequence https://oeis.org/A226485, or twice the negative sequence http://oeis.org/A094178).
(y^2 - (n^2 - n))/(2*n - 1) is an integer when

n^2 - n == y^2 (mod 2*n-1)

4*n^2 - 4*n == 4*y^2 (mod 2*n - 1)

(2*n - 1)^2 == 4*y^2 +1 (mod 2*n - 1)

4*y^2 + 1 == 0 (mod 2*n - 1); that is,

2*n - 1 divides 4*y^2 + 1

Since 4*y^2 + 1 is divisible only by primes congruent to 1 (mod 4), the same is true of its divisor 2*n - 1. This solves (1) straightaway.

If n = 0, we have y^2 == 0 (mod 1) which is trivial.

If n < 0, we have that 2*|n| + 1 divides 4*y^2 + 1. This implies all divisors of 2*|n| + 1 are congruent to 1 (mod 4), so that n is even, solving (2) in the formulation of the second OEIS sequence.

Multiplying the congruence through by 4 is allowed, since 4 is relatively prime to 2*n - 1.

Last fiddled with by Dr Sardonicus on 2021-05-08 at 02:21 Reason: Add justification for multiplying congruence by 4