This is documentation for Mathematica 4, which was
based on an earlier version of the Wolfram Language.
Wolfram Research, Inc.

3.4.11 Advanced Topic: Equations Modulo Integers

When you write an equation like lhs == rhs, you usually want to assert that the expressions lhs and rhs are exactly equal. For some purposes, however, it is convenient to use a weaker notion of equality, and to interpret lhs == rhs as meaning that two integer expressions are equal modulo some fixed integer. Solving equations that use this weaker notion of equality is important in many problems in number theory.

Solving equations modulo integers.

There are two ways to work with equations modulo integers. The first is explicitly to specify the modulus you want to use. The second is to let Solve find a modulus for which your equations are satisfied.

Mathematica cannot find a closed-form solution for this equation over complex numbers.

In[1]:= Solve[5 + 11x + 17x^2 + 7x^3 + 16x^4 + x^5==0, x]

Out[1]=

The equation does, however, have simple solutions over integers modulo . Notice that if you include an equation for Modulus, you do not have to set Mode->Modular explicitly.

In[2]:= Solve[5 + 11x + 17x^2 + 7x^3 + 16x^4 + x^5==0 &&

Modulus==19, x]

Out[2]=

If you use Mode->Modular, but do not explicitly include an equation for the modulus you want to use, Mathematica will try to find a modulus for which your set of equations can be satisfied.

The result shows that these equations are satisfied modulo 2 when is odd.

In[3]:= Solve[{x^2 + 1 == 0, x^3 + 1 == 0}, x, Mode->Modular]

Out[3]=

When you solve equations in the usual way over complex numbers, it takes equations to determine the values of complex variables. When you use Mode->Modular without specifying the modulus in advance, however, you can expect to get a finite number of solutions for integer variables only by giving equations. You can think of the extra equation as being what is needed to determine the modulus.

Here is a polynomial of degree three.

In[4]:= f = x^3 + 4x + 17

Out[4]=

This finds the value of x and the modulus for which both f and its derivative vanish.

In[5]:= Solve[ f == D[f,x] == 0, x, Mode->Modular ]

Out[5]=

Here are the corresponding values of f and D[f,x].

In[6]:= {f, D[f,x]} /. %

Out[6]=

They indeed do vanish modulo 8059.

In[7]:= Mod[%, 8059]

Out[7]=

Here is another example, based on a polynomial in two variables.

In[8]:= f = y^2 - y - x^3 + x^2

Out[8]=

In the language of arithmetic geometry, this shows that the curve defined by has a singular point modulo the prime number 11.

In[9]:= Solve[ f == D[f,x] == D[f,y] == 0, {x, y},

Mode->Modular ]

Out[9]=