Modular Arithmetic -Need Help

I have noticed the following:

No integer congruent with 7(mod 8) is ever a factor/divisor of any number n²+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 n²+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 n²+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?

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

Maybe a link?

Yes,you remind me that I've read that 7(mod 8) integers are the sum of four squares. Weird.

As n²+2 = n²+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 4^k (and cannot be if m= 4^k).

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

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

v	n2+2	c
0,4	2	6
1,3,5,7	3	5
2,6	6	2

64u²+16uv+v²+2 = 64ab+8(ac+7b)+7c

v	v2+2	7c	diff	7b+ac=8(u2-ab)+2uv+diff/8
0	2	42	-40	8(u2-ab)-5
1	3	35	-32	8(u2-ab)+2u-4
2	6	14	8	8(u2-ab)+4u+1
3	11	35	24	8(u2-ab)+6u+3
4	18	42	24	8(u2-ab)+8u+3
5	27	35	8	8(u2-ab)+10u+1
6	38	14	-24	8(u2-ab)+12u-3
7	51	35	-16	8(u2-ab)+14u-2

Or, modulo 8,

v	7b+ac	=
0	7b+6a	-5
1	7b+5a	2u-4
2	7b+2a	4u+1
3	7b+5a	6u+3
4	7b+6a	+3
5	7b+5a	2u+1
6	7b+2a	4u-3
7	7b+5a	6u-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 -> n²+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.

Quote: kubikulann

As n²+2 = n²+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 4^k (and cannot be if m= 4^k).

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.

Quote: kubikulann

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

v	n2+2	c
0,4	2	6
1,3,5,7	3	5
2,6	6	2

64u²+16uv+v²+2 = 64ab+8(ac+7b)+7c

v	v2+2	7c	diff	7b+ac=8(u2-ab)+2uv+diff/8
0	2	42	-40	8(u2-ab)-5
1	3	35	-32	8(u2-ab)+2u-4
2	6	14	8	8(u2-ab)+4u+1
3	11	35	24	8(u2-ab)+6u+3
4	18	42	24	8(u2-ab)+8u+3
5	27	35	8	8(u2-ab)+10u+1
6	38	14	-24	8(u2-ab)+12u-3
7	51	35	-16	8(u2-ab)+14u-2

Or, modulo 8,

v	7b+ac	=
0	7b+6a	-5
1	7b+5a	2u-4
2	7b+2a	4u+1
3	7b+5a	6u+3
4	7b+6a	+3
5	7b+5a	2u+1
6	7b+2a	4u-3
7	7b+5a	6u-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 -> n²+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 = (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)² 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 n² +2? Because 7(mod8) numbers divide into n² +3. Example: 7*12=84=9²+3

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
u² = (8(a+8i)+6)(8(b+8j)+7)-2
= (8a+6)(8b+7)-2 + 64i(8b+7) + 64j(8a+6) + 64²ij

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

( u/8 )² = <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.)

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 n² + 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"

I have been checking the literature, mainly by mining the On-line Encyclopedia of Integer Sequences, oeis.org

Sequence A059100 is a(n)=n^2+2. There is not any mention of the numbers in this sequence never being a multiple of 8k+7.

Numbers of the form n²+m², such as n²+1, n²+4, n²+9, etc. are the sums of squares and are known to be divisible only by integers congruent to 1(mod 4); that is, divisible by integers congruent 1,5(mod 8). However, I have not seen any mention of other values of (n² +/- m) having any limits on factors/divisors.

Quote: ThatDonGuy

I started a brute force search, and could not find any n < 16,000 such that n² + 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"

Can you post a link? I can read Legendre symbols and quadratic residues.

Edit: I found it.

I'm satisfied with the proof that ThatDonGuy stimulated on The Art of Problem Solving site. You can read it here:
Proof: Read Post #14 and subsequent Posts by Stormersyle

I can also see why n²+3 would be divisible by all of the congruence classes of 8, i.e., by 1,3,5,7(mod 8).

I have submitted a comment on this to the OEIS website and it appears to have been accepted for 'publication.'

Thanks to kubikulann and ThatDonGuy for your help with this. Two of the smartest guys on this forum!

Quote: gordonm888

I'm satisfied with the proof that ThatDonGuy stimulated on The Art of Problem Solving site. You can read it here:
Proof: Read Post #14 and subsequent Posts by Stormersyle

Also note that the same proof shows that no integer congruent with 5 (mod 8) is a factor of n² + 2.

Quote: gordonm888

I'm satisfied with the proof that ThatDonGuy stimulated on The Art of Problem Solving site. You can read it here:
Proof: Read Post #14 and subsequent Posts by Stormersyle!

Delightful and fascinating. I love learning that stuff. Thank you both.