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

7, 29, 61, 223, 127, 761, 307, 911, 617, 1741, 1171, 2927, 3181, 2593, 1667, 4519, 2927, 10781, 5167, 6491, 8419, 7177, 5501, 7307, 9829, 11117, 12703, 20011, 10789, 13249, 18217, 22271, 14771, 29629, 13691, 18773, 22543, 21601, 19927, 46411, 18749, 32957

Offset: 3

Author

Seiichi Azuma, Jul 21 2022

Keywords

• nonn

Comments

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.

Conjecture: a(n) == 1 (mod n). - Jason Yuen, May 18 2024

Examples

			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.
		

Links

• Jason Yuen, Table of n, a(n) for n = 3..63
• MathOverflow, Does the expression x^4+y^4 take on all values in Z/pZ?
• Seiichi Azuma, Python code for calculating a(n) (Google Colab)

Crossrefs

Cf. A289559.

Programs

Python

import sympy
def a(n):
    g = (n - 1) * (n - 2) / 2
    plist = list(sympy.primerange(2, n ** 4))
    plist.reverse()
    for p in plist:
        # equivalent to p-1-2*g*p**0.5 > n:
        if (p - 1 - n) ** 2 > 4 * g * g * p:
            continue
        solution = [False] * p
        r = sympy.primitive_root(p)
        rn = r ** n % p  # generator for subgroup {x^n}
        d = sympy.n_order(rn, p)  # size of subgroup {x^n}
        nth_power_list = []
        xn = 1
        for k in range(d):
            xn = xn * rn % p
            nth_power_list.append(xn)
            for yn in nth_power_list:
                solution[(xn + yn) % p] = True
        for yn in nth_power_list:  # consider the case x=0
            solution[yn] = True
        solution[0] = True
        if False in solution:
            return p
    return -1
print([a(n) for n in range(3, 18)])

Extensions

a(13)-a(25) from Jinyuan Wang, Jul 22 2022

a(26)-a(27) from Chai Wah Wu, Sep 13 2022

a(28)-a(33) from Chai Wah Wu, Sep 14 2022

a(34)-a(40) from Robin Visser, Dec 09 2023

a(41)-a(49) from Robin Visser, Mar 18 2024