# 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

$$
2x+3y=1
$$

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

$$
x=-1,\qquad y=1,
$$

since

$$
2(-1)+3(1)=1.
$$

A linear Diophantine equation in two unknowns has the form

$$
ax+by=c,
$$

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

$$
d=\gcd(a,b).
$$

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

$$
d\mid ax
$$

and

$$
d\mid by
$$

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

$$
d\mid ax+by.
$$

Thus, if

$$
ax+by=c
$$

has an integer solution, then necessarily

$$
d\mid c.
$$

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

$$
d=\gcd(a,b).
$$

The equation

$$
ax+by=c
$$

has an integer solution if and only if

$$
d\mid c.
$$

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

$$
au+bv=d.
$$

If $d\mid c$, write

$$
c=dm
$$

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

$$
a(um)+b(vm)=dm=c.
$$

Hence

$$
x_0=um,\qquad y_0=vm
$$

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

$$
ax+by=c.
$$

Then

$$
ax_0+by_0=c.
$$

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

$$
ax+by=c.
$$

Subtracting the two equations gives

$$
a(x-x_0)+b(y-y_0)=0.
$$

Thus

$$
a(x-x_0)=-b(y-y_0).
$$

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

$$
a=da',\qquad b=db',
$$

where

$$
\gcd(a',b')=1.
$$

Then

$$
a'(x-x_0)=-b'(y-y_0).
$$

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

$$
x-x_0=b't.
$$

Substituting back gives

$$
y-y_0=-a't.
$$

Therefore all integer solutions are

$$
x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t,
$$

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

## Example

Consider

$$
14x+21y=35.
$$

Here

$$
\gcd(14,21)=7,
$$

and

$$
7\mid 35.
$$

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

$$
2x+3y=5.
$$

One solution is

$$
x=1,\qquad y=1,
$$

since

$$
2(1)+3(1)=5.
$$

The general solution is

$$
x=1+3t,\qquad y=1-2t,
$$

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

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

$$
(1,1),\qquad (4,-1),\qquad (-2,3).
$$

Each satisfies the original equation.

## Geometric Interpretation

Over the real numbers, the equation

$$
ax+by=c
$$

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

$$
\gcd(a,b)\mid c
$$

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:

$$
(x,y)=
\left(
x_0+\frac{b}{d}t,\,
y_0-\frac{a}{d}t
\right),
\qquad t\in\mathbb{Z}.
$$

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