gordonm888 Joined: Feb 18, 2015
• Posts: 2859
September 10th, 2019 at 2:55:32 PM permalink
I have noticed the following:

No integer congruent with 7(mod 8) is ever a factor/divisor of any number n2+2.

For example, 7, 15 and 23 are each congruent with 7(mod 8) but they are not a factor/divisor of any value of n2+2: 3, 6, 11, 18, 27, 38, 51, 66, 83, 102, 123, 146, 171, 198, 227, 258, 291 . . . . 4016018, 4020027 . . .

I have been fooling around with modular math, and its pretty clear that for all possible values of n that n2+2 is always congruent with 2,3 or 6 (mod 8). But I can't see the reason why a number that is 7(mod 8) -which also can be written as -1(mod 8) - can't be a factor/divisor of a number that is 2,3 or 6 (mod 8)

So, I'm stuck. I don't know enough modular arithmetic, I guess. Can anyone help with this?
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
kubikulann Joined: Jun 28, 2011
• Posts: 905
September 10th, 2019 at 3:08:14 PM permalink
Not thought about your question, but it reminds me of a result I encountered recently:
All integers are the sum of three squares, except those congruent to 7(mod 8).

Reperiet qui quaesiverit
gordonm888 Joined: Feb 18, 2015
• Posts: 2859
September 10th, 2019 at 4:54:12 PM permalink
Yes,you remind me that I've read that 7(mod 8) integers are the sum of four squares. Weird.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
kubikulann Joined: Jun 28, 2011
• Posts: 905
Thanks for this post from: September 11th, 2019 at 5:19:08 AM permalink
As n2+2 = n2+1+1 is the sum of three squares, it cannot be =7(mod8).

But that doesn�t say anything about its factors. For exemple, 2*(8+7)=30=25+4+1 : m*(8x+7) must be the sum of three squares if m is not 4k (and cannot be if m= 4k).

Are you sure about the original assertion or is it a conjecture?
Last edited by: kubikulann on Sep 11, 2019
Reperiet qui quaesiverit
kubikulann Joined: Jun 28, 2011
• Posts: 905
Thanks for this post from: September 11th, 2019 at 6:43:37 AM permalink
Looking for an integer n such that n2+2 equals (8a+7)(8b+c).
Defining n = 8u+v we have the following constraints modulo 8:
vn2+2c
0,426
1,3,5,735
2,662

64u2+16uv+v2+2 = 64ab+8(ac+7b)+7c
vv2+27cdiff7b+ac=8(u2-ab)+2uv+diff/8
0242-408(u2-ab)-5
1335-328(u2-ab)+2u-4
261488(u2-ab)+4u+1
31135248(u2-ab)+6u+3
41842248(u2-ab)+8u+3
5273588(u2-ab)+10u+1
63814-248(u2-ab)+12u-3
75135-168(u2-ab)+14u-2

Or, modulo 8,
v7b+ac=
07b+6a-5
17b+5a2u-4
27b+2a4u+1
37b+5a6u+3
47b+6a+3
57b+5a2u+1
67b+2a4u-3
77b+5a6u-2

Alas, these are necessary Conditions, not sufficient. For ex., third line v=2, a=1 b=1 u=2 fills the modulo condition, but it gives n=18 -> n2+2=326, which is not equal to (15)*(10).

What is left to do is:
Gather all triplets (u,a,b) respecting the necessary condition ;
Then
either prove that it is impossible to respect the 2d table condition,
Or find an example, which makes the original assumption false.
Reperiet qui quaesiverit
gordonm888 Joined: Feb 18, 2015
• Posts: 2859
September 11th, 2019 at 12:00:32 PM permalink
Quote: kubikulann

As n2+2 = n2+1+1 is the sum of three squares, it cannot be =7(mod8).

But that doesn�t say anything about its factors. For exemple, 2*(8+7)=30=25+4+1 : m*(8x+7) must be the sum of three squares if m is not 4k (and cannot be if m= 4k).

Are you sure about the original assertion or is it a conjecture?

It is a conjecture, based on >20,000 trials.

Thanks for looking at this, I am reading everything you post.
Last edited by: gordonm888 on Sep 11, 2019
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
gordonm888 Joined: Feb 18, 2015
• Posts: 2859
September 11th, 2019 at 12:49:08 PM permalink
Quote: kubikulann

Looking for an integer n such that n2+2 equals (8a+7)(8b+c).
Defining n = 8u+v we have the following constraints modulo 8:

vn2+2c
0,426
1,3,5,735
2,662

