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 233–234 of | |

Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective, | |

Springer-Verlag, 1982. ISBN 0–387–90652–5. | |

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

L_{i} = b_{i} (0 ≤ i < k) | (1) |

_{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) |

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

L_{0} = b_{0} | |

L_{1} = b_{1} (3) |

and |
L_{i} = b_{i} for 2 ≤ 1 < | (4) |

Consider for natural P_{0} and P_{1}, to be chosen later, the equation

P_{0} * L_{0} + P_{1} * L_{1}= P_{0} * b_{0} + P_{1} * b_{1} | (5) |

_{0}and P

_{1}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

_{0}and P

_{1}in such a way that (5), considered as an equation in L

_{0}and L

_{1}, has (3) as its

**only**natural solution; because all natural choices for the original unknowns will give rise to natural L

_{0}and L

_{1}, this is sufficient.

Considered as an equation in L_{0} and L_{1} , the general parametric
solution of (5) is given by
L_{0} = b_{0} + t * P_{1}
L_{1} = b_{1} - t * P_{0}
(where, to start with, t need not be a natural number). We shall choose a
natural P_{0} and P_{1} in such a way that from natural L_{0} and L_{1} , viz.

b_{0} + t * P_{1} ≥ 0 | (6) | |

b_{1} - t * P_{0} ≥ 0 | (7) | |

left-hand sides of (6) and (7) integer | (8) |

Choosing P_{1} > b , we derive from (6)

t > -1 | (9) |

Choosing P_{0} > b_{1} , we derive from (7)

t < 1 | (10) |

Choosing P_{0} and P_{1} furthermore such that gcd(P_{0}, P_{1}) = 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

P_{0} > b_{1}, P_{1} > b_{0} , gcd(P_{0}, P_{1}) = 1 |

* *

*

**Example**. Let the given set be x = 1, y = 1, z = 1 . The first two equations
can be combined by choosing P_{0} = 2 and P_{1} = 3, yielding:

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

_{0}= 2 and P

_{1}= 7, yielding

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

3 August 1976

Plataanstraat 5

NL-4565 NUENEN

The Netherlands

Transcribed by Martin P.M. van der Burgt

Last revision