1 Monty: You're living dangerously, invading the Vatican, Haken.
2 Haken: Die Catholic Church will cower before die might of Nazi science!
3 Monty: I wouldn't bet on it. Just the other day they announced a brand new algorithm to determine the greatest common divisor of two numbers.
4 Haken: Bah! In this algorithm, how many divisions does the Pope have?

The greatest common divisor (GCD) of two integers is the largest integer that divides into both of them with no remainder. For example, the CGD of 28 and 36 is 4, because 4 divides evenly into 28 (7 times), and 36 (9 times), but no number larger than 4 does so.

Given two integers, finding the GCD of them requires some calculation, most commonly done using an ancient method known as Euclid's algorithm, after the great Greek mathematician and geometer Euclid, who first published it around 300 BC. (Although evidence suggests the algorithm was known and used before Euclid recorded it.)

To find the GCD using Euclid's algorithm, check if one of the numbers is 0. If so, the other number is the GCD. If not, divide the smaller number into the larger number, and replace the larger number with the remainder of the division. Lather, rinse, and repeat, until one of the numbers becomes 0.

For example, with our numbers 28 and 36:

1. Check if one of the numbers is 0.
2. No, so divide 28 into 36, and replace 36 with the remainder, which is 8 (36 = 1×28 + 8). Our two numbers are now 28 and 8.
3. Check if one of the numbers is 0.
4. No, so divide 8 into 28, and replace 28 with the remainder, which is 4 (28 = 3×8 + 4). Our two numbers are now 8 and 4.
5. Check if one of the numbers is 0.
6. No, so divide 4 into 8, and replace 8 with the remainder, which is 0 (8 = 2×4 + 0). Our two numbers are now 4 and 0.
7. Check if one of the numbers is 0.
8. Yes! So the GCD of 28 and 36 is the other number: 4.

As you can see, this process requires a number of divisions. Division is a relatively complex mathematical operation (compared to addition and subtraction, that is), so the number of divisions is an important measure of how complicated this algorithm is and how long it takes to compute it, either by hand or with a computer.

(Aside: This is a simple example, and a human looking at this problem could probably pick 4 as the correct answer merely by looking at the numbers for a few seconds, since we are trained to know our times tables and our brain works in interesting parallel processing ways where it's not obvious what mathematical steps we're actually taking to calculate something. In fact, what we're actually doing is a subconscious form of trial and error: "Maybe it's 6? No, 6 doesn't go into 28. Maybe it's 7? No, 7 doesn't go into 36. Maybe it's 4? Why yes, that works. Is there anything bigger? 8? No... 9? No..." We're actually making a whole bunch of divisions and rejecting the answers, without consciously realising that what we're doing is dividing numbers, so it feels like we can figure it out by making only a couple of explicit divisions. A computer doesn't have this luxury, and actually has to go through the gruntwork of calculating the divisions explicitly. The human brain is an amazing thing.)

If anyone discovered a new algorithm to determine the GCD of two numbers, that used fewer divisions than Euclid's algorithm, this would be a major breakthrough in mathematical theory. Thus Colonel Haken's interest in the answer to the question he asks.

Moving from mathematics to history:

Pierre Laval served as Prime Minister of France on four separate occasions, the last two in the era of the Vichy government during World War II, after the invasion and occupation of France by Nazi Germany. Laval supported a policy of full cooperation with the Nazis, and met with Hitler before adopting a policy of allying France with Nazi Germany. After the Allied victory in the War, Laval was tried as a traitor against France and executed by firing squad.

Prior to the war, Laval had met with Mussolini and Stalin in 1935, to seek alliances against Germany. In one meeting with Stalin, he warned the Soviet leader against his policy of persecuting Catholicism within the USSR. Laval urged Stalin to tolerate the religion, in order to placate Pope Pius XI, who he believed could raise a substantial resistance from the masses of Catholics across Europe and Russia. It was this urging that led Stalin to utter one of his many famous quotations:

How many divisions does the Pope have?

(In fact he said this in Russian, and his words have variously been translated into English as "The Pope! How many divisions has he got?", and "How many divisions has the Pope?", as well as the version above.)

Back to mathematics:

For the really hard core readers, if the explanation above wasn't enough for you, check MathWorld's articles on greatest common divisor and Euclid's algorithm, which provide details and applications using such fun things as Fourier transforms, the golden ratio, the Riemann zeta function*, and, almost inevitably, logarithms and pi.

* Apparently everything you can possibly think of in mathematics is intimately related to the Riemann zeta function. But that's an annotation for another day.

---

2018-06-13 Rerun commentary: Interestingly, this page is (currently as I type) only the third Google search hit for ["greatest common divisor" stalin], the fifth hit for ["greatest common divisor" laval], and doesn't even appear in the top ten for ["greatest common divisor" mussolini].

There must be a lot more people writing crossovers between Euclid's algorithm and pre-World War II politics than I imagined.