64u2+16uv+v2+2 = 64ab+8(ac+7b)+7c
vv2+27cdiff7b+ac=8(u2-ab)+2uv+diff/8
0242-408(u2-ab)-5
1335-328(u2-ab)+2u-4
261488(u2-ab)+4u+1
31135248(u2-ab)+6u+3
41842248(u2-ab)+8u+3
5273588(u2-ab)+10u+1
63814-248(u2-ab)+12u-3
75135-168(u2-ab)+14u-2

Or, modulo 8,
v7b+ac=
07b+6a-5
17b+5a2u-4
27b+2a4u+1
37b+5a6u+3
47b+6a+3
57b+5a2u+1
67b+2a4u-3
77b+5a6u-2

Alas, these are necessary Conditions, not sufficient. For ex., third line v=2, a=1 b=1 u=2 fills the modulo condition, but it gives n=18 -> n2+2=326, which is not equal to (15)*(10).

What is left to do is:
Gather all triplets (u,a,b) respecting the necessary condition ;
Then
either prove that it is impossible to respect the 2d table condition,
Or find an example, which makes the original assumption false.

Wow! Wow! I am VERY impressed. Okay, my head is exploding, but after studying it, I have followed this through and understand the point you are at. For each of the eight possible pairs of (v, c) as defined by the 1st table, it is necessary to define triplets (u,a,b) that satisfy the v-dependent modulo conditions of the last table and either find an example for which (8u+v)2 +2 = (8a+7)*(8b+c) or show algebraicly that it can't be solved.

Are a and b allowed to be negative? If not, then there is no possible (u,a,b) triplet that satisfies the modulo conditions for v=0. Or for v=4.

EDIT: My general impression is that, always, u>b and u>a. Therefore, it seems that (8u+v)2 is always greater than (8a+7)*(8b+c).

But why? If we had done this for 1,3,5(mod 8) we should find that there are plenty of solutions. What is there about 7mod(8) that makes it have zero solutions? And what is there about n2 +2? Because 7(mod8) numbers divide into n2 +3. Example: 7*12=84=92+3
Last edited by: gordonm888 on Sep 11, 2019
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
kubikulann Joined: Jun 28, 2011
• Posts: 905
Thanks for this post from: September 11th, 2019 at 3:55:20 PM permalink
Quote:

Are a and b allowed to be negative? If not, then there is no possible (u,a,b) triplet that satisfies the modulo conditions for v=0. Or for v=4.

I thought so (even wrote it down, but later edited).
Actually, as it is modular, it doesn�t matter if a and b are positive or not.

Writing [a] for a(mod8),
what we have for v=1 is
7[a]+5[b]=2[u]-4

Example
For v=0 : 7[a]+6[b]+5=0 (mod 8)
Solutions : ([a],[b]) = (1,2),(1,6),(3,1),(3,5),(5,0),(5,4),(7,3),(7,7)

(8a+6)(8b+7) = 14*23,14*55,30*15,30*47,46*7,46*39,62*31,62*63
(8a+6)(8b+7)-2 = 320, 768 , 448 , 1408 , 320 , 1792 , 1920 , 3904

none of which is a square.

But there are many other solutions to (a,b) ; (9,2),(9,6),(17,2),(17,6)�(1,10),(1,18),(9,10),(9,18)� ad inf
The equation becomes
u2 = (8(a+8i)+6)(8(b+8j)+7)-2
= (8a+6)(8b+7)-2 + 64i(8b+7) + 64j(8a+6) + 642ij

Ouch!
The underlined part mod 64 can be 0,0,0,0,0,0,0,0
so we are looking for u such that u2=0(mod64)
This is clearly not impossible.
One more turn on the merry-go-round.

( u/8 )2 = <5,12,7,22,5,28,30,61> +i(8b+7) + j(8a+6) + 64ij
= <5,12,7,22,5,28,30,61> + <23,55,15,47,7,39,31,63>i + <14,14,30,30,46,46,62,62>j + 64ij

Eight equations with the question, does there exist i and j such that it is a square?

(It.s 1AM now. To be followed tomorrow.)
Reperiet qui quaesiverit
ThatDonGuy Joined: Jun 22, 2011
• Posts: 4683
Thanks for this post from: September 11th, 2019 at 5:51:06 PM permalink
Quote: gordonm888

Quote: kubikulann

Are you sure about the original assertion or is it a conjecture?

It is a conjecture, based on >20,000 trials.

I started a brute force search, and could not find any n < 16,000 such that n2 + 2 was a multiple of any number of the form 8k + 7.
EDIT: None found through 25,000

I have also asked the math boffins at Art of Problem Solving to see if they can come up with anything.
EDIT: Somebody has come up with a solution (that confirms the conjecture) that I need to check; it involves "quadratic residues" and "Legendre symbols"
Last edited by: ThatDonGuy on Sep 11, 2019
gordonm888 Joined: Feb 18, 2015