Proofs of Existence and Optimality · Constructive Proofs of Existence

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Yes, a number ending in \(15\) and divisible by \(13\) exists: \(715 = 13\cdot 55\). This is a clear example of a constructive proof of existence: to prove that the desired object exists, we simply present it. In the proof itself, we may not explain how exactly the desired object was found. The number \(715\) could have been found by manual enumeration, with the help of a computer, or even seen in a dream. The code below finds all such numbers in the interval \([0, 9\ 999]\).

for n in range(10 ** 4):
    if n % 13 == 0 and n % 100 == 15:
        print(n)

The following code finds just the first such number.

from itertools import count

print(next(n for n in count() if n % 13 == 0 and n % 100 == 15))

However, a number ending in \(13\) and divisible by \(15\) does not exist: if a number is divisible by \(15\), it ends in \(0\) or \(5\).