mersenneforum.org > Math p² | (n²+1)
 Register FAQ Search Today's Posts Mark Forums Read

 2018-11-02, 22:09 #1 bhelmes     Mar 2016 52×11 Posts 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
 2018-12-16, 00:16 #2 JeppeSN     "Jeppe" Jan 2016 Denmark 25·5 Posts 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
2018-12-16, 01:08   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by bhelmes 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
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

2018-12-16, 01:50   #4
Dr Sardonicus

Feb 2017
Nowhere

3×7×132 Posts

Quote:
 Originally Posted by bhelmes If i have p² | f(m) how could i calculate p | f(n) with 1
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.

2018-12-17, 16:54   #5
bhelmes

Mar 2016

1000100112 Posts

Quote:
 Originally Posted by Dr Sardonicus 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