mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)
-   -   A pretty good challenge (https://www.mersenneforum.org/showthread.php?t=26781)

 Charles Kusniec 2021-05-08 00:09

A pretty good challenge

1 Attachment(s)
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 ([url]http://oeis.org/A004613[/url], [url]https://oeis.org/A008846[/url], [url]https://oeis.org/A020882[/url]).

2. If n≤0, there will be Integer solution for x iff n=-|2m| negative Even (negative sequence [url]https://oeis.org/A226485[/url], or twice the negative sequence [url]http://oeis.org/A094178[/url]).

 Dr Sardonicus 2021-05-08 02:18

[QUOTE=Charles Kusniec;577933]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 ([url]http://oeis.org/A004613[/url], [url]https://oeis.org/A008846[/url], [url]https://oeis.org/A020882[/url]).

2. If n≤0, there will be Integer solution for x iff n=-|2m| negative Even (negative sequence [url]https://oeis.org/A226485[/url], or twice the negative sequence [url]http://oeis.org/A094178[/url]).[/QUOTE](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) [sup]†[/sup]

(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.

[sup]†[/sup]Multiplying the congruence through by 4 is allowed, since 4 is relatively prime to 2*n - 1.

 Charles Kusniec 2021-05-08 10:38

Dear Dr Sardonicus, I read your proof and found no fault. Apparently it is perfect. Congratulations. I think the way I asked already giving the answers helped. Now, the challenge is to find at least one other form of proof where you use the sum of two squares theorem. A very interesting surprise will appear, and that is the only hint for now.

 Dr Sardonicus 2021-05-08 13:37

[QUOTE=Charles Kusniec;577969]Now, the challenge is to find at least one other form of proof where you use the sum of two squares theorem.[/QUOTE]I forgot to point out that the thing is also trivial when n = 1, y^2 = 0 (mod 1).

What I proved was that your given hypotheses imply that

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

2*|n| + 1 divides 4*y^2 + 1, if n < 0.

The fact that every prime divisor p of 4*y^2 + 1 is congruent to 1 (mod 4) is elementary, and does not require the two-squares theorem. Using Fermat's "little theorem,"

p divides (2*y)^(p-1) - 1. From the above,

p divides (2*y)^4 - 1, but p does [i]not[/i] divide (2*y)^2 - 1.

Therefore, 2*y has multiplicative order 4 (mod p), from which it follows that p-1 is divisible by 4.

 Charles Kusniec 2021-05-08 13:46

Actually, we have 2 trivialities for n. We have n=0 and n=1 as trivialities. I agree with what you said. What I am complementing is that there is another way to do this proof and in it we have to use the sum of 2 squares theorem. When we do the proof by this second way, we find a very interesting equality.

 a1call 2021-05-08 15:52

Nice.
A numeric example for 2n-1 = 65:

[url]https://www.wolframalpha.com/input/?i=y%3D%28x%5E2-%28%28%2865%2B1%29%2F2%29%5E2-%28%2865%2B1%29%2F2%29%29%29%2F65+solve+for+over+the+integer[/url]

ETA:
No solutions for 2n-1 = 21 even though it is of the form 4m+1 since it has at least one prime factor of the form 2m+1 with odd m:

[url]https://www.wolframalpha.com/input/?i=y%3D%28x%5E2-%28%28%2821%2B1%29%2F2%29%5E2-%28%2821%2B1%29%2F2%29%29%29%2F21+solve+for+over+the+integer[/url]

 Charles Kusniec 2021-05-08 16:50

Dear a1call,

Thanks for the example.

I like you used 65 as an example, because this is one of those cases of multiplicity of primitive Pythagorean triangle.

At 65, we have 2 solutions because we have 2 ways to make the Pythagorean triangle.

That’s why I don’t really like how WolframAlpha and many others present this kind of solution.

The way they present it looks like we have 4 sequences of solutions, when in fact, we only have 2 sequences.

They should present only the sequences a(n) = 65 n^2 +- 8 n - 16 and a(n) = 65 n^2 +- 18 n - 15. These two sequences are at offset Zero.

For more details about offset I have a study that explains well this phenomenon...

 All times are UTC. The time now is 10:11.