Diophantine¶
Diophantine equations¶
The word “Diophantine” comes with the name Diophantus, a mathematician lived in the great city of Alexandria sometime around 250 AD. Often referred to as the “father of Algebra”, Diophantus in his famous work “Arithmetica” presented 150 problems that marked the early beginnings of number theory, the field of study about integers and their properties. Diophantine equations play a central and an important part in number theory.
We call a “Diophantine equation” to an equation of the form,
where
and
are
integer variables. If we can find
integers
such that
satisfies the above equation, we say
that the equation is solvable. You can read more about Diophantine equations in
[1] and [2].
Currently, following five types of Diophantine equations can be solved using
diophantine()
and other helper functions of
the Diophantine module.
- Linear Diophantine equations:
.
- General binary quadratic equation:
- Homogeneous ternary quadratic equation:
- Extended Pythagorean equation:
- General sum of squares:
Module structure¶
This module contains diophantine()
and
helper functions that are needed to solve certain Diophantine equations. It’s
structured in the following manner.
When an equation is given to diophantine()
,
it factors the equation(if possible) and solves the equation given by each
factor by calling diop_solve()
separately.
Then all the results are combined using merge_solution()
.
diop_solve()
internally uses
classify_diop()
to find the type of the equation(and some other details) given to it and then
calls the appropriate solver function based on the type returned. For example,
if classify_diop()
returned “linear” as the
type of the equation, then diop_solve()
calls diop_linear()
to solve the equation.
Each of the functions, diop_linear()
,
diop_quadratic()
,
diop_ternary_quadratic()
,
diop_general_pythagorean()
and diop_general_sum_of_squares()
solves a
specific type of equations and the type can be easily guessed by it’s name.
Apart from these functions, there are a considerable number of other functions in the “Diophantine Module” and all of them are listed under User functions and Internal functions.
Tutorial¶
First, let’s import the highest API of the Diophantine module.
>>> from sympy.solvers.diophantine import diophantine
Before we start solving the equations, we need to define the variables.
>>> from sympy import symbols
>>> x, y, z = symbols("x, y, z", integer=True)
Let’s start by solving the easiest type of Diophantine equations, i.e. linear
Diophantine equations. Let’s solve . Note that although we
write the equation in the above form, when we input the equation to any of the
functions in Diophantine module, it needs to be in the form
.
>>> diophantine(2*x + 3*y - 5)
set([(3*t_0 - 5, -2*t_0 + 5)])
Note that stepping one more level below the highest API, we can solve the very
same equation by calling diop_solve()
.
>>> from sympy.solvers.diophantine import diop_solve
>>> diop_solve(2*x + 3*y - 5)
(3*t_0 - 5, -2*t_0 + 5)
Note that it returns a tuple rather than a set.
diophantine()
always return a set of tuples.
But diop_solve()
may return a single tuple
or a set of tuples depending on the type of the equation given.
We can also solve this equation by calling diop_linear()
,
which is what diop_solve()
calls internally.
>>> from sympy.solvers.diophantine import diop_linear
>>> diop_linear(2*x + 3*y - 5)
(3*t_0 - 5, -2*t_0 + 5)
If the given equation has no solutions then the outputs will look like below.
>>> diophantine(2*x + 4*y - 3)
set()
>>> diop_solve(2*x + 4*y - 3)
(None, None)
>>> diop_linear(2*x + 4*y - 3)
(None, None)
Note that except for the highest level API, in case of no solutions, a tuple of
are returned. Size of the tuple is the same as the number of variables.
Also, one can specifically set the parameter to be used in the solutions by
passing a customized parameter. Consider the following example:
>>> m = symbols("m", integer=True)
>>> diop_solve(2*x + 3*y - 5, m)
(3*m_0 - 5, -2*m_0 + 5)
For linear Diophantine equations, the customized parameter is the prefix used for each free variable in the solution. Consider the following example:
>>> diop_solve(2*x + 3*y - 5*z + 7, m)
(m_0, -9*m_0 - 5*m_1 - 14, -5*m_0 - 3*m_1 - 7)
In the solution above, m_0 and m_1 are independent free variables.
Please note that for the moment, users can set the parameter only for linear Diophantine equations and binary quadratic equations.
Let’s try solving a binary quadratic equation which is an equation with two
variables and has a degree of two. Before trying to solve these equations, an
idea about various cases associated with the equation would help a lot. Please
refer [3] and [4] for detailed analysis of different cases and the nature
of the solutions. Let us define w.r.t. the binary quadratic
.
When , there are either no solutions or only a finite number of solutions.
>>> diophantine(x**2 - 4*x*y + 8*y**2 - 3*x + 7*y - 5)
set([(2, 1), (5, 1)])
In the above equation and hence only a finite
number of solutions exist.
When we might have either no solutions or parameterized solutions.
>>> diophantine(3*x**2 - 6*x*y + 3*y**2 - 3*x + 7*y - 5)
set()
>>> diophantine(x**2 - 4*x*y + 4*y**2 - 3*x + 7*y - 5)
set([(-2*t**2 - 7*t + 10, -t**2 - 3*t + 5)])
>>> diophantine(x**2 + 2*x*y + y**2 - 3*x - 3*y)
set([(t_0, -t_0), (t_0, -t_0 + 3)])
The most interesting case is when and it is not a perfect square.
In this case, the equation has either no solutions or an infinte number of
solutions. Consider the below cases where
.
>>> diophantine(x**2 - 4*x*y + 2*y**2 - 3*x + 7*y - 5)
set()
>>> from sympy import sqrt
>>> n = symbols("n", integer=True)
>>> s = diophantine(x**2 - 2*y**2 - 2*x - 4*y, n)
>>> x_1, y_1 = s.pop()
>>> x_2, y_2 = s.pop()
>>> x_n = -(-2*sqrt(2) + 3)**n/2 + sqrt(2)*(-2*sqrt(2) + 3)**n/2 - sqrt(2)*(2*sqrt(2) + 3)**n/2 - (2*sqrt(2) + 3)**n/2 + 1
>>> x_1 == x_n or x_2 == x_n
True
>>> y_n = -sqrt(2)*(-2*sqrt(2) + 3)**n/4 + (-2*sqrt(2) + 3)**n/2 + sqrt(2)*(2*sqrt(2) + 3)**n/4 + (2*sqrt(2) + 3)**n/2 - 1
>>> y_1 == y_n or y_2 == y_n
True
Here is an integer. Although x_n and y_n may not look like
integers, substituting in specific values for n (and simplifying) shows that they
are. For example consider the following example where we set n equal to 9.
>>> from sympy import simplify
>>> simplify(x_n.subs({n: 9}))
-9369318
Any binary quadratic of the form can be
transformed to an equivalent form
.
>>> from sympy.solvers.diophantine import find_DN, diop_DN, transformation_to_DN
>>> find_DN(x**2 - 3*x*y + y**2 - 7*x + 5*y - 3)
(5, 920)
So, the above equation is equivalent to the equation after
a linear transformation. If we want to find the linear transformation, we can
use
transformation_to_DN()
>>> A, B = transformation_to_DN(x**2 - 3*x*y + y**2 - 7*x + 5*y - 3)
Here A is a 2 X 2 matrix and B is a 2 X 1 matrix such that the transformation
gives the equation . Values of
and
are as belows.
>>> A
Matrix([
[1/10, 3/10],
[ 0, 1/5]])
>>> B
Matrix([
[ 1/5],
[-11/5]])
We can solve an equation of the form by passing
and
to
diop_DN()
>>> diop_DN(5, 920)
[]
Unfortunately, our equation does not have solutions.
Now let’s turn to homogeneous ternary quadratic equations. These equations are
of the form . These type of equations
either have infinitely many solutions or no solutions (except the obvious
solution (0, 0, 0))
>>> diophantine(3*x**2 + 4*y**2 - 5*z**2 + 4*x*y + 6*y*z + 7*z*x)
set()
>>> diophantine(3*x**2 + 4*y**2 - 5*z**2 + 4*x*y - 7*y*z + 7*z*x)
set([(-16*p**2 + 28*p*q + 20*q**2, 3*p**2 + 38*p*q - 25*q**2, 4*p**2 - 24*p*q + 68*q**2)])
If you are only interested about a base solution rather than the parameterized
general solution (to be more precise, one of the general solutions), you can
use diop_ternary_quadratic()
.
>>> from sympy.solvers.diophantine import diop_ternary_quadratic
>>> diop_ternary_quadratic(3*x**2 + 4*y**2 - 5*z**2 + 4*x*y - 7*y*z + 7*z*x)
(-4, 5, 1)
diop_ternary_quadratic()
first converts the
given equation to an equivalent equation of the form and
then it uses
descent()
to solve the latter
equation. You can refer to the docs of
transformation_to_normal()
to find more on
this. The equation can be solved more easily by using the
Aforementioned
descent()
.
>>> from sympy.solvers.diophantine import descent
>>> descent(3, 1) # solves the equation w**2 = 3*Y**2 + Z**2
(1, 0, 1)
Here the solution tuple is in the order (w, Y, Z)
The extended Pythagorean equation,
and the
general sum of squares equation,
can
also be solved using the Diophantine module.
>>> from sympy.abc import a, b, c, d, e, f
>>> diophantine(9*a**2 + 16*b**2 + c**2 + 49*d**2 + 4*e**2 - 25*f**2)
set([(70*t1**2 + 70*t2**2 + 70*t3**2 + 70*t4**2 - 70*t5**2, 105*t1*t5, 420*t2*t5, 60*t3*t5, 210*t4*t5, 42*t1**2 + 42*t2**2 + 42*t3**2 + 42*t4**2 + 42*t5**2)])
function diop_general_pythagorean()
can
also be called directly to solve the same equation. This is true about the
general sum of squares too. Either you can call
diop_general_pythagorean()
or use the high
level API.
>>> diophantine(a**2 + b**2 + c**2 + d**2 + e**2 + f**2 - 112)
set([(8, 4, 4, 4, 0, 0)])
If you want to get a more thorough idea about the the Diophantine module please refer to the following blog.
References¶
[1] | Andreescu, Titu. Andrica, Dorin. Cucurezeanu, Ion. An Introduction to Diophantine Equations |
[2] | Diophantine Equation, Wolfram Mathworld, [online]. Available: http://mathworld.wolfram.com/DiophantineEquation.html |
[3] | Methods to solve Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0,[online], Available: http://www.alpertron.com.ar/METHODS.HTM |
[4] | Solving the equation ax^2+ bxy + cy^2 + dx + ey + f= 0, [online], Available: http://www.jpr2718.org/ax2p.pdf |
User Functions¶
These are functions that are imported into the global namespace with from
sympy import *
. These functions are intended for use by ordinary users of SymPy.
diophantine()
¶
-
sympy.solvers.diophantine.
diophantine
(eq, param=t)[source]¶ Simplify the solution procedure of diophantine equation
eq
by converting it into a product of terms which should equal zero.For example, when solving,
this is treated as
and
and
are solved independently and combined. Each term is solved by calling
diop_solve()
.Output of
diophantine()
is a set of tuples. Each tuple represents a solution of the input equation. In a tuple, solution for each variable is listed according to the alphabetic order of input variables. i.e. if we have an equation with two variablesand
, first element of the tuple will give the solution for
and the second element will give the solution for
.
See also
diop_solve
Examples
>>> from sympy.solvers.diophantine import diophantine >>> from sympy.abc import x, y, z >>> diophantine(x**2 - y**2) set([(-t_0, -t_0), (t_0, -t_0)])
#>>> diophantine(x*(2*x + 3*y - z)) #set([(0, n1, n2), (3*t - z, -2*t + z, z)]) #>>> diophantine(x**2 + 3*x*y + 4*x) #set([(0, n1), (3*t - 4, -t)])
Usage
diophantine(eq, t)
: Solve the diophantine equationeq
.t
is the parameter to be used bydiop_solve()
.Details
eq
should be an expression which is assumed to be zero.t
is the parameter to be used in the solution.
diop_solve()
¶
-
sympy.solvers.diophantine.
diop_solve
(eq, param=t)[source]¶ Solves the diophantine equation
eq
.Similar to
diophantine()
but doesn’t try to factoreq
as latter does. Usesclassify_diop()
to determine the type of the eqaution and calls the appropriate solver function.See also
diophantine
Examples
>>> from sympy.solvers.diophantine import diop_solve >>> from sympy.abc import x, y, z, w >>> diop_solve(2*x + 3*y - 5) (3*t_0 - 5, -2*t_0 + 5) >>> diop_solve(4*x + 3*y -4*z + 5) (t_0, -4*t_1 + 5, t_0 - 3*t_1 + 5) >>> diop_solve(x + 3*y - 4*z + w -6) (t_0, t_0 + t_1, -2*t_0 - 3*t_1 - 4*t_2 - 6, -t_0 - 2*t_1 - 3*t_2 - 6) >>> diop_solve(x**2 + y**2 - 5) set([(-2, -1), (-2, 1), (2, -1), (2, 1)])
Usage
diop_solve(eq, t)
: Solve diophantine equation,eq
usingt
as a parameter if needed.Details
eq
should be an expression which is assumed to be zero.t
is a parameter to be used in the solution.
classify_diop()
¶
-
sympy.solvers.diophantine.
classify_diop
(eq)[source]¶ Helper routine used by diop_solve() to find the type of the
eq
etc.Returns a tuple containing the type of the diophantine equation along with the variables(free symbols) and their coefficients. Variables are returned as a list and coefficients are returned as a dict with the key being the respective term and the constant term is keyed to Integer(1). Type is an element in the set {“linear”, “binary_quadratic”, “general_pythagorean”, “homogeneous_ternary_quadratic”, “univariate”, “general_sum_of_squares”}
Examples
>>> from sympy.solvers.diophantine import classify_diop >>> from sympy.abc import x, y, z, w, t >>> classify_diop(4*x + 6*y - 4) ([x, y], {1: -4, x: 4, y: 6}, 'linear') >>> classify_diop(x + 3*y -4*z + 5) ([x, y, z], {1: 5, x: 1, y: 3, z: -4}, 'linear') >>> classify_diop(x**2 + y**2 - x*y + x + 5) ([x, y], {1: 5, x: 1, x**2: 1, y: 0, y**2: 1, x*y: -1}, 'binary_quadratic')
Usage
classify_diop(eq)
: Return variables, coefficients and type of theeq
.Details
eq
should be an expression which is assumed to be zero.
diop_linear()
¶
-
sympy.solvers.diophantine.
diop_linear
(eq, param=t)[source]¶ Solves linear diophantine equations.
A linear diophantine equation is an equation of the form
where
are integer constants and
are integer variables.
See also
diop_quadratic
,diop_ternary_quadratic
,diop_general_pythagorean
,diop_general_sum_of_squares
Examples
>>> from sympy.solvers.diophantine import diop_linear >>> from sympy.abc import x, y, z, t >>> from sympy import Integer >>> diop_linear(2*x - 3*y - 5) #solves equation 2*x - 3*y -5 = 0 (-3*t_0 - 5, -2*t_0 - 5)
Here x = -3*t_0 - 5 and y = -2*t_0 - 5
>>> diop_linear(2*x - 3*y - 4*z -3) (t_0, -6*t_0 - 4*t_1 + 3, 5*t_0 + 3*t_1 - 3)
Usage
diop_linear(eq)
: Returns a tuple containing solutions to the diophantine equationeq
. Values in the tuple is arranged in the same order as the sorted variables.Details
eq
is a linear diophantine equation which is assumed to be zero.param
is the parameter to be used in the solution.
base_solution_linear()
¶
-
sympy.solvers.diophantine.
base_solution_linear
(c, a, b, t=None)[source]¶ Return the base solution for a linear diophantine equation with two variables.
Used by
diop_linear()
to find the base solution of a linear Diophantine equation. Ift
is given then the parametrized solution is returned.Examples
>>> from sympy.solvers.diophantine import base_solution_linear >>> from sympy.abc import t >>> base_solution_linear(5, 2, 3) # equation 2*x + 3*y = 5 (-5, 5) >>> base_solution_linear(0, 5, 7) # equation 5*x + 7*y = 0 (0, 0) >>> base_solution_linear(5, 2, 3, t) # equation 2*x + 3*y = 5 (3*t - 5, -2*t + 5) >>> base_solution_linear(0, 5, 7, t) # equation 5*x + 7*y = 0 (7*t, -5*t)
Usage
base_solution_linear(c, a, b, t)
:a
,b
,c
are coefficients inand
t
is the parameter to be used in the solution.
diop_quadratic()
¶
-
sympy.solvers.diophantine.
diop_quadratic
(eq, param=t)[source]¶ Solves quadratic diophantine equations.
i.e. equations of the form
. Returns a set containing the tuples
which contains the solutions. If there are no solutions then
is returned.
See also
diop_linear
,diop_ternary_quadratic
,diop_general_sum_of_squares
,diop_general_pythagorean
References
[R445] Methods to solve Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0,[online], Available: http://www.alpertron.com.ar/METHODS.HTM [R446] Solving the equation ax^2+ bxy + cy^2 + dx + ey + f= 0, [online], Available: http://www.jpr2718.org/ax2p.pdf Examples
>>> from sympy.abc import x, y, t >>> from sympy.solvers.diophantine import diop_quadratic >>> diop_quadratic(x**2 + y**2 + 2*x + 2*y + 2, t) set([(-1, -1)])
Usage
diop_quadratic(eq, param)
:eq
is a quadratic binary diophantine equation.param
is used to indicate the parameter to be used in the solution.Details
eq
should be an expression which is assumed to be zero.param
is a parameter to be used in the solution.
diop_DN()
¶
-
sympy.solvers.diophantine.
diop_DN
(D, N, t=t)[source]¶ Solves the equation
.
Mainly concerned in the case
is not a perfect square, which is the same as generalized Pell equation. To solve the generalized Pell equation this function Uses LMM algorithm. Refer [R447] for more details on the algorithm. Returns one solution for each class of the solutions. Other solutions of the class can be constructed according to the values of
D
andN
. Returns a list containing the solution tuples.
See also
find_DN
,diop_bf_DN
References
[R447] (1, 2) Solving the generalized Pell equation x**2 - D*y**2 = N, John P. Robertson, July 31, 2004, Pages 16 - 17. [online], Available: http://www.jpr2718.org/pell.pdf Examples
>>> from sympy.solvers.diophantine import diop_DN >>> diop_DN(13, -4) # Solves equation x**2 - 13*y**2 = -4 [(3, 1), (393, 109), (36, 10)]
The output can be interpreted as follows: There are three fundamental solutions to the equation
given by (3, 1), (393, 109) and (36, 10). Each tuple is in the form (x, y), i. e solution (3, 1) means that
and
.
>>> diop_DN(986, 1) # Solves equation x**2 - 986*y**2 = 1 [(49299, 1570)]
Usage
diop_DN(D, N, t)
: D and N are integers as inand
t
is the parameter to be used in the solutions.Details
D
andN
correspond to D and N in the equation.t
is the parameter to be used in the solutions.
cornacchia()
¶
-
sympy.solvers.diophantine.
cornacchia
(a, b, m)[source]¶ Solves
where
and
.
Uses the algorithm due to Cornacchia. The method only finds primitive solutions, i.e. ones with
. So this method can’t be used to find the solutions of
since the only solution to former is
and it is not primitive. When ` a = b = 1`, only the solutions with
are found. For more details, see the References.
References
[R448] - Nitaj, “L’algorithme de Cornacchia”
[R449] Solving the diophantine equation ax**2 + by**2 = m by Cornacchia’s method, [online], Available: http://www.numbertheory.org/php/cornacchia.html Examples
>>> from sympy.solvers.diophantine import cornacchia >>> cornacchia(2, 3, 35) # equation 2x**2 + 3y**2 = 35 set([(2, 3), (4, 1)]) >>> cornacchia(1, 1, 25) # equation x**2 + y**2 = 25 set([(4, 3)])
diop_bf_DN()
¶
-
sympy.solvers.diophantine.
diop_bf_DN
(D, N, t=t)[source]¶ Uses brute force to solve the equation,
.
Mainly concerned with the generalized Pell equation which is the case when
is not a perfect square. For more information on the case refer [R450]. Let
be the minimal positive solution of the equation
. Then this method requires
to be small.
See also
diop_DN
References
[R450] (1, 2) Solving the generalized Pell equation x**2 - D*y**2 = N, John P. Robertson, July 31, 2004, Page 15. http://www.jpr2718.org/pell.pdf Examples
>>> from sympy.solvers.diophantine import diop_bf_DN >>> diop_bf_DN(13, -4) [(3, 1), (-3, 1), (36, 10)] >>> diop_bf_DN(986, 1) [(49299, 1570)]
Usage
diop_bf_DN(D, N, t)
:D
andN
are coefficients inand
t
is the parameter to be used in the solutions.Details
D
andN
correspond to D and N in the equation.t
is the parameter to be used in the solutions.
transformation_to_DN()
¶
-
sympy.solvers.diophantine.
transformation_to_DN
(eq)[source]¶ This function transforms general quadratic,
to more easy to deal with
form.
This is used to solve the general quadratic equation by transforming it to the latter form. Refer [R451] for more detailed information on the transformation. This function returns a tuple (A, B) where A is a 2 X 2 matrix and B is a 2 X 1 matrix such that,
Transpose([x y]) = A * Transpose([X Y]) + B
See also
find_DN
References
[R451] (1, 2) Solving the equation ax^2 + bxy + cy^2 + dx + ey + f = 0, John P.Robertson, May 8, 2003, Page 7 - 11. http://www.jpr2718.org/ax2p.pdf Examples
>>> from sympy.abc import x, y >>> from sympy.solvers.diophantine import transformation_to_DN >>> from sympy.solvers.diophantine import classify_diop >>> A, B = transformation_to_DN(x**2 - 3*x*y - y**2 - 2*y + 1) >>> A Matrix([ [1/26, 3/26], [ 0, 1/13]]) >>> B Matrix([ [-6/13], [-4/13]])
A, B returned are such that Transpose((x y)) = A * Transpose((X Y)) + B. Substituting these values for
and
and a bit of simplifying work will give an equation of the form
.
>>> from sympy.abc import X, Y >>> from sympy import Matrix, simplify, Subs >>> u = (A*Matrix([X, Y]) + B)[0] # Transformation for x >>> u X/26 + 3*Y/26 - 6/13 >>> v = (A*Matrix([X, Y]) + B)[1] # Transformation for y >>> v Y/13 - 4/13
Next we will substitute these formulas for
and
and do
simplify()
.>>> eq = simplify(Subs(x**2 - 3*x*y - y**2 - 2*y + 1, (x, y), (u, v)).doit()) >>> eq X**2/676 - Y**2/52 + 17/13
By multiplying the denominator appropriately, we can get a Pell equation in the standard form.
>>> eq * 676 X**2 - 13*Y**2 + 884
If only the final equation is needed,
find_DN()
can be used.Usage
transformation_to_DN(eq)
: whereeq
is the quadratic to be transformed.
find_DN()
¶
-
sympy.solvers.diophantine.
find_DN
(eq)[source]¶ This function returns a tuple,
of the simplified form,
, corresponding to the general quadratic,
.
Solving the general quadratic is then equivalent to solving the equation
and transforming the solutions by using the transformation matrices returned by
transformation_to_DN()
.See also
transformation_to_DN
References
[R452] Solving the equation ax^2 + bxy + cy^2 + dx + ey + f = 0, John P.Robertson, May 8, 2003, Page 7 - 11. http://www.jpr2718.org/ax2p.pdf Examples
>>> from sympy.abc import x, y >>> from sympy.solvers.diophantine import find_DN >>> find_DN(x**2 - 3*x*y - y**2 - 2*y + 1) (13, -884)
Interpretation of the output is that we get
after transforming
using the transformation returned by
transformation_to_DN()
.Usage
find_DN(eq)
: whereeq
is the quadratic to be transformed.
diop_ternary_quadratic()
¶
-
sympy.solvers.diophantine.
diop_ternary_quadratic
(eq)[source]¶ Solves the general quadratic ternary form,
.
Returns a tuple
which is a base solution for the above equation. If there are no solutions,
is returned.
Examples
>>> from sympy.abc import x, y, z >>> from sympy.solvers.diophantine import diop_ternary_quadratic >>> diop_ternary_quadratic(x**2 + 3*y**2 - z**2) (1, 0, 1) >>> diop_ternary_quadratic(4*x**2 + 5*y**2 - z**2) (1, 0, 2) >>> diop_ternary_quadratic(45*x**2 - 7*y**2 - 8*x*y - z**2) (28, 45, 105) >>> diop_ternary_quadratic(x**2 - 49*y**2 - z**2 + 13*z*y -8*x*y) (9, 1, 5)
Usage
diop_ternary_quadratic(eq)
: Return a tuple containing a basic solution toeq
.Details
eq
should be an homogeneous expression of degree two in three variables and it is assumed to be zero.
square_factor()
¶
descent()
¶
-
sympy.solvers.diophantine.
descent
(A, B)[source]¶ Lagrange’s
with lattice-reduction to find solutions to
.
Here
and
should be square free and pairwise prime. Always should be called with suitable
A
andB
so that the above equation has solutions.This is more faster than the normal Lagrange’s descent algorithm because the gaussian reduction is used.
References
[R453] Efficient Solution of Rational Conices, J. E. Cremona and D. Rusin, Mathematics of Computation, Volume 00, Number 0. Examples
>>> from sympy.solvers.diophantine import descent >>> descent(3, 1) # x**2 = 3*y**2 + z**2 (1, 0, 1)
is a solution to the above equation.
>>> descent(41, -113) (-16, -3, 1)
diop_general_pythagorean()
¶
-
sympy.solvers.diophantine.
diop_general_pythagorean
(eq, param=m)[source]¶ Solves the general pythagorean equation,
.
Returns a tuple which contains a parametrized solution to the equation, sorted in the same order as the input variables.
Examples
>>> from sympy.solvers.diophantine import diop_general_pythagorean >>> from sympy.abc import a, b, c, d, e >>> diop_general_pythagorean(a**2 + b**2 + c**2 - d**2) (m1**2 + m2**2 - m3**2, 2*m1*m3, 2*m2*m3, m1**2 + m2**2 + m3**2) >>> diop_general_pythagorean(9*a**2 - 4*b**2 + 16*c**2 + 25*d**2 + e**2) (10*m1**2 + 10*m2**2 + 10*m3**2 - 10*m4**2, 15*m1**2 + 15*m2**2 + 15*m3**2 + 15*m4**2, 15*m1*m4, 12*m2*m4, 60*m3*m4)
Usage
diop_general_pythagorean(eq, param)
: whereeq
is a general pythagorean equation which is assumed to be zero andparam
is the base parameter used to construct other parameters by subscripting.
diop_general_sum_of_squares()
¶
-
sympy.solvers.diophantine.
diop_general_sum_of_squares
(eq, limit=1)[source]¶ Solves the equation
.
Returns at most
limit
number of solutions. Currently there is no way to setlimit
using higher level API’s likediophantine()
ordiop_solve()
but that will be fixed soon.Examples
>>> from sympy.solvers.diophantine import diop_general_sum_of_squares >>> from sympy.abc import a, b, c, d, e, f >>> diop_general_sum_of_squares(a**2 + b**2 + c**2 + d**2 + e**2 - 2345) set([(0, 48, 5, 4, 0)])
Usage
general_sum_of_squares(eq, limit)
: Hereeq
is an expression which is assumed to be zero. Also,eq
should be in the form,. At most
limit
number of solutions are returned.Details
When
if
for some
then there will be no solutions. Refer [R454] for more details.
Reference
[R454] Representing an Integer as a sum of three squares, [online], Available: http://www.proofwiki.org/wiki/Integer_as_Sum_of_Three_Squares
partition()
¶
-
sympy.solvers.diophantine.
partition
(n, k=None, zeros=False)[source]¶ Returns a generator that can be used to generate partitions of an integer
.
A partition of
is a set of positive integers which add upto
. For example, partitions of 3 are 3 , 1 + 2, 1 + 1+ 1. A partition is returned as a tuple. If
k
equals None, then all possible partitions are returned irrespective of their size, otherwise only the partitions of sizek
are returned. If there are no partions ofwith size
then an empty tuple is returned. If the
zero
parameter is set to True then a suitable number of zeros are added at the end of every partition of size less thank
.zero
parameter is considered only ifk
is not None. When the partitions are over, the lastcall throws the
StopIteration
exception, so this function should always be used inside a try - except block.Examples
>>> from sympy.solvers.diophantine import partition >>> f = partition(5) >>> next(f) (1, 1, 1, 1, 1) >>> next(f) (1, 1, 1, 2) >>> g = partition(5, 3) >>> next(g) (3, 1, 1) >>> next(g) (2, 2, 1)
Details
partition(n, k)
: Heren
is a positive integer andk
is the size of the partition which is also positive integer.Reference
[R455] Generating Integer Partitions, [online], Available: http://jeromekelleher.net/partitions.php
sum_of_three_squares()
¶
-
sympy.solvers.diophantine.
sum_of_three_squares
(n)[source]¶ Returns a 3-tuple
such that
and
.
Returns (None, None, None) if
for some
. See [R456] for more details.
References
[R456] (1, 2) Representing a number as a sum of three squares, [online], Available: http://www.schorn.ch/howto.html Examples
>>> from sympy.solvers.diophantine import sum_of_three_squares >>> sum_of_three_squares(44542) (207, 37, 18)
Usage
sum_of_three_squares(n)
: Heren
is a non-negative integer.
sum_of_four_squares()
¶
-
sympy.solvers.diophantine.
sum_of_four_squares
(n)[source]¶ Returns a 4-tuple
such that
.
Here
.
References
[R457] Representing a number as a sum of four squares, [online], Available: http://www.schorn.ch/howto.html Examples
>>> from sympy.solvers.diophantine import sum_of_four_squares >>> sum_of_four_squares(3456) (8, 48, 32, 8) >>> sum_of_four_squares(1294585930293) (0, 1137796, 2161, 1234)
Usage
sum_of_four_squares(n)
: Heren
is a non-negative integer.
Internal Functions¶
These functions are intended for the internal use in Diophantine module.
merge_solution
¶
-
sympy.solvers.diophantine.
merge_solution
(var, var_t, solution)[source]¶ This is used to construct the full solution from the solutions of sub equations.
For example when solving the equation
, solutions for each of the equations
and
are found independently. Solutions for
are
. But we should introduce a value for z when we output the solution for the original equation. This function converts
into
where
is an integer parameter.
divisible
¶
extended_euclid
¶
-
sympy.solvers.diophantine.
extended_euclid
(a, b)[source]¶ For given
a
,b
returns a tuple containing integers,
and
such that
. Here
.
Examples
>>> from sympy.solvers.diophantine import extended_euclid >>> extended_euclid(4, 6) (-1, 1, 2) >>> extended_euclid(3, 5) (2, -1, 1)
Usage
extended_euclid(a, b)
: returns,
and
.
Details
a
Any instance of Integer.b
Any instance of Integer.
PQa
¶
-
sympy.solvers.diophantine.
PQa
(P_0, Q_0, D)[source]¶ Returns useful information needed to solve the Pell equation.
There are six sequences of integers defined related to the continued fraction representation of
, namely {
}, {
}, {
},{
}, {
}, {
}.
PQa()
Returns these values as a 6-tuple in the same order as mentioned above. Refer [R458] for more detailed information.References
[R458] (1, 2) Solving the generalized Pell equation x^2 - Dy^2 = N, John P. Robertson, July 31, 2004, Pages 4 - 8. http://www.jpr2718.org/pell.pdf Examples
>>> from sympy.solvers.diophantine import PQa >>> pqa = PQa(13, 4, 5) # (13 + sqrt(5))/4 >>> next(pqa) # (P_0, Q_0, a_0, A_0, B_0, G_0) (13, 4, 3, 3, 1, -1) >>> next(pqa) # (P_1, Q_1, a_1, A_1, B_1, G_1) (-1, 1, 1, 4, 1, 3)
Usage
PQa(P_0, Q_0, D)
:P_0
,Q_0
andD
are integers corresponding to,
and
in the continued fraction
. Also it’s assumed that
and
is square free.
equivalent
¶
-
sympy.solvers.diophantine.
equivalent
(u, v, r, s, D, N)[source]¶ Returns True if two solutions
and
of
belongs to the same equivalence class and False otherwise.
Two solutions
and
to the above equation fall to the same equivalence class iff both
and
are divisible by
. See reference [R459]. No test is performed to test whether
and
are actually solutions to the equation. User should take care of this.
References
[R459] (1, 2) Solving the generalized Pell equation x**2 - D*y**2 = N, John P. Robertson, July 31, 2004, Page 12. http://www.jpr2718.org/pell.pdf Examples
>>> from sympy.solvers.diophantine import equivalent >>> equivalent(18, 5, -18, -5, 13, -1) True >>> equivalent(3, 1, -18, 393, 109, -4) False
Usage
equivalent(u, v, r, s, D, N)
:and
are two solutions of the equation
and all parameters involved are integers.
parametrize_ternary_quadratic
¶
-
sympy.solvers.diophantine.
parametrize_ternary_quadratic
(eq)[source]¶ Returns the parametrized general solution for the ternary quadratic equation
eq
which has the form.
References
[R460] The algorithmic resolution of Diophantine equations, Nigel P. Smart, London Mathematical Society Student Texts 41, Cambridge University Press, Cambridge, 1998. Examples
>>> from sympy.abc import x, y, z >>> from sympy.solvers.diophantine import parametrize_ternary_quadratic >>> parametrize_ternary_quadratic(x**2 + y**2 - z**2) (2*p*q, p**2 - q**2, p**2 + q**2)
Here
and
are two co-prime integers.
>>> parametrize_ternary_quadratic(3*x**2 + 2*y**2 - z**2 - 2*x*y + 5*y*z - 7*y*z) (2*p**2 - 2*p*q - q**2, 2*p**2 + 2*p*q - q**2, 2*p**2 - 2*p*q + 3*q**2) >>> parametrize_ternary_quadratic(124*x**2 - 30*y**2 - 7729*z**2) (-1410*p**2 - 363263*q**2, 2700*p**2 + 30916*p*q - 695610*q**2, -60*p**2 + 5400*p*q + 15458*q**2)
diop_ternary_quadratic_normal
¶
-
sympy.solvers.diophantine.
diop_ternary_quadratic_normal
(eq)[source]¶ Solves the quadratic ternary diophantine equation,
.
Here the coefficients
,
, and
should be non zero. Otherwise the equation will be a quadratic binary or univariate equation. If solvable, returns a tuple
that satisifes the given equation. If the equation does not have integer solutions,
is returned.
Examples
>>> from sympy.abc import x, y, z >>> from sympy.solvers.diophantine import diop_ternary_quadratic_normal >>> diop_ternary_quadratic_normal(x**2 + 3*y**2 - z**2) (1, 0, 1) >>> diop_ternary_quadratic_normal(4*x**2 + 5*y**2 - z**2) (1, 0, 2) >>> diop_ternary_quadratic_normal(34*x**2 - 3*y**2 - 301*z**2) (4, 9, 1)
Usage
diop_ternary_quadratic_normal(eq)
: whereeq
is an equation of the form.
ldescent
¶
-
sympy.solvers.diophantine.
ldescent
(A, B)[source]¶ Uses Lagrange’s method to find a non trivial solution to
.
Here,
and
and
and
are square free. Output a tuple
which is a solution to the above equation.
References
[R461] The algorithmic resolution of Diophantine equations, Nigel P. Smart, London Mathematical Society Student Texts 41, Cambridge University Press, Cambridge, 1998. [R462] Efficient Solution of Rational Conices, J. E. Cremona and D. Rusin, Mathematics of Computation, Volume 00, Number 0. Examples
>>> from sympy.solvers.diophantine import ldescent >>> ldescent(1, 1) # w^2 = x^2 + y^2 (1, 1, 0) >>> ldescent(4, -7) # w^2 = 4x^2 - 7y^2 (2, -1, 0)
This means that
and
is a solution to the equation
>>> ldescent(5, -1) # w^2 = 5x^2 - y^2 (2, 1, -1)
gaussian_reduce
¶
-
sympy.solvers.diophantine.
gaussian_reduce
(w, a, b)[source]¶ Returns a reduced solution
to the congruence
so that
is minimal.
References
[R463] Gaussian lattice Reduction [online]. Available: http://home.ie.cuhk.edu.hk/~wkshum/wordpress/?p=404 [R464] Efficient Solution of Rational Conices, J. E. Cremona and D. Rusin, Mathematics of Computation, Volume 00, Number 0. Details
Here
w
is a solution of the congruence
holzer
¶
prime_as_sum_of_two_squares
¶
-
sympy.solvers.diophantine.
prime_as_sum_of_two_squares
(p)[source]¶ Represent a prime
which is congruent to 1 mod 4, as a sum of two squares.
Examples
>>> from sympy.solvers.diophantine import prime_as_sum_of_two_squares >>> prime_as_sum_of_two_squares(5) (2, 1)
Reference
[R465] Representing a number as a sum of four squares, [online], Available: http://www.schorn.ch/howto.html
pairwise_prime
¶
-
sympy.solvers.diophantine.
pairwise_prime
(a, b, c)[source]¶ Transform
into an equivalent equation
where
are pairwise relatively prime.
Returns a tuple containing
.
should equal
for this to work. The solutions for
can be recovered from the solutions of
.
See also
make_prime
,reocnstruct
Examples
>>> from sympy.solvers.diophantine import pairwise_prime >>> pairwise_prime(6, 15, 10) (5, 2, 3)
make_prime
¶
-
sympy.solvers.diophantine.
make_prime
(a, b, c)[source]¶ Transform the equation
to an equivalent equation
with
.
Returns a tuple
which satisfies above conditions. Note that in the returned tuple
and
can take any value.
See also
pairwaise_prime
,reconstruct
Examples
>>> from sympy.solvers.diophantine import make_prime >>> make_prime(4, 2, 7) (2, 1, 14)