## 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 numberN. By way of an example, sayN= 100.

Write down all the whole-number positive factors ofNin 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 thatdoeshave 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 doesnotdivide 9, 4 doesnotdivide 15, 10 doesnotdivide 45, and 20 doesnotdivide 75.

So no, it isnotthe case forN= 100 that every factor in the ascending list ofN's factors exactly divides the sum of the two following factors.

All right, so much for forN= 100. Might it be the case for someothervalue ofN, though? Is there perhaps a family of numbersNfor 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.
*p*^{k} divides exactly into *p*^{k+1} + *p*^{k+2} with
whole-number quotient *p* + *p*².

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

Theorem.Nis factorwise compliant iff it has exactly one prime factorp(so thatNis just some power ofp).

Proof.

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

I have already dealt with the "if" by noting in the preamble that *p*^{k} divides exactly into
*p*^{k+1} + *p*^{k+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, *p*, *q*, … or it might be delayed by powers of *p*:
1, *p*, *p*², *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"
*N*, *N*/*p*, *N*/*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*/*p*^{k} for some power *k* (possibly
*k* = 1). To the right of *that* is *N*/*p*^{k-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*/*p*^{k} + *N*/*p*^{k-1}), where *k* might be 1 or any bigger whole
number?

That can be restated as: Can the fraction
(*N*/*p*^{k} + *N*/*p*^{k-1}) / (*N*/*q*) be a whole
number?

If you multiply top and bottom of the fraction by *p*^{k}*q* / *N* it resolves to
*q*(1 + *p*) / *p*^{k}. 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