»  Solutions to puzzles in my VDARE.com monthly Diary

  April 2024

—————————

In the Math Corner of my April 2024 Diary I posted the following brainteaser from the 2023 International Mathematical Olympiad (IMO).

Think of a fair-sized whole number that is not prime. I shall of course call the number N.  By way of an example, say N = 100.

Write down all the whole-number positive factors of N in ascending order:

        1, 2, 4, 5, 10, 20, 25, 50, 100

Is it the case that each factor in the list exactly divides the sum of the two following factors? (Of course, we'll have to stop looking after 25, the last factor that does have two following it in the list.)

Answer: No, it is not the case. The number 1 does indeed divide 6, 5 divides 30, and 25 divides 150. Unfortunately 2 does not divide 9, 4 does not divide 15, 10 does not divide 45, and 20 does not divide 75.

So no, it is not the case for N = 100 that every factor in the ascending list of N 's factors exactly divides the sum of the two following factors.

All right, so much for for N = 100. Might it be the case for some other value of N, though? Is there perhaps a family of numbers N for which it is the case? If so, what are the distinguishing characteristics of that family?

—————————

•  Solution.

If some number N has the desired property — every factor in the ascending list of N 's factors exactly divides the sum of the two following factors — I shall say that N is factorwise compliant. So what numbers are factorwise compliant? Is there a family of such numbers? What does it look like?

Let's consider the prime factors of N. In the case of N = 100 the prime factors are 2 and 5:  100 = 2²×5².

In the simplest case N may have only one prime factor: 729, for example, is the sixth power of 3. Its factor list therefore looks like this: 1, 3, 9, 27, 81, 243, 729.

Clearly those simplest cases with only one prime factor are factorwise compliant. When N has only one prime factor (and is bigger than that one factor because there need to be at least three members in the factor list), its ascending factor list is the the list of powers of that prime in ascending order, as I just showed for 729.

Obviously any member of the list divides the sum of the next two: 9 divides 27 + 81, and so on.  pk divides exactly into pk+1  + pk+2 with whole-number quotient p + p².

I shall now state the problem as a theorem to be proven.

TheoremN is factorwise compliant iff it has exactly one prime factor p (so that N is just some power of p).
Proof.

That "iff" is mathspeak for "if and only if."

I have already dealt with the "if" by noting in the preamble that pk divides exactly into pk+1  + pk+2 with whole-number quotient p + p².

It remains to prove the "only if": that is, to prove that only if N is some power of a prime p can it be factorwise compliant. Equivalently: if N has more than one prime factor it cannot be factorwise compliant.

On my way to a proof I shall offer as an example the number N = 25947. This number does have more than one prime factor: it is 3³×31². You can easily confirm that 25947's factor list looks like this:

1, 3, 9, 27, 31, 93, 279, 837, 961, 2883, 8649, 25947.

The key to a proof here is a certain symmetry of the factor list. Reading from the left-hand end the list for N = 25947 goes: 1, 3, 9, 27, 31, …  Reading from the right-hand end it goes: N/1, N/3, N/9, N/27, N/31, … 

OK, from the particular to the general. From here on I shall refer to the smallest prime factor of N as p, the second smallest as q. There may of course be lots of other prime factors, but I only need these two smallest ones for my proof.

So the ascending list of factors starts with 1, then p, then either p² or q, whichever is the smaller. There might be more powers of p in the list before q shows up.

In my example of N = 25947 the smallest prime factor p is 3, the next smallest q is 31, and the ascending factor list shows the zeroth, first, second, and third powers of p before q makes an appearance.

Key point.  Sooner or later q, the second smallest prime factor, will show up in the ascending factor list. It might show up as soon as third place:  1, pq, …  or it might be delayed by powers of p:  1, pp², p³, q, …

So what? So this.

Remembering the symmetry I noted, let's "translate" that key point into what we see if we scan the factor list backwards, starting from the right-hand end and heading left.

Translation:  Sooner or later the number N/q will show up. It might "follow" (we're heading leftwards, remember) in third place from the right immediately "after" N and N/p, or it might be delayed, as in my example, "following" NN/pN/p², N/p³, … 

Whatever: That N/q has at least two numbers to its right in the list.

And we know what they are! Immediately to its right is N/pk for some power k (possibly k = 1). To the right of that is N/pk-1 (which, if k = 1, will just be N).

So now let's ask the impertinent question about those three successive members of the ascending factor list: Can the first divide exactly into the sum of the second and third?

In other words: Can N/q divide exactly into  (N/pk + N/pk-1), where k might be 1 or any bigger whole number?

That can be restated as: Can the fraction (N/pk + N/pk-1) / (N/q) be a whole number?

If you multiply top and bottom of the fraction by pkq / N it resolves to q(1 + p) / pk. Since p and q are two different primes, that cannot possibly be a whole number.

Thus any number with more than one prime factor cannot possibly be factorwise compliant. N is factorwise compliant only if it is some power (the second or greater power) of some single prime.  QED