A367688 Number of primes p such that x^n + y^n mod p does not take all values on Z/pZ.

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

Offset: 1

Author

Robin Visser, Nov 26 2023

Keywords

• nonn

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.

Examples

			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.
		

Links

• MathOverflow, Does the expression x^4+y^4 take on all values in Z/pZ?

Crossrefs

Cf. A355920, A367689.

Programs

Python

from itertools import combinations_with_replacement
from sympy import sieve
def A367688(n):
    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
    return c # Chai Wah Wu, Nov 27 2023

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

Extensions

a(36)-a(63) from Jason Yuen, May 18 2024