A proof of a theorem communicated to us by S.Ghosh

---

NOTE: This transcription was contributed by Martin P.M. van der Burgt, who has devised a process for producing transcripts automatically. Although its markup is incomplete, we believe it serves a useful purpose by virtue of its searchability and its accessibility to text-reading software. It will be replaced by a fully marked-up version when time permits. —HR

---

Copyright Notice
The following manuscript
	EWD 582 A proof of a theorem communicated to us by S.Ghosh (with C.S.Scholten) :
is held in copyright by Springer-Verlag New York.
The manuscript was published as pages 233234 of
	Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective,
	Springer-Verlag, 1982. ISBN 0387906525.
Reproduced with permission from Springer-Verlag New York.
Any further reproduction is strictly prohibited.

A proof of a theorem communicated to us by S.Ghosh.

by Edsger W.Dijkstra and C.S.Scholten

In a letter of 19 August 1976, S.Ghosh (currently c/o Lehrstuhl Informatik I, Universitat Dortmund, Western Germany) communicated without proof the following theorem in natural numbers —here chosen to mean “nonnegative integers”— :

Given a set of k linear equations of the form

Li = bi (0 ≤ i < k)

(1)

in which the L_i are homogeneous linear expressions in the unknowns with natural coefficients and the b_i are natural numbers, there exists a single equation

M = c

(2)

in which M is a homogeneous linear expression in the unknowns with natural coefficients and c is a natural number, such that (2) has the same natural solutions as (1).

Because the natural solutions of (1) are the common natural solutions of (3) and (4), as given by

	L0 = b0
	L1 = b1 (3)

and

Li = bi for 2 ≤ 1 <

(4)

it suffices to prove that (3) can be replaced by a single equation with the same natural solutions as (3).

Consider for natural P₀ and P₁, to be chosen later, the equation

P0 * L0 + P1 * L1= P0 * b0 + P1 * b1

(5)

All solutions of (3) are solutions of (5). We shall show that and P₀ and P₁ can be chosen in such a way, that, conversely, all natural solutions of (5) are solutions of (3). We shall do so by choosing P₀ and P₁ in such a way that (5), considered as an equation in L₀ and L₁ , has (3) as its only natural solution; because all natural choices for the original unknowns will give rise to natural L₀ and L₁ , this is sufficient.

Considered as an equation in L₀ and L₁ , the general parametric solution of (5) is given by L₀ = b₀ + t * P₁ L₁ = b₁ - t * P₀ (where, to start with, t need not be a natural number). We shall choose a natural P₀ and P₁ in such a way that from natural L₀ and L₁ , viz.

	b0 + t * P1 ≥ 0	(6)
	b1 - t * P0 ≥ 0	(7)
	left-hand sides of (6) and (7) integer	(8)

we can conclude t = 0 .

Choosing P₁ > b , we derive from (6)

t > -1

(9)

Choosing P₀ > b₁ , we derive from (7)

t < 1

(10)

Choosing P₀ and P₁ furthermore such that gcd(P₀, P₁) = 1 , we derive From (8) that t must be integer; in view of (9) and (10) we conclude that t = 0 holds. Summarizing: (5) can replace (3) provided

P0 > b1, P1 > b0 , gcd(P0, P1) = 1

*              *
*

Example. Let the given set be x = 1, y = 1, z = 1 . The first two equations can be combined by choosing P₀ = 2 and P₁ = 3, yielding:

2*x + 3*y = 5 , z = 1 .

These two can be combined by choosing P₀ = 2 and P₁ = 7, yielding

4*x + 6*y + 7*z = 17

for which (1,1,1) is, indeed, the only natural solution. (End of example.)

3 August 1976
Plataanstraat 5
NL-4565 NUENEN
The Netherlands

---

Transcribed by Martin P.M. van der Burgt
Last revision 2015-01-23 .