Brocard's Problem

Yev Barkalov

November 30, 2024

When you’re in school you get acquainted with math problems - equations or variables you’re supposed to solve using the formulas you were just taught about. Unless it’s an intentional curveball or accidental homework, the problems you’re provided are ones the teachers know the solutions to. However, there’s a whole laundry list of math problems that have not yet been solved!

Some of these problems get more publicity than others due to monetary reward or notoriety. Of course, there’s an inherent risk to poking at certain ones but here’s what we believe to be a solution to Brocard’s Problem.

Helpful context
Problem
Solution

Helpful context

Integer solutions

Before getting into the weeds of the specific problem of interest there are a few concepts that’d be good to warm up familiarity to before diving into our solution. First, what do we mean by “integer solutions”?

When an equation involves variables there may or may not be some number of values you can put in place of those variables such that the overall equation holds true. Take for example the following:

\[ 2x + 1 = 27 \]

There’s only one solution that works for \(x\) which, in the equation above, is 13.

\[ 2x + 1 = 27 \]

\[ (2x + 1) - 1 = (27) - 1 \]

\[ 2x = 26 \]

\[ x = 13 \]

However there could be more than one valid solution for an equation with variables such as the following:

\[ 2x^2 = 40 \]

\[ (2x^2) \div 2 = (40) \div 2 \]

\[ x^2 = 20 \]

\[ x = (2 * \sqrt{5}) \text{ or } (-2 * \sqrt{5}) \]

The first equation had 13, an integer, as a solution whereas the second equation has two irrational numbers as solutions. There could even be equations that, under certain constraints, have no solutions at all.

If we were to work with the constraint where we’re only interested in solutions which happen to be integers then it wouldn’t be unfair to say the second equation actually has no solutions. An example where you may be familiar with this idea would be in geometry with the equation for describing the relationship between side lengths of a right triangle.

\[ a^2 + b^2 = c^2 \]

Integer solutions to the above equation are known as Pythagorean triples and include tuples like the following:

\[ (3)^2 + (4)^2 = (5)^2 \]

\[ (5)^2 + (12)^2 = (13)^2 \]

There’s infinite number of possible Pythagorean triples which can be seen if you were to imagine generating an arbitrarily large number of solutions. The way this idea ties into the problem we’re tackling is because the underlying question has to do with whether or not infinite number of integer solutions exists for a specific equation.

Factorials

How many different ways can you sort a standard deck of 52 playing cards? If you don’t already know about the factorial function, here’s how you might go about finding the number by hand:

How many possibilities are there for the card on the top of the deck? 52
After the card on the top of the deck, how many possibilities are there for the second card in the deck? 51
After the first and second cards from the top of the deck, how many possibilities are there for the third card in the deck? 50
…

Then multiplying these together for your final calculation:

\[ 52 * 51 * 50 ... * 3 * 2 * 1 = \text{a big number} \]

The left-hand side of the equation where we’re multiplying all the numbers from 1 to 52 could be generalized for any positive integer \(n\) which gives us the definition of a factorial.

\[ n! = 1 * 2 * 3 * \text{...} * (n-2) * (n-1) * n \]

Here’s how that looks for a few numbers:

\[ 3! = 1 * 2 * 3 = 6 \]

\[ 5! = 1 * 2 * 3 * 4 * 5 = 120 \]

\[ 8! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 40320 \]

If you’re curious what happens when you work with non-integer or negative values, check out the gamma function.

Parity

Parity is just a formal way of saying a number is even or odd but an intentional rigor does provide us with tools that can help answer questions about properties of certain numbers. For example, consider the following proof that the square of an even number must be even and that the square of an odd number must be odd:

The square of an even number is even

An even number can be expressed as the product of 2 and some integer, let’s use \(k\) to refer to the integer.

\[ x = \text{some even number} \]

\[ x = 2k \]

Squaring that number then looks like

\[ x^2 = (2k)^2 \]

\[ (2k)^2 = 4k^2 \]

Given \(k\) is an integer, it follows that its square is also an integer (since multiplying integers yields an integer), as is that product multiplied by 2. Let’s define a \(l\) to wrap that value in order to simplify the expression we have above.

\[ j = 2k^2 \]

\[ 4k^2 = 2j \]

The final righthand side matches the format we used to describe an even number and, so, we have ended up with an even number after squaring an even number.

The square of an odd number is odd

An odd number can be expressed as an even number plus one so, working off the definition for an even number we used before:

