Many Diophantine problems include restrictions beyond the requirement that variables be integers. For example, a problem may require positive integers, nonnegative integers, distinct integers, or integers within a specified range. These restrictions are called constraints. A complete solution must satisfy both the original equation and every stated constraint. An equation may have infinitely many integer solutions but only finitely many positive or bounded solutions. For example, x + y = 10 has infinitely many integer solutions, but only eleven solutions when both variables are required to be nonnegative integers. Several techniques can help apply constraints. Inequalities can restrict the possible range of variables, parity arguments can eliminate certain cases, and modular arithmetic can determine which residues are possible. Divisibility conditions can further narrow the solution set. Parameterization is especially useful because it expresses all integer solutions in terms of integer parameters, after which the constraints can be translated into restrictions on those parameters.
Integer Solutions and Constraints
Integer solutions and constraints concern finding integer values that satisfy an equation while also obeying additional conditions such as positivity, nonnegativity, parity, divisibility, or upper and lower bounds.
Find (x₁, x₂, ..., xₖ) ∈ ℤᵏ such that P(x₁, ..., xₖ) = 0 and C₁, C₂, ..., Cₘ are all satisfied.
Explanation
Variables
X₁, ..., xₖ
Unknown integer variables.
P
The equation or polynomial expression that must be satisfied.
C₁, ..., Cₘ
Additional constraints such as positivity, parity, divisibility, or bounds.
ℤᵏ
The set of all k-tuples of integers.
Example or application
Problem
Find all nonnegative integer solutions of x + y = 6.
Solution
Because x and y must be nonnegative integers, x can take only the values 0 through 6. For each value of x, y is determined by y = 6 − x. The resulting pairs are (0, 6), (1, 5), (2, 4), (3, 3), (4, 2), (5, 1), and (6, 0).
Answer
There are 7 nonnegative integer solutions.
Text
Integer constraints determine which members of a general integer solution set are acceptable. A correct solution must satisfy the equation and all restrictions simultaneously; satisfying only one part of the problem is insufficient.
Key Points
Integer solutions must satisfy the equation using integer values.
Constraints provide additional restrictions on acceptable solutions.
Positive integers are greater than zero.
Nonnegative integers include zero and positive integers.
Parity conditions distinguish even and odd possibilities.
Upper and lower bounds can make an otherwise infinite solution set finite.
Parameterization helps convert constraints into restrictions on integer parameters.
Every final candidate must be checked against both the equation and the constraints.
Constraint Types
| Name | Description |
|---|---|
Positive Integer Constraints | Every unknown must be a positive integer, so zero and negative values are excluded. |
Nonnegative Integer Constraints | Every unknown must be greater than or equal to zero. |
Parity Constraints | Unknowns may be required to be even, odd, or to have a specified parity relationship. |
Divisibility Constraints | An unknown or expression must be divisible by a specified integer. |
Distinctness Constraints | The unknowns must have different integer values. |
Bounded Integer Constraints | Unknowns must lie within specified minimum and maximum values. |
Methods
| Name | Description |
|---|---|
Parameterization | Express the general integer solution using one or more integer parameters. |
Inequality Analysis | Use upper and lower bounds to restrict the possible values of variables. |
Parity Analysis | Determine whether variables must be even or odd. |
Modular Arithmetic | Use congruences to restrict the possible residues of variables. |
Systematic Enumeration | Check a finite set of candidates when the constraints establish clear bounds. |
Applications
Solving integer optimization and allocation problems.
Finding whole-number combinations under fixed limits.
Analyzing mathematical puzzles involving integer restrictions.
Solving counting and scheduling problems.
Determining possible integer dimensions or quantities.
Reducing general Diophantine solutions to specific valid cases.
Learning Outcomes
Distinguish integer, positive-integer, and nonnegative-integer solutions.
Identify all constraints in a Diophantine problem.
Apply inequalities and parity to restrict possible values.
Translate parameterized solutions into valid constrained solutions.
Verify that every final solution satisfies all requirements.
Practice Questions
Find all positive integer solutions of x + y = 8.
Find all nonnegative integer solutions of 2x + y = 7.
Determine the integer solutions of x + y = 10 when x and y must be distinct positive integers.
Find all even integers x satisfying 2x + 4y = 20 for some integer y.
Explain why a bounded integer problem may have finitely many solutions.
How can modular arithmetic help when variables are restricted to particular parity classes?
Related Concepts
Diophantine Equations
Linear Diophantine Equations
Integer Inequalities
Divisibility
Parity
Modular Arithmetic
Combinatorics
Common Mistakes
Including zero when only positive integers are allowed.
Excluding zero when nonnegative integers are allowed.
Checking the equation but ignoring the additional constraints.
Assuming that a parameter can take real values when it must be an integer.
Failing to establish bounds before claiming that all solutions have been listed.
Counting the same solution more than once.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- David M. Burton, Elementary Number Theory
- Kenneth H. Rosen, Elementary Number Theory and Its Applications
- Titu Andreescu and Dorin Andrica, An Introduction to Diophantine Equations
Suggest a correction or source · More in Arithmetic & Number Theory