|
|
A367688
|
|
Number of primes p such that x^n + y^n mod p does not take all values on Z/pZ.
|
|
2
|
|
|
0, 0, 1, 4, 4, 13, 5, 14, 11, 24, 9, 42, 14, 30, 26, 37, 17, 54, 17, 63, 33, 43, 25, 104, 31, 53, 49, 87, 26, 130, 27, 85, 56, 69, 56, 170, 36, 74, 68, 140, 40, 175, 43, 124, 105, 91, 45, 215, 55, 149, 87, 142, 48, 209, 83, 185, 96, 119, 57, 339, 59, 128, 133
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
a(n) is finite for all positive integers n by the Hasse-Weil bound. Indeed, for any integer k, the number of solutions N to x^n + y^n == k (mod p) satisfies |N - (p+1)| <= 2*g*sqrt(p) where g = (n-1)(n-2)/2 is the genus of the Fermat curve X^n + Y^n = kZ^n. Thus, N is nonzero if p+1 > (n-1)(n-2)*sqrt(p). In particular, x^n + y^n mod p takes all values on Z/pZ for all primes p > n^4.
|
|
LINKS
|
|
|
EXAMPLE
|
For n = 1, the equation x + y == k (mod p) always has a solution for any integer k and prime p, so a(1) = 0.
For n = 2, the equation x^2 + y^2 == k (mod p) always has a solution for any integer k and prime p, so a(2) = 0.
For n = 3, the equation x^3 + y^3 == 3 (mod 7) does not have a solution, but x^3 + y^3 == k (mod p) does have a solution for any integer k and prime p not equal to 7, thus a(3) = 1.
|
|
PROG
|
(Sage)
def a(n):
ans = 0
for p in prime_range(1, n^4):
nth_powers = set([power_mod(x, n, p) for x in range(p)])
for k in range(p):
for xn in nth_powers:
if (k-xn)%p in nth_powers: break
else: ans += 1; break
return ans
(Sage) # This is very slow for n larger than 7
def a(n):
ans = 0
for p in prime_range(1, n^4):
all_values = set()
for x in range(p):
for y in range(p):
all_values.add((x^n+y^n)%p)
if len(all_values) < p: ans += 1
return ans
(Python)
from itertools import combinations_with_replacement
from sympy import sieve
c = 0
for p in sieve.primerange(n**4+1):
s = set()
for k in combinations_with_replacement({pow(x, n, p) for x in range(p)}, 2):
s.add(sum(k)%p)
if len(s) == p:
break
else:
c += 1
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|