mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2018-11-02, 22:09   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52×11 Posts
Default p² | (n²+1)

A peaceful and pleasant night for all members,


Regarding the irreducible polynomial f(n)=n²+1
If i have a prime p| f(n) then i know that i could calculate
p² | f(m) with the Hensel-lifting with m>n.


If i have p² | f(m) how could i calculate p | f(n) with 1<n<m


Or in other words could there be a quadrat of a prime as a divisor of the function
without the earlier appearance of the prime.


Perhaps someone knows an easy prove,
would be nice to know it



Greetings from Landaus problem

Bernhard

Last fiddled with by bhelmes on 2018-11-02 at 22:12
bhelmes is offline   Reply With Quote
Old 2018-12-16, 00:16   #2
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

25·5 Posts
Default

Not quite clear to me what you ask, but I think that every prime of the form p = 4n+1 will satisfy that p^2 divides numbers of the form n^2 + 1 (and other primes p will not). On the other hand, the n values such that n^2 + 1 is divisible by a non-trivial square, are A049532. /JeppeSN
JeppeSN is offline   Reply With Quote
Old 2018-12-16, 01:08   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by bhelmes View Post
A peaceful and pleasant night for all members,


Regarding the irreducible polynomial f(n)=n²+1
If i have a prime p| f(n) then i know that i could calculate
p² | f(m) with the Hensel-lifting with m>n.


If i have p² | f(m) how could i calculate p | f(n) with 1<n<m


Or in other words could there be a quadrat of a prime as a divisor of the function
without the earlier appearance of the prime.


Perhaps someone knows an easy prove,
would be nice to know it



Greetings from Landaus problem

Bernhard
Well there's the obvious pick n coprime to m .
There's also that n^4+2n^2+1 will divide by p^2 so gcd of these polynomials will also have the p^2 factor.

Last fiddled with by science_man_88 on 2018-12-16 at 01:08
science_man_88 is offline   Reply With Quote
Old 2018-12-16, 01:50   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×7×132 Posts
Default

Quote:
Originally Posted by bhelmes View Post
<snip>
If i have p² | f(m) how could i calculate p | f(n) with 1<n<m


Or in other words could there be a quadrat of a prime as a divisor of the function
without the earlier appearance of the prime.


Perhaps someone knows an easy prove,
would be nice to know it
Assuming f(x) is a polynomial with integer coefficients, and you are only interested in integer values of x, then whether p divides f(m) only depends on m (mod p). The relevant values of m (mod p) show up in the linear factors of f(x) (mod p), i.e. f(x) viewed as a polynomial in Fp[x]. Representative m-values may be taken in the interval [0, p-1].

For f(x) = x2 + 1, there will (for p == 1 (mod 4)) be two such values of m in [0, p-1]; one value will be in [0, (p-1)/2]. In either case, though, 0 < m2 + 1 < p2, so neither value is divisible by p2.
Dr Sardonicus is offline   Reply With Quote
Old 2018-12-17, 16:54   #5
bhelmes
 
bhelmes's Avatar
 
Mar 2016

1000100112 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post

For f(x) = x2 + 1, there will (for p == 1 (mod 4)) be two such values of m in [0, p-1]; one value will be in [0, (p-1)/2]. In either case, though, 0 < m2 + 1 < p2, so neither value is divisible by p2.

Thanks for this clear and logical answer

Bernhard
bhelmes is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 01:12.

Tue Oct 20 01:12:12 UTC 2020 up 39 days, 22:23, 0 users, load averages: 1.82, 2.01, 2.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.