A linear integer equation is a first-degree equation whose unknown variables are restricted to integers. Problems may involve one variable, two variables, or several variables. In a single-variable equation ax = b, an integer solution exists exactly when a divides b, assuming a is nonzero. For two variables, the standard equation ax + by = c is governed by the greatest common divisor condition. Equations involving several variables can be approached by extending the same linear-combination principle. A systematic solution usually begins by examining divisibility and simplifying the coefficients. The extended Euclidean algorithm can then produce a particular solution when necessary. The complete solution set is expressed using integer parameters. If the problem includes restrictions such as nonnegative values, positive values, or upper bounds, these conditions must be applied to the general solution. This distinction is important because an equation may have infinitely many integer solutions but only a few solutions satisfying the additional conditions.
Solving Linear Integer Equations
Solving linear integer equations involves finding all integer values of the unknown variables that satisfy a linear equation, often by using divisibility, greatest common divisors, parameterization, and additional constraints.
For ax = b with a ≠ 0: x = b/a ∈ ℤ ⇔ a | b. For ax + by = c: gcd(a, b) | c.
Explanation
Variables
A, b
Integer coefficients.
C
An integer constant.
X, y
Unknown integer variables.
D
The greatest common divisor of the relevant coefficients.
T
An integer parameter used in the general solution.
Example or application
Problem
Find all nonnegative integer solutions of 4x + 6y = 26.
Solution
First divide by 2 to obtain 2x + 3y = 13. Since 2x is even and 13 is odd, 3y must be odd, so y must be odd. Testing nonnegative odd values of y gives y = 1, 3, and 5. These produce x = 5, 2, and −1, respectively. The last value is not nonnegative, so it is excluded.
Answer
The nonnegative integer solutions are (x, y) = (5, 1) and (2, 3).
Text
A complete solution to a linear integer equation requires identifying the allowed integer values, not merely solving the equation over the real numbers. Divisibility tests and parameterization help establish both existence and completeness.
Key Points
The unknown variables must belong to the integers.
A single-variable linear equation has an integer solution only when the required divisibility condition holds.
The greatest common divisor determines solvability for two-variable linear equations.
The extended Euclidean algorithm can produce particular solutions.
Parameterization is used to describe all integer solutions.
Nonnegative, positive, or bounded restrictions must be applied after obtaining the general solution.
Parity and divisibility arguments can simplify many integer-equation problems.
Properties
Integer solutions form a restricted subset of the corresponding real solutions.
A linear equation with two unknowns may have infinitely many integer solutions.
A divisibility condition can rule out solutions without solving the equation completely.
The parity of variables may impose restrictions on possible values.
A general parameter must be an integer to preserve integer solutions.
Additional inequalities can turn an infinite solution set into a finite set.
Methods
| Name | Description |
|---|---|
Divisibility Analysis | Check whether the coefficients and constant satisfy the necessary divisibility conditions. |
Greatest Common Divisor | Use the greatest common divisor of the coefficients to determine whether integer solutions exist. |
Extended Euclidean Algorithm | Find a particular solution to a solvable linear equation. |
Parameterization | Express all integer solutions using one or more integer parameters. |
Constraint Analysis | Apply positivity, nonnegativity, parity, and upper or lower bounds to select valid solutions. |
Applications
Solving exact quantity and allocation problems.
Analyzing combinations of whole-number units.
Finding integer solutions in algebraic word problems.
Solving scheduling and counting problems with integer restrictions.
Understanding linear combinations and divisibility.
Learning Outcomes
Solve single-variable linear equations under integer restrictions.
Apply divisibility and greatest common divisor tests.
Find and express integer solutions using parameters.
Use parity and divisibility to reduce possible cases.
Apply nonnegative and positive constraints correctly.
Practice Questions
Determine whether 7x = 45 has an integer solution.
Find all integer solutions of 3x + 5y = 16.
Find all nonnegative integer solutions of 2x + 4y = 18.
Explain how parity can help solve 5x + 3y = 14.
Solve 9x + 12y = 30 and express the complete solution set.
What is the difference between an integer solution and a nonnegative integer solution?
Related Concepts
Linear Diophantine Equations
Divisibility
Greatest Common Divisor
Extended Euclidean Algorithm
Integer Solutions and Constraints
Parity
Common Mistakes
Accepting non-integer solutions when the problem requires integers.
Ignoring the divisibility condition.
Stopping after finding one solution.
Applying nonnegative restrictions before obtaining a correct general solution.
Forgetting to check every candidate against the original equation.
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
Suggest a correction or source · More in Arithmetic & Number Theory