Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

## #1 2016-10-20 13:53:53

Member
Registered: 2013-01-22
Posts: 131

### Reducing the no. of potential factors for n^2+1.

New Theorem:
Potential factors for

may only be factored by previous values of

Because.............
Let p= potential factor
Let p=n-y
(n-y)(n+y) =

Therefore remainder when
is divided by p =

And remainder when
is divided by p =

y will be less than p because y=n-p and p>0
p will not be greater than n because we are only concerned with primes

This should reduce potential factors for

and reduce computing space for finding primes.

I have tried up to n=43. Prime factors <44 that were missing were 3, 7, 11, 19, 23, 31 and 43 which exactly halved the no. of potential prime factors. Any value for n to infinity will not be factorable by these no.'s.
The factors repeat themselves every +p value for n. So if they don't occur before

then they will never occur because ones above p are just repeats of ones <p.

"Time not important. Only life important." - The Fifth Element 1997

Offline

## #2 2016-10-20 23:22:31

Member
Registered: 2013-01-22
Posts: 131

### Re: Reducing the no. of potential factors for n^2+1.

Examples: [Formulas followed by prime factorization, as you can see factors 3,7,11,19,23,31 and 43 are missing]
n=1

2
n=2
5
n=3
10=2,5
n=4
17
n=5
26=2,13
n=6
37
n=7
50=2,5
n=8
65=5,13
n=9
82=2,41
n=10
101
n=11
122=2,61
n=12
145=5,29
n=13
170=2,5,17
n=14
197
n=15
226=2,113
n=16
257
n=17
290=2,5,29
n=18
325=5,13
n=19
362=2,181
n=20
401
n=21
442=2,13,17
n=22
485=5,97
n=23
530=2,5,53
n=24
577
n=25
626=2,313
n=26
677
n=27
730=2,5,73
n=28
785=5,157
n=29
842=2,421
n=30
901=17,53
n=31
962=2,13,37
n=32
1025=5,41
n=33
1090=2,5,109
n=34
1157=13,89
n=35
1226=2,613
n=36
1297
n=37
1370=2,5,137
n=38
1445=5,17
n=39
1522=2,761
n=40
1601
n=41
1682=2,29
n=42
1765=5,353
n=43
1850=2,5,37

"Time not important. Only life important." - The Fifth Element 1997

Offline

## #3 2016-10-27 07:04:41

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,192
Website

### Re: Reducing the no. of potential factors for n^2+1.

Potential factors for

may only be factored by previous values of

Forgive my ignorance, but I have no idea what this means. Could you explain this?

Because.............
Let p= potential factor
Let p=n-y
(n-y)(n+y) =

Therefore remainder when
is divided by p =

And remainder when

is divided by p =

That's correct. But I still don't know what a potential factor is (or what you need this part for).

y will be less than p because y=n-p and p>0

You mean y will be less than n, not p.

p will not be greater than n because we are only concerned with primes