\[ x = \text{some odd number} \]

\[ x = 2k + 1 \]

Next we square the odd number.

\[ x^2=(2k + 1)^2 \]

\[ (2k + 1)^2=4k^2+4k+1 \]

Again, we can define an integer to wrap a value in the expression which we’ll do with \(2k^2+2k\).

\[ j = 2k^2+2k \]

\[ 4k^2+4k+1=2j+1 \]

Finally, the righthand side expression matches with our definition for an odd number and, so, we have ended up with an odd number after squaring an odd number.

Problem

With \(m!\) being the factorial function and \(n^2\) being n squared, the equation we’re interested in integer solutions for is the following:

\[ m! + 1 = n^2 \]

The known solutions to this equation are as follows:

\[ (4)! + 1 = (5)^2 \]

\[ (5)! + 1 = (11)^2 \]

\[ (7)! + 1 = (71)^2 \]

The question is do any more integer solutions exist and, if so, is there a finite or infinite number of those further solutions?

\[ m! + 1 = n^2 \text{ where } (m,n) \notin \{(4, 5), (5, 11), (7, 71)\} \]

Solution

Modifying the equation

While it can be alluring to target the “near miss” of the expression \(m! + 1\), the way we’re going to approach this problem is by first restructuring the equation of interest so we eventually get to a different but equivalent problem.

\[ m! + 1 = n^2 \]

\[ (m! + 1) - 1 = (n^2) - 1 \]

\[ m! = n^2 - 1 \]

Then, we can factor the righthand side thanks to an identity from algebra.

\[ a^2-b^2 = (a-b)(a+b) \]

Where we’ll have \(a=n\) and \(b=1\).

\[ m! = n^2 - 1 \]

\[ m! = (n-1)(n+1) \]

Now we have the different but equivalent problem to Brocard’s problem in which we are seeking integer solutions to the above equation.

Observations about the new equation

Parity of the factorial

Being interested in values where \(m>1\), it then follows that \(m!\) will always contain 2 as a factor which means the lefthand and righthand sides of the equation represent even numbers.

\[ m! = m * (m-1) * \text{...} * 2 * 1 \]

\[ \text{let } j = m * (m-1) * (m-2) * \text{...} * 4 * 3 \]

\[ m * (m-1) * \text{...} * 2 * 1 \Rightarrow j * 2 * 1 = 2j \]

Parity of the values being multiplied

Whether as a consequence of the above or by starting with the parity of \(m!+1\), it can be seen that \(n\) must be an odd number.

\[ n = 2k + 1 \]

The two values being multiplied, since they are both just one off from an odd number, must then be even.

\[ n-1=(2k+1)-1=2k \]

\[ n+1=(2k+1)+1=2k+2=2*(k+1) \]

Due to it being a product of two even numbers, it then follows the lefthand side of the equation \(m!\) must be divisible by four which would explain why 4 is the smallest integer solution for \(m\).

Divisor connection between values being multiplied

The difference between the two numbers being multiplied is 2 and we know they’re both divisible by 2 so we can do the following.

\[ \text{let } n = 2k + 1 \]

\[ n-1=(2k+1) -1=2k \rightarrow 2k \div 2 = k \]

\[ n+1=(2k+1)+1=2k+2 \rightarrow (2k+2) \div 2 = k+1 \]

The two numbers when divided by two have a difference of 1 and must be coprime as a result. This can be seen with remainders because every factor that divides \(k\) must have a remainder of 1 when dividing \(k+1\) by the same number. For an example of this, consider 3, 6, and 7:

\[ 6 \div 3 \Rightarrow \text{remainder of 0} \]

\[ 6 + 1 = 7 \rightarrow 7 \div 3 \Rightarrow \text{remainder of 1} \]

Therefore, the only factor the values \(n-1\) and \(n+1\) share in common is 2. A way to state this more formally would be to say their greatest common divisor is 2.

\[ \gcd(n-1, n+1) = 2 \]

A number packing problem

In reference to sphere packing, let’s consider the parititioning of factors of the factorial into two products as being like a “packing” problem since there’s (albeit not physical) constraints.

\[ m!=(n-1)*(n+1) \]

\[ m * (m-1) * (m-2) * \text{...} * 3 * 2 * 1 = (n-1)*(n+1) \]

Let’s imagine we divvy up the factors of the lefthand side into products \(a\) and \(b\) like so:

