cp's OEIS Frontend

A355920 Largest prime number p such that x^n + y^n mod p does not take all values on Z/pZ.

%I A355920 #64 Apr 21 2025 23:26:33
%S A355920 7,29,61,223,127,761,307,911,617,1741,1171,2927,3181,2593,1667,4519,
%T A355920 2927,10781,5167,6491,8419,7177,5501,7307,9829,11117,12703,20011,
%U A355920 10789,13249,18217,22271,14771,29629,13691,18773,22543,21601,19927,46411,18749,32957
%N A355920 Largest prime number p such that x^n + y^n mod p does not take all values on Z/pZ.
%C A355920 As discussed in the link below, the Hasse-Weil bound assures that x^n + y^n == k (mod p) always has a solution when p - 1 - 2*g*sqrt(p) > n, where g = (n-1)*(n-2)/2 is the genus of the Fermat curve. For example, p > n^4 is large enough to satisfy this condition, so we only need to check finitely many p below n^4.
%C A355920 Conjecture: a(n) == 1 (mod n). - _Jason Yuen_, May 18 2024
%H A355920 Jason Yuen, <a href="/A355920/b355920.txt">Table of n, a(n) for n = 3..63</a>
%H A355920 MathOverflow, <a href="https://mathoverflow.net/questions/356270">Does the expression x^4+y^4 take on all values in Z/pZ?</a>
%H A355920 Seiichi Azuma, <a href="https://colab.research.google.com/drive/1LzZa-uf0U2clOW_reov1iXwZuZSMetym?usp=sharing">Python code for calculating a(n) (Google Colab)</a>
%e A355920 a(3) = 7 because x^3 + y^3 == 3 (mod 7) does not have a solution, but x^3 + y^3 == k (mod p) always has a solution when p is a prime greater than 7.
%o A355920 (Python)
%o A355920 import sympy
%o A355920 def a(n):
%o A355920     g = (n - 1) * (n - 2) / 2
%o A355920     plist = list(sympy.primerange(2, n ** 4))
%o A355920     plist.reverse()
%o A355920     for p in plist:
%o A355920         # equivalent to p-1-2*g*p**0.5 > n:
%o A355920         if (p - 1 - n) ** 2 > 4 * g * g * p:
%o A355920             continue
%o A355920         solution = [False] * p
%o A355920         r = sympy.primitive_root(p)
%o A355920         rn = r ** n % p  # generator for subgroup {x^n}
%o A355920         d = sympy.n_order(rn, p)  # size of subgroup {x^n}
%o A355920         nth_power_list = []
%o A355920         xn = 1
%o A355920         for k in range(d):
%o A355920             xn = xn * rn % p
%o A355920             nth_power_list.append(xn)
%o A355920             for yn in nth_power_list:
%o A355920                 solution[(xn + yn) % p] = True
%o A355920         for yn in nth_power_list:  # consider the case x=0
%o A355920             solution[yn] = True
%o A355920         solution[0] = True
%o A355920         if False in solution:
%o A355920             return p
%o A355920     return -1
%o A355920 print([a(n) for n in range(3, 18)])
%Y A355920 Cf. A289559.
%K A355920 nonn
%O A355920 3,1
%A A355920 _Seiichi Azuma_, Jul 21 2022
%E A355920 a(13)-a(25) from _Jinyuan Wang_, Jul 22 2022
%E A355920 a(26)-a(27) from _Chai Wah Wu_, Sep 13 2022
%E A355920 a(28)-a(33) from _Chai Wah Wu_, Sep 14 2022
%E A355920 a(34)-a(40) from _Robin Visser_, Dec 09 2023
%E A355920 a(41)-a(49) from _Robin Visser_, Mar 18 2024