Repository: sympy/sympy
Pull request: fixed is_nthpow_residue
Fixes #18394 
 
<!-- BEGIN RELEASE NOTES -->
* ntheory
  * `is_nthpow_residue` no longer raises ValueError when a < 0
  * `polynomial_congruence` recognizes x**n + a = 0 mod m as a special case
<!-- END RELEASE NOTES -->

Problem statement:
Noticed several bugs in residue.py
(1) is_nthpow_residue(3, 0, 2) in the test case is wrong because x**0 = 3 mod 2 has solutions {0, 1}
(2) is_nthpow_residue(a, n, m) when a < 0 there should not be an assertion error.
(3) nthroot_mod(a, n, p, all_roots=False) when a < 0, it gives assertion error due to bug in is_nthpow_residue(a, n, m).

Hints from issue discussion:
@oscarbenjamin @smichr @jksuom please check if these are correct issue, and i will start working on it.

Commit message: minor improvements

Patch to review:
diff --git a/sympy/ntheory/residue_ntheory.py b/sympy/ntheory/residue_ntheory.py
index cb5d11022f13..f1924336dcbb 100644
--- a/sympy/ntheory/residue_ntheory.py
+++ b/sympy/ntheory/residue_ntheory.py
@@ -628,18 +628,17 @@ def is_nthpow_residue(a, n, m):
     .. [1] P. Hackman "Elementary Number Theory" (2009), page 76
 
     """
+    a = a % m
     a, n, m = as_int(a), as_int(n), as_int(m)
     if m <= 0:
         raise ValueError('m must be > 0')
     if n < 0:
         raise ValueError('n must be >= 0')
-    if a < 0:
-        raise ValueError('a must be >= 0')
     if n == 0:
         if m == 1:
             return False
         return a == 1
-    if a % m == 0:
+    if a == 0:
         return True
     if n == 1:
         return True
@@ -834,6 +833,7 @@ def nthroot_mod(a, n, p, all_roots=False):
     >>> nthroot_mod(68, 3, 109)
     23
     """
+    a = a % p
     from sympy.core.numbers import igcdex
     a, n, p = as_int(a), as_int(n), as_int(p)
     if n == 2:
@@ -1487,10 +1487,9 @@ def _val_poly(root, coefficients, p):
 
 
 def _valid_expr(expr):
-    """This function is used by `polynomial_congruence`.
-    If `expr` is a univariate polynomial will integer
-    coefficients the it returns its coefficients,
-    otherwise it raises Valuerror
+    """
+    return coefficients of expr if it is a univariate polynomial
+    with integer coefficients else raise a ValueError.
     """
 
     from sympy import Poly
@@ -1526,6 +1525,7 @@ def polynomial_congruence(expr, m):
     [3257]
     """
     coefficients = _valid_expr(expr)
+    coefficients = [num % m for num in coefficients]
     rank = len(coefficients)
     if rank == 3:
         return quadratic_congruence(coefficients[0], coefficients[1],
@@ -1533,6 +1533,8 @@ def polynomial_congruence(expr, m):
     if rank == 2:
         return quadratic_congruence(0, coefficients[0], coefficients[1],
             m)
+    if coefficients[0] == 1 and 1 + coefficients[-1] = sum(coefficients):
+        return nthroot_mod(-coefficients[-1], rank - 1, m, True)
     if isprime(m):
         return _polynomial_congruence_prime(coefficients, m)
     return _help(m,
diff --git a/sympy/ntheory/tests/test_residue.py b/sympy/ntheory/tests/test_residue.py
index 85590629cb29..8328813a17b6 100644
--- a/sympy/ntheory/tests/test_residue.py
+++ b/sympy/ntheory/tests/test_residue.py
@@ -130,7 +130,7 @@ def test_residue():
     #issue 10816
     assert is_nthpow_residue(1, 0, 1) is False
     assert is_nthpow_residue(1, 0, 2) is True
-    assert is_nthpow_residue(3, 0, 2) is False
+    assert is_nthpow_residue(3, 0, 2) is True
     assert is_nthpow_residue(0, 1, 8) is True
     assert is_nthpow_residue(2, 3, 2) is True
     assert is_nthpow_residue(2, 3, 9) is False
@@ -274,6 +274,7 @@ def test_residue():
     assert polynomial_congruence(10*x**2 + 14*x + 20, 2) == [0, 1]
     assert polynomial_congruence(x**3 + 3, 16) == [5]
     assert polynomial_congruence(65*x**2 + 121*x + 72, 277) == [249, 252]
+    assert polynomial_congruence(x**4 - 4, 27) == [5, 22]
     assert polynomial_congruence(35*x**3 - 6*x**2 - 567*x + 2308, 148225) == [86957,
         111157, 122531, 146731]
     assert polynomial_congruence(x**16 - 9, 36) == [3, 9, 15, 21, 27, 33]


Code review comments:
diff_hunk: @@ -1526,13 +1525,16 @@ def polynomial_congruence(expr, m):
     [3257]
     """
     coefficients = _valid_expr(expr)
+    coefficients = [num % m for num in coefficients]
     rank = len(coefficients)
     if rank == 3:
         return quadratic_congruence(coefficients[0], coefficients[1],
             coefficients[2], m)
     if rank == 2:
         return quadratic_congruence(0, coefficients[0], coefficients[1],
path: sympy/ntheory/residue_ntheory.py
text: @user1:
```suggestion
        return quadratic_congruence(0, *coefficients, m)
```

diff_hunk: @@ -1526,13 +1525,16 @@ def polynomial_congruence(expr, m):
     [3257]
     """
     coefficients = _valid_expr(expr)
+    coefficients = [num % m for num in coefficients]
     rank = len(coefficients)
     if rank == 3:
         return quadratic_congruence(coefficients[0], coefficients[1],
path: sympy/ntheory/residue_ntheory.py
text: @user1:
```suggestion
        return quadratic_congruence(*coefficients, m)
```