So I am guessing by "potential factor" you mean "prime factor"? Also, assuming you want n^2 + 1 to be composite (which isn't true in general, as your next post shows), you need a ≤ sign.

This should reduce potential factors for

You mean reduce the possibilities for the prime factors of n^2 + 1?

I have tried up to n=43. Prime factors <44 that were missing were 3, 7, 11, 19, 23, 31 and 43 which exactly halved the no. of potential prime factors. Any value for n to infinity will not be factorable by these no.'s.
The factors repeat themselves every +p value for n. So if they don't occur before

then they will never occur because ones above p are just repeats of ones <p.

I still don't really understand what you are trying to do, from your post or from your examples in the post above. If you're wondering why 3, 7, 11, 19, 23, 31 and 43 don't appear in the prime factorisations of n^2 + 1, then this is because of quadratic reciprocity. (Let me know if you haven't come across this term before, and I'll be happy to explain it.) In other words, consider the congruence for p = 3 mod 4:

but this doesn't have any solutions, because if
, then
, where
is the quadratic reciprocity symbol. (Which is just another way of saying that -1 isn't a square modulo p, where p is 3 modulo 4 -- in other words, the congruence has no solutions for p = 3 mod 4.)

Last edited by zetafunc (2016-10-27 07:12:38)

Offline

## #4 2016-10-27 07:33:48

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,192
Website

### Re: Reducing the no. of potential factors for n^2+1.

By the way, this is more generally called Euler's Criterion, which says that:

where
is an odd prime, and
is coprime to
.

Offline

## #5 2016-10-27 15:43:37

Member
Registered: 2013-01-22
Posts: 131

### Re: Reducing the no. of potential factors for n^2+1.

zetafunc wrote:

Potential factors for

may only be factored by previous values of

Forgive my ignorance, but I have no idea what this means. Could you explain this?

may only be factorable by factors of
where x<n

zetafunc wrote:

Because.............
Let p= potential factor
Let p=n-y
(n-y)(n+y) =

Therefore remainder when
is divided by p =

And remainder when

is divided by p =

That's correct. But I still don't know what a potential factor is (or what you need this part for).

y=n-x

y<n,
all remainders when
is divided by x. If
is not factorable by a certain integer then neither will
be.

zetafunc wrote:

y will be less than p because y=n-p and p>0

You mean y will be less than n, not p.

Yes

zetafunc wrote:

p will not be greater than n because we are only concerned with primes

So I am guessing by "potential factor" you mean "prime factor"? Also, assuming you want n^2 + 1 to be composite (which isn't true in general, as your next post shows), you need a ≤ sign.

Basically x<n because we are only concerned with factors below the square root, and because y=n-x, y cannot=n because x>0.

zetafunc wrote:

This should reduce potential factors for

You mean reduce the possibilities for the prime factors of n^2 + 1?

Yes

zetafunc wrote:

I have tried up to n=43. Prime factors <44 that were missing were 3, 7, 11, 19, 23, 31 and 43 which exactly halved the no. of potential prime factors. Any value for n to infinity will not be factorable by these no.'s.
The factors repeat themselves every +p value for n. So if they don't occur before

then they will never occur because ones above p are just repeats of ones <p.

I still don't really understand what you are trying to do, from your post or from your examples in the post above. If you're wondering why 3, 7, 11, 19, 23, 31 and 43 don't appear in the prime factorisations of n^2 + 1, then this is because of quadratic reciprocity. (Let me know if you haven't come across this term before, and I'll be happy to explain it.) In other words, consider the congruence for p = 3 mod 4:

but this doesn't have any solutions, because if
, then
, where
is the quadratic reciprocity symbol. (Which is just another way of saying that -1 isn't a square modulo p, where p is 3 modulo 4 -- in other words, the congruence has no solutions for p = 3 mod 4.)

Basically I am trying to make it so that instead of a computer having to try to factor all the primes below the square root for an integer, it only has to try and factor a lot less. Also because the factors repeat themselves this could make things easier. Maybe could do a wheel or something? No, I have never come across Euler' Criterion and I don't get it.

"Time not important. Only life important." - The Fifth Element 1997

Offline

## #6 2016-10-28 05:38:16

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,192
Website

### Re: Reducing the no. of potential factors for n^2+1.

Basically I am trying to make it so that instead of a computer having to try to factor all the primes below the square root for an integer, it only has to try and factor a lot less. Also because the factors repeat themselves this could make things easier. Maybe could do a wheel or something?

You can immediately say that the smallest possible prime factor
will not satisfy
whenever
is not itself prime. You can also rule out primes
by Euler's criterion (or more specifically, by the corollary I mentioned in my previous post).

No, I have never come across Euler' Criterion and I don't get it.

Is there anything in particular in post #4 and #5 you need help with?

Last edited by zetafunc (2016-10-28 08:28:49)

Offline

## #7 2016-10-28 07:39:32

Member
Registered: 2013-01-22
Posts: 131

### Re: Reducing the no. of potential factors for n^2+1.

zetafunc wrote:

You can immediately rule out any primes
such that
whenever
is not itself prime.

But after you have ruled out primes where

all that is left are p's
For instance n=12
=145 rule out/divide by 5 and you get 29, a prime

zetafunc wrote:

You can also rule out primes

by Euler's criterion (or more specifically, by the corollary I mentioned in my previous post).

I don't get Euler's criterion, and probably never will it's just too advanced for me, don't worry. So what you're basically saying is we can rule out possible prime factors where p=4m+3 for

?

"Time not important. Only life important." - The Fifth Element 1997

Offline

## #8 2016-10-28 08:56:25

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,192
Website

### Re: Reducing the no. of potential factors for n^2+1.

But after you have ruled out primes where

all that is left are p's
For instance n=12
=145 rule out/divide by 5 and you get 29, a prime

I meant to say that the smallest prime factor p will not satisfy that relation. (See my edit in the quoted post.)

I don't get Euler's criterion, and probably never will it's just too advanced for me, don't worry. So what you're basically saying is we can rule out possible prime factors where p=4m+3 for

?

It isn't particularly difficult to understand -- I can explain it to you if you just tell me what it is that you need help with. Yes, I'm saying that any prime that has a remainder of 3 when divided by 4 (that's what
means) can be ruled out, by Euler's criterion.

Just to make sure, this is what you want to know, correct?

-You are considering only numbers of the form
any non-zero positive integer.
-You would like to know something about the prime factorisations of these numbers.

Now, the question is: what specifically would you like to know about the prime factorisations? Moreover, what are you trying to demonstrate in post #2? You made this observation earlier:

I have tried up to n=43. Prime factors <44 that were missing were 3, 7, 11, 19, 23, 31 and 43 which exactly halved the no. of potential prime factors.

Notice that the ones missing are all congruent to
The question then becomes: what proportion of primes, less than a given magnitude, are
and
? More generally, what proportion of primes are congruent to
and
? This is a difficult question in analytic number theory, but I can provide you with some insight.

A reasonable guess would be that the number of primes congruent to 1 mod 4 or 3 mod 4 are about the same (i.e. 50-50). Indeed, using Dirichlet's theorem for primes in arithmetic progressions, we can see that for large numbers this is true (that is, as n tends to infinity). More precisely:

where
denotes the number of primes congruent to
, less than or equal to
(If you want to read more about this, look up "prime races".) Note that this is an asymptotic formula. Is it true for any
? Surprisingly, it isn't true at all. In fact, most of the time, primes are more likely to be congruent to 3 mod 4 than they are 1 mod 4. This is called Chebyshev's bias. In fact, you can extend this idea to primes modulo some arbitrary number modulo q, say. But this can only be proven assuming the Riemann hypothesis.

So I suppose you want to ask the question: given any integer
which primes will appear in its prime factorisation, and as
varies, is there any bias towards residue classes of primes modulo
say?

Last edited by zetafunc (2016-10-29 00:27:41)

Offline

## #9 2016-10-29 14:23:16

Member
Registered: 2013-01-22
Posts: 131

### Re: Reducing the no. of potential factors for n^2+1.

zetafunc wrote:

It isn't particularly difficult to understand -- I can explain it to you if you just tell me what it is that you need help with.

I get the beginning but not the end of it where you've put (-1/p)=-1.

zetafunc wrote:

Just to make sure, this is what you want to know, correct?

-You are considering only numbers of the form
any non-zero positive integer.
-You would like to know something about the prime factorisations of these numbers.

First point is correct but I just wanted to show that by using

we can reduce the number of possible factors which should help compute primes faster. And now you have shown that
will never be factorable by the primes of the form
so thank you. I thought about 50% of primes could not possibly be factors but now you're saying that not only would there be 50%, but that there would be a bias to more than 50% due to Chebyshev's bias. Have I got this right?

I am also still trying to work out if there's anything else we can use this scenario for to do with primes. If there was a wheel of prime factors that could factor

, it would be 20m + 1 or 9 or 13 or 17, not including 2 and 5.

"Time not important. Only life important." - The Fifth Element 1997

Offline

## #10 2016-10-29 20:25:54

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,192
Website

### Re: Reducing the no. of potential factors for n^2+1.

I get the beginning but not the end of it where you've put (-1/p)=-1.

Let's define the quadratic residue symbol.

First of all, suppose
is an odd prime, and let
be a non-zero number coprime to
Then,
is called a quadratic residue modulo
if the congruence
has solutions. If it doesn't, then we say that
is called a quadratic non-residue. The quadratic residue symbol summarises this information. We define:

So if I say that
whenever
, that just means the congruence
has no solutions for such primes

First point is correct but I just wanted to show that by using

we can reduce the number of possible factors which should help compute primes faster. And now you have shown that
will never be factorable by the primes of the form
so thank you. I thought about 50% of primes could not possibly be factors but now you're saying that not only would there be 50%, but that there would be a bias to more than 50% due to Chebyshev's bias. Have I got this right?

I am also still trying to work out if there's anything else we can use this scenario for to do with primes. If there was a wheel of prime factors that could factor

, it would be 20m + 1 or 9 or 13 or 17, not including 2 and 5.

What I'm saying is that primes less than a given number
say, are more likely to be
than they are
But primes congruent to
don't appear in your factorisation of
anyway -- so this tells us that slightly more than 50% of primes will never appear in your factorisation, which is due to Chebyshev's bias. But as
they approach the same value.

Offline