\[ m * (m-1) * (m-2) * \text{...} * 3 * 2 * 1 = a * b \]

\[ m * (m-2) * \text{...} * 3 = a \]

\[ (m-1) * \text{...} * 2 * 1 = b \]

Our “packing problem” is in \(a\) and \(b\) being able to match \(n-1\) and \(n+1\) where the values have a difference as well as greatest common divisor of 2.

\[ a = b + 2 \]

\[ \gcd(a, b) = 2 \]

The number packing problem for known solutions

Let’s take the known solutions and work our way towards the “number packing” done under the hood.

\[ 4! + 1 = 5^2 \rightarrow 4! = (5-1) * (5+1) \]

\[ 4! = 4 * 6 \]

\[ 5! + 1 = 11^2 \rightarrow 5! = (11-1) * (11+1) \]

\[ 5! = 10 * 12 \]

\[ 7! + 1 = 71^2 \rightarrow 7! = (71-1) * (71+1) \]

\[ 7! = 70 * 72 \]

Expanding the factorials then gives us the following:

\[ 4! = 4 * 6 \Rightarrow 1 * 2 * 3 * 4 = 4 * 6 \]

\[ 5! = 10 * 12 \Rightarrow 1 * 2 * 3 * 4 * 5 = 10 * 12 \]

\[ 7! = 70 * 72 \Rightarrow 1 * 2 * 3 * 4 * 5 * 6 * 7 = 70 * 72 \]

If you remember how dividing the products by 2 results in two coprime numbers, it then also follows one of the products is divisible by 2 only once. Below shows the expanded factorials with the factors of the product which is divisible by 2 once being highlighted.

\[ 4! = 4 * 6 \Rightarrow 1 * \fbox{2} * \fbox{3} * 4 = 4 * \fbox{6} \]

\[ 5! = 10 * 12 \Rightarrow 1 * \fbox{2} * 3 * 4 * \fbox{5} = \fbox{10} * 12 \]

\[ 7! = 70 * 72 \Rightarrow 1 * \fbox{2} * 3 * 4 * \fbox{5} * 6 * \fbox{7} = \fbox{70} * 72 \]

The number packing problem limiting further solutions

It can be checked by hand that integer solutions for \(n\) do not exist values of \(m\) in \((8, 9, 10, 11, 12, 13, 14)\).

\[ 8! = 40320 \rightarrow \text{Not a square} \]

\[ 9! = 362880 \rightarrow \text{Not a square} \]

\[ 10! = 3628800 \rightarrow \text{Not a square} \]

\[ 11! = 39916800 \rightarrow \text{Not a square} \]

\[ 12! = 479001600 \rightarrow \text{Not a square} \]

\[ 13! = 6227020800 \rightarrow \text{Not a square} \]

\[ 14! = 87178291200 \rightarrow \text{Not a square} \]

So let’s instead skip forward to something interesting for our “number packing problem” that becomes clearer at \(m\) gets to 15.

\[ m! = (n-1)(n+1) \text{ where } m \geq 15 \]

Expanding the factorial expression for \(m=15\).

\[ 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 = (n-1) * (n+1) \]

Taking from what we know already, the two products on the righthand side must be even and possess a greatest common divisor of 2. It then follows the value that’s only divisible by 2 once would contain one even factor. Before we start plucking out values that could possibly be factors for this number, let’s highlight the numbers we know cannot be factors.

\[ 1 * 2 * \fbox{3} * \fbox{4} * \fbox{5} * \fbox{6} * 7 * \fbox{8} * \fbox{9} * \fbox{10} * 11 * \fbox{12} * 13 * 14 * \fbox{15} = (n-1) * (n+1) \]

In particular, the sets that cannot be included as factors are \(\{4, 8\}\), \(\{3, 6, 9, 12\}\), and \(\{5, 10, 15\}\).

Given we are cultivating the factors of the product that’s only divisible by 2 once, it cannot be divisible by four hence excluding \(\{4, 8\}\)
For the products to share no common factors besides 2, all multiples of a prime greater than 2 must correspond to one of the products. If we use 3 as a factor for one of the products then 6 for the other, they will share 3 as a common factor which cannot be the case. The reason all multiples of 3 here cannot be incorporated into the product that’s only divisble by 2 once is that it’d mean including 12 as a factor which’d mean the product’s divisble by four which we cannot do.
Similar to how we cannot include any multiples of 3, including any multiple of 5 would mean including 15 as a factor which’d mean eventually picking up multiples of 3 which includes 12 and cannot be the case.

