20150916, 14:09  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
2^{3}×797 Posts 
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 minimumvalueofmaximumcoefficient: 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 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 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 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 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 20150917 at 08:19 Reason: add some quadraticinx^2 cases 
20150916, 14:39  #2  
Nov 2003
1D24_{16} Posts 
Quote:
http://websites.math.leidenuniv.nl/a...chebotarev.pdf 

20150918, 12:54  #3  
Nov 2003
1110100100100_{2} Posts 
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime numbers norms of modulo cyclotomic polynomials  carpetpool  carpetpool  24  20171029 23:47 
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve  mickfrancis  Factoring  2  20160506 08:13 
modulo operation for polynomials?  smslca  Math  3  20110418 17:18 
Roots of 1 mod 2^n  fenderbender  Miscellaneous Math  17  20101116 16:25 
Fast calculations modulo small mersenne primes like M61  Dresdenboy  Programming  10  20040229 17:27 