Chapter 2. Classical Number Theory

Equations in Integers

A Diophantine equation is an equation whose solutions are required to be integers. The unknowns are not allowed to range over the real numbers or complex numbers unless explicitly stated. This restriction changes the nature of the problem.

For example, the equation

has many real solutions, but number theory asks for integer solutions. One such solution is

since

A linear Diophantine equation in two unknowns has the form

where $a,b,c\in\mathbb{Z}$, and the goal is to find all pairs $(x,y)\in\mathbb{Z}^2$ satisfying the equation.

The Divisibility Condition

The basic question is whether a solution exists at all. The answer is controlled by the greatest common divisor of $a$ and $b$.

Let

Since $d\mid a$ and $d\mid b$, we have

and

for all integers $x$ and $y$. Therefore,

Thus, if

has an integer solution, then necessarily

This gives a necessary condition. It is also sufficient.

Existence Theorem

Theorem. Let $a,b,c\in\mathbb{Z}$, not both $a$ and $b$ equal to zero, and let

The equation

has an integer solution if and only if

If $d\mid c$, then all integer solutions can be obtained from one particular solution.

By Bézout’s identity, there exist integers $u$ and $v$ such that

If $d\mid c$, write

for some integer $m$. Multiplying the Bézout identity by $m$, we get

Hence

is an integer solution.

Conversely, if $ax+by=c$ has an integer solution, then $d\mid ax+by$, so $d\mid c$. This proves the theorem.

Description of All Solutions

Suppose $(x_0,y_0)$ is one integer solution of

Then

If $(x,y)$ is another solution, then

Subtracting the two equations gives

Thus

Let $d=\gcd(a,b)$, and write

where

Then

Since $a'$ and $b'$ are coprime, $b'\mid x-x_0$. Hence there exists an integer $t$ such that

Substituting back gives

Therefore all integer solutions are

where $t\in\mathbb{Z}$.

Example

Consider

Here

and

So integer solutions exist. Dividing by $7$, we get

One solution is

since

The general solution is

where $t\in\mathbb{Z}$.

For example, taking $t=0,1,-1$, we obtain

Each satisfies the original equation.

Geometric Interpretation

Over the real numbers, the equation

describes a line in the plane. A linear Diophantine equation asks which lattice points lie on this line. Here a lattice point means a point whose coordinates are both integers.

The divisibility condition

says exactly when the line passes through at least one lattice point. Once it passes through one lattice point, the full set of lattice points on the line forms an infinite arithmetic progression in two dimensions:

Thus a linear Diophantine equation has either no integer solutions or infinitely many integer solutions.