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

%I #27 May 18 2024 13:40:56

%S 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,

%T 53,49,87,26,130,27,85,56,69,56,170,36,74,68,140,40,175,43,124,105,91,

%U 45,215,55,149,87,142,48,209,83,185,96,119,57,339,59,128,133

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

%C 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.

%H MathOverflow, <a href="https://mathoverflow.net/questions/356270">Does the expression x^4+y^4 take on all values in Z/pZ?</a>

%e 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.

%e 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.

%e 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.

%o (Sage)

%o def a(n):

%o ans = 0

%o for p in prime_range(1, n^4):

%o nth_powers = set([power_mod(x,n,p) for x in range(p)])

%o for k in range(p):

%o for xn in nth_powers:

%o if (k-xn)%p in nth_powers: break

%o else: ans += 1; break

%o return ans

%o (Sage) # This is very slow for n larger than 7

%o def a(n):

%o ans = 0

%o for p in prime_range(1,n^4):

%o all_values = set()

%o for x in range(p):

%o for y in range(p):

%o all_values.add((x^n+y^n)%p)

%o if len(all_values) < p: ans += 1

%o return ans

%o (Python)

%o from itertools import combinations_with_replacement

%o from sympy import sieve

%o def A367688(n):

%o c = 0

%o for p in sieve.primerange(n**4+1):

%o s = set()

%o for k in combinations_with_replacement({pow(x,n,p) for x in range(p)},2):

%o s.add(sum(k)%p)

%o if len(s) == p:

%o break

%o else:

%o c += 1

%o return c # _Chai Wah Wu_, Nov 27 2023

%Y Cf. A355920, A367689.

%K nonn

%O 1,4

%A _Robin Visser_, Nov 26 2023

%E a(36)-a(63) from _Jason Yuen_, May 18 2024