Multiplying the numbers unavailable gives us 46,656,000 and only a product of 28,028 with the leftover numbers at the moment. What we can see, as general rules:

Multiples of 3 and 4 cannot be included therefore eliminating 50% of numbers as possibilities (a third plus a fourth minus a twelfth to account for redundancy)
Multiples of 5 cannot be included eliminating more numbers

Additionally, not all of the leftover numbers can be used in the resulting product. If we include 14 we then cannot include the value 2 since it’d redundantly include 2 leaving us with the following options for the product that gives a number only divisible by two once.

2 multiplied by every odd prime \(p\) such that \(2p>m\)
A prime \(q\) mutiplied by \(2q\) as well as every odd prime \(p\) such that \(3q>m\) and \(2p>m\)

Thereby eliminating either 2 or the factors \(\{7, 14\}\) from the product of interest which reduces available factors to the number of odd primes less than \(m\) with multiples greater than \(m\) plus one or two (for either 2 or \(\{p, 2p\}\)). Since this number of certain primes must be less than the overall number of primes less than \(m\), we can restate this as the following inequality:

\[ F_{m}= \text{# of numbers less than } m \text{ that can be used for product of interest} \]

\[ P_{m} = \text{# of primes less than } m \]

\[ F_{m} < P_{m} \]

Conveniently, \(P_{m}\) here has a decent understanding as being the prime counting function

\[ P_{m} \approx \frac{m}{\ln(m)} \]

Let’s assume the best case scenario in terms of maximizing available factors where we include \(\{p, 2p\}\), this would give us a definite upper bound as being the prime counting function plus 2

\[ F_{m} < \frac{m}{\ln(m)} + 2 \]

For values of \(m\) greater than 15, we can include another expression in this inequality:

\[ F_{m} < \frac{m}{\ln(m)} + 2 < \frac{m}{2} \]

The inequality above dictates that there will reliably being significantly less than half the available numbers to multiply for the product that’s only divisble by two once. Finally, remember how the two products we implicitly end up with after modifying the original equation need to only have a difference of 2?

Once the gap between available and unavailable factors is sufficiently large, since a significant number of possible factors cannot “become available” upon introduction of new consecutive integers, we find ourselves faced with it being impossible to partition two products that meet the required conditions. Presenting how this plays out for 16:

\[ 16! = (n-1)(n+1) \]

\[ 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 *16 = (n-1) * (n+1) \]

Highlighting the values that cannot be factors of the product that’s only divisible by two once.

\[ 1 * 2 * \fbox{3} * \fbox{4} * \fbox{5} * \fbox{6} * 7 * \fbox{8} * \fbox{9} * \fbox{10} * 11 * \fbox{12} * 13 * 14 * \fbox{15} * \fbox{16} = (n-1) * (n+1) \]

Multiplying these values gives us 746,496,000 already “unavailable” and 28,028 leftover before any further filtering. 17 certainly can be added to multiply the smaller product but incrementing further in values only grossly emphasizes the gap between products.

To more strongly show this gap does pose an impossibility to the constraints of the products, let’s lastly show the ratio of available factors to \(m\) tends towards zero as \(m\) tends towards infinity.

\[ \lim_{m \to \infty} \frac{F_{m}}{m} = 0 \]

To accomplish this let’s make a closed form definition for \(F_{m}\) that makes note of the definition for our product that’s only divisible by two once (a prime \(q\) mutiplied by \(2q\) as well as every odd prime \(p\) such that \(3q>m\) and \(2p>m\)). This effectively gives us the following with \(\pi\) being the prime counting function:

\[ F_{m} = 2 + \pi(m) - \pi(\frac{m}{2}) \]

The reason for this is because the \(p\) values we’re considering in this product are those greater than \(m/2\). If we leverage the definition of the prime counting function we get the following closed form for \(F_{m}\):

\[ \pi(n)=\frac{n}{\ln(n)} \]

\[ F_{m} = 2 + \frac{m}{\ln(m)} - \frac{\frac{m}{2}}{\ln(\frac{m}{2})} \]

\[ F_{m} = 2 + \frac{m}{\ln(m)} - \frac{m}{2 * (\ln(m/2))} \]

While we could reduce the expression further, the way we’ve defined \(F_{m}\) suffices for the limit expression we’re interested in: