[Introduction to Number Theory Series Part 7] When Does a Linear Diophantine Equation Have Integer Solutions?

A linear Diophantine equation asks for integer solutions, not just real ones. That restriction changes the problem completely.

What this post covers

• What a linear Diophantine equation is
• The necessary and sufficient condition for integer solutions
• Examples with and without solutions
• Why the problem has a structural connection to the gcd

Key terms

• linear Diophantine equation: an equation of the form ax+by=c studied over the integers
• Bézout's identity: the identity that expresses the gcd as ax+by
• greatest common divisor: the largest positive common divisor of two integers
• coprime: having gcd 1

The main question

When does

$$ax+by=c$$

have integer solutions?

The answer is precise:

ax+by=c has an integer solution if and only if gcd(a,b) divides c.

In symbols,

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

Why does this condition appear?

Let d=gcd(a,b). Since d divides both a and b, any value of ax+by must also be a multiple of d. So if the equation is going to equal c, then c must also be a multiple of d.

Conversely, if d | c, then c=dk for some integer k. By Bézout's identity, there exist integers x_0,y_0 such that

$$ax_0+by_0=d.$$

Multiplying by k gives

$$a(kx_0)+b(ky_0)=c,$$

so an integer solution exists.

Example 1: a solvable case

Consider

$$6x+9y=3.$$

Since

$$\gcd(6,9)=3$$

and 3 divides 3, solutions exist. For instance,

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

Example 2: an unsolvable case

Now consider

$$6x+9y=4.$$

Again gcd(6,9)=3, but 3 does not divide 4. So there are no integer solutions.

What if the numbers are coprime?

If a and b are coprime, then gcd(a,b)=1. Since 1 divides every integer, ax+by=c always has integer solutions in that case. So the coprime case is the simplest possible existence pattern.

After finding one solution

A linear Diophantine equation rarely has just one integer solution. Once one solution is known, the full family of solutions can be described. At this stage, the key thing to remember is the order of thought: first check the gcd condition, then find one solution, and only after that think about the whole family.

Common mistakes

1. Confusing real solutions with integer solutions

Real solutions may exist even when integer solutions do not.

2. Forgetting to check the gcd condition first

Before solving, ask whether gcd(a,b) divides the right-hand side.

3. Assuming there is only one solution

Usually there is a pattern of solutions, not a single isolated answer.

Wrap-up

The equation ax+by=c has integer solutions exactly when gcd(a,b) divides c. That is one of the clearest examples of how the gcd controls structure.

Next we turn to primes, the basic building blocks of integer factorization.