Thread by @susam

It took me a while to realize what this picture on the cover of the book "Introduction to Analytic Number Theory" (Apostol, 1976) really means.

Special thanks to @LavaboMouille for helping me interpret this picture correctly.

On the horizontal axis we have x = 0, 1, 2, ..., 17. On the vertical axis we have y = 0, 1, 2, ..., 17. A cell exists at (x, y) if and only if gcd(x, y) ≠ 1.

In other words, a cell exists at (x, y) if and only if x and y are not relatively prime to each other.

When x = 1, we get gcd(x, y) = 1 for every integer y, so the column at x = 1 is completely empty. Similarly, the row at y = 1 is also completely empty.

When x = 0 and y ≠ 1, we get gcd(x, y) = |y| ≠ 1, so the entire column at x = 0 has cells except at (0, 1). Similarly, the entire row at y = 0 has cells except at (1, 0).

Note that (0, 0) must have a cell because gcd(0, 0) = 0 ≠ 1.

Does 0 really divide 0? Isn't 0/0 undefined? Yes, 0 indeed divides 0 even though 0/0 is undefined.

We say an integer d divides an integer n when n = cd for some integer c. We have 0 = 0 · 0, so indeed 0 divides 0.

Is gcd(0, 0) = 0 really? Every integer divides 0, e.g., 1 divides 0, 2 divides 0, 3 divides 0, etc. There does not seem to be a greatest common divisor of 0 and 0. Shouldn't gcd(0, 0) be called either infinity or undefined?

Well, gcd(x, y) must satisfy certain properties. One of them is that every common divisor of x and y must also divide gcd(x, y). We define gcd(0, 0) = 0 and it does satisfy this property. Further, this definition makes gcd(0, y) = |y| for every integer y.

Also, defining gcd(0, 0) = 0 makes Bézout's identity work for all integers.

Bézout's identity: There exists integers m and n such that mx + ny = gcd(x, y).

Indeed if we define gcd(0, 0) = 0, we get 0 · 0 + 0 · 0 = 0.

Note that the diagonal y = x always has a cell except at (1, 1) because gcd(x, x) = |x| for all integers x. Once again, this simple result is possible due to defining gcd(0, 0) = 0.

The picture is symmetric about the diagonal y = x because gcd(x, y) = gcd(y, x).

Can we spot the primes easily? A column at x has exactly one cell below the diagonal if and only if x is prime.

Check the column for x = 5. It has exactly one cell below the diagonal. 5 is prime.

Now check the column for x = 6. It has 4 cells below the diagonal. 6 is not prime.