mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2015-09-16, 14:09   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

142628 Posts
Default On polynomials without roots modulo small p

A friend of mine observed that the centred hexagonal numbers (3x^2+3x+1) never looked 'nice'. This is true, and the reason is that they're never divisible by 2, 3, 5 or 11.

So I've been looking for polynomials which take only values not divisible by small primes. You can construct these by the Chinese Remainder Theorem, but I'm more interested in the asymptotics of where they turn up in nature for polynomials with small coefficients.

For quadratics, going up by minimum-value-of-maximum-coefficient:

Code:
a2  a1  a0  smallest prime with root mod p
48   42   73      53
81  141  -139   59
178   74  179    67
358  222  331  73
786  912  -811 83
2106  546 3037  89
3840 1290 2089  97
For cubics
Code:
a3  a2  a1  a0   p_min
12  3  33    -1  37
16  9  36    -1  41
4  48 -10   47  47
1  49 -52    1  53
60 52 -10   71  71
6  44 164 -131  79
For monic quadratics
Code:
1  1415   -673   67
1  6663  -1361   71
1  8433  -8171   73
1 12431  -6079   83
1 12787  -3187  101
1 16159 -10093  107
1 41569 -19993  127
1 97195 -93463  131
1 139831 -124513  137
1 221601 -204983  149
For quartics
Code:
2 -4 -2 4 -1  23
4 0 -6 0 1  31
3 -6 -4 7 1  41
5 6 18 15 -1  43
9 13 19 13 -1  53
29 0 -29 0 -1  61
4 22 -45 19 -1  83
3 0 85 0 1  89
7 -14 -90 97 -1 103
29 0 37 0 107  107
61 -122 -41 102 109  109
For ax^4+bx^2+c
Code:
4 0 -6 0 1  31
19 0 19 0 -1  37
21 0 -21 0 -1  41
25 0 -27 0 1  47
29 0 -29 0 -1  61
61 0 53 0 -1  83
3 0 85 0 1  89
29 0 37 0 107  107
19 0 -139 0 -137  113
156 0 -174 0 -131  131
9 0 259 0 1  139
486 0 -6 0 -223  149

Last fiddled with by fivemack on 2015-09-17 at 08:19 Reason: add some quadratic-in-x^2 cases
fivemack is offline   Reply With Quote
Old 2015-09-16, 14:39   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by fivemack View Post
A friend of mine observed that the centred hexagonal numbers (3x^2+3x+1) never looked 'nice'. This is true, and the reason is that they're never divisible by 2, 3, 5 or 11.

So I've been looking for polynomials which take only values not divisible by small primes. You can construct these by the Chinese Remainder Theorem, but I'm more interested in the asymptotics of where they turn up in nature for polynomials with small coefficients.

For quadratics, going up by minimum-value-of-maximum-coefficient:

Code:
a2  a1  a0  smallest prime with root mod p
48  42  73      53
81 141 -139   59
178 74 179    67
358 222 331  73
786 912 -811 83
(I have examples with 89 [387 7353 -7963] and 97 [960 330 7951] but am not sure they're smallest)
For cubics
Code:
a3  a2  a1  a0   p_min
12  3  33    -1  37
16  9  36    -1  41
4  48 -10   47  47
1  49 -52    1  53
60 52 -10   71  71
6  44 164 -131  79
For monic quadratics
Code:
1  1415   -673   67
1  6663  -1361   71
1  8433  -8171   73
1 12431  -6079   83
1 12787  -3187  101
1 16159 -10093  107
For quartics
Code:
2 -4 -2 4 -1  23
4 0 -6 0 1  31
3 -6 -4 7 1  41
5 6 18 15 -1  43
9 13 19 13 -1  53
29 0 -29 0 -1  61
4 22 -45 19 -1  83
One may find a lot of useful information in:

http://websites.math.leidenuniv.nl/a...chebotarev.pdf
R.D. Silverman is offline   Reply With Quote
Old 2015-09-18, 12:54   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
One may find a lot of useful information in:

http://websites.math.leidenuniv.nl/a...chebotarev.pdf
I should have added (from elementary algebraic number theory) that f(x) will be
divisible by p for some x if

(1) p divides the discriminant and
(2) the polynomial is not constant mod p.

Such primes p ramify.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime numbers norms of modulo cyclotomic polynomials carpetpool carpetpool 24 2017-10-29 23:47
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve mickfrancis Factoring 2 2016-05-06 08:13
modulo operation for polynomials? smslca Math 3 2011-04-18 17:18
Roots of 1 mod 2^n fenderbender Miscellaneous Math 17 2010-11-16 16:25
Fast calculations modulo small mersenne primes like M61 Dresdenboy Programming 10 2004-02-29 17:27

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

Mon Oct 26 01:47:32 UTC 2020 up 45 days, 22:58, 0 users, load averages: 1.80, 1.62, 1.63

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.