Blog

It is a truth universally acknowledged that mathematicians like to state the obvious. As further confirmation of this well-established fact, it was recently pointed out to me that my 'thinking out loud' posts cannot rival with Marcello's. Now, what is one supposed to do in the face of this self-evident truth? Certainly not get offended – how can you get offended by something you agree with? So, maybe panic? Stop making these posts, to everyone's relief? After some deliberation, I decided that what the comment really meant was that I should strive to be more creative in my writing. I cannot guarentee that I succeeded, but it is a fact that I ended up composing an even longer post than usual. So read ahead at your own peril, you've been warned: long-winded ramblings follow.

EGMO 2014, Problem 3. We denote the number of positive divisors of a positive integer $m$ by $d(m)$ and the number of distinct prime divisors of $m$ by $\omega(m)$. Let $k$ be a positive integer. Prove that there exist infinitely many positive integers $n$ such that $\omega(n) = k$ and $d(n)$ does not divide $d(a^2+b^2)$ for any positive integers $a, b$ satisfying $a + b = n$.

Now that's an ugly statement if I ever saw one! When a problem is this hideous, it often means that it's been built around a solution, instead of the other way around. And this should make it easier: I suspect that the requirement of having precisely $k$ prime factors might be there just to obfuscate what the problem is really about. Can I solve it with just one prime factor, that is, $\omega(n)=1$?

Let's see: I need to take $n=p^r$ for some prime $p$ and a positive integer $r$. Also I want $d(n)=r+1$ not to divide something, so maybe taking $r+1=q$ to be a large prime could be a good idea. Let's do just that. As for $p$, I don't see any good reason why one choice should be better than another, except that 2 (while one might argue that deep down $2$ is not really a prime number – come on, it's even!) tends to have stranger properties than other primes, so let's take $p=2$. If this doesn't work I'll try $p=3$, but I refuse to believe that I need to take $p=32003$.

So suppose $n=2^{q-1}$, $a+b=n=2^{q-1}$, and $d(n)=q$ divides $d(a^2+b^2)$. Now, where does $d(a^2+b^2)$ take its prime factor $q$ from? From some prime power $p^{q-1}$, or rather, $p^{kq-1}$. But this is a huge number: let's find out how big it really is. We have $a^2+b^2 \leq n^2 = 2^{2q-2}$, so $p^{kq-1} \leq 4^{q-1}$. This definitely cannot happen for $p \geq 5$. What happens for $p=2,3$? Assuming that $q$ is not too small (...to be made precise later), $p^{kq-1} \leq 4^{q-1}$ implies $k=1$. But is it possible that $3^{q-1} \mid a^2+b^2$? A well-known lemma (ok, I must confess – I'm a number theorist by trade. All the same, this problem is still not the most appealing one I've come across in my life) says that in this case $3^{(q-1)/2}$ divides both $a$ and $b$ – and if $(q-1)/2$ is not an integer, then probably I need to round it up. (Do I? Let's see: the basic lemma is that if $3 \mid a^2+b^2$, then $3 \mid a$ – because $3$ is $3 \bmod 4$. So for $q=1$... ehr, ok, I was mistaken: $a,b$ are divisible by $3^{\lceil q/2 \rceil}$. Well whatever, they are divisible by some large power of $3$). So anyway, if $3^{q-1}$ divides $a^2+b^2$, then $a,b$ are divisible by something like $3^{q/2}$. In this case $a+b \geq 2 \cdot 3^{q/2}$, which I was hoping to be larger than $2^{q-1}$, but that doesn't seem to be the case. Oh but wait, I'm being really obtuse: if $3^{\text{something}}$ divides both $a$ and $b$, then $3$ divides $a+b=n=2^{q-1}$, which is more than a little absurd. Ok, so the only possibility is $a^2+b^2 = 2^{kq-1} \times \text{something}$ with $k=1$ or maybe $2$. Can $k=2$ really happen? If I write down the obvious inequalities I find\[2^{2q-2} = n^2 \geq a^2+b^2 \geq 2^{2q-1}\]so no, that does not happen. Fine. Suppose $a^2+b^2=2^{q-1} \times \text{something}$: this would be a little surprising, because the powers of 2 need to recombine in very interesting ways to ensure that the same power of 2 divides both $n$ and $a^2+b^2$ with $a+b=n$. Can I turn this philosophy into an actual statement? Write $a=2^{m} x, b=2^{n} y$ and\[a^2+b^2 = 2^{2m} x^2 + 2^{2n} y^2.\]If (say) $x < y$ then I can collect a term $2^{2m}$ and find that $a^2+b^2 = 2^{2m}(x^2+2^{2n-2m}y^2)$, so the largest power of $2$ that divides $a^2+b^2$ is $2^{2m}$. It should also be $2^{q-1}$, however, so $2m=q-1$ and $n$ is larger. What's the other condition? $a+b=n$. But then no, the largest power of $2$ in $a+b$ is going to be $2^m$ (same argument), and $2^m = 2^{(q-1)/2} < 2^{q-1}$. Ok, this seems to do it, right? Ah no, I'm forgetting one case: what happens if $m=n$? Let me see again,\[a^2+b^2 = 2^{2m} x^2 + 2^{2n} y^2 = 2^{2m} (x^2 + y^2)\]with $x$ and $y$ odd. So $x^2+y^2 \equiv 2 \pmod 4$, and $a^2+b^2$ is divisible exactly by $2^{2m+1}$. So this time $2m+1=q-1$, which however cannot happen because $q$ is odd. Ok, that was not so hard... but boy am I glad that I'm writing this down! I think I've already forgotten 80% of what I've done. I'm also slightly worried at having used this lemma $3 \mid a^2+b^2 \Rightarrow 3 \mid a, b$. Is this going to generalize nicely when I take $n$ with $k$ prime factors?

Ok, let's stop for a sec and think before trying the general case – what have I used so far?

• That $n$ is small: this seems to be crucial, so I want to make $n$ very small.
• On the other hand, I need (maybe? Or maybe I'm just on the wrong track altogether?) a prime with a largish exponent, in order to fabricate a largish prime in $d(n)$.
• I've also used that $n$ is not divisible by $3$. I have no clue if this is going to be necessary in general, but it might be.
• Putting everything together, I think that I should try to take $n = 2^{q-1} p_2 p_3 \cdots p_k$ where the $p_i$'s are distinct primes that as small as possible (which might mean either $p_2=3, p_3=5, p_4=7, ...$ or $p_2=5, p_3=7, p_4=11, ...$, depending on whether I want to enforce the condition $3 \nmid n$ or not).

Ok, let's get started. Have I already mentioned that I don't like this problem? I don't like this problem. So, $n=2^{q-1} p_2 p_3 \cdots p_k$, $a+b=n$, and $d(a^2+b^2)$ is a multiple of $q$. Can this really happen? It means that $a^2+b^2$ (of order roughly $n^2$...) has a prime power factor of the form $r^{kq-1}$ with $r$ prime. Now, let's say something which is a bit false but philosophically very true: if $q$ is ginormous, then $n^2$ looks very much like $2^{2q-2}$. Ok, not really, but let's say that it's sort of true on a logarithmic scale, which is what I care about at the moment (because I'm looking at exponents). So anyway, mathematics, not philosophy:\[a^2+b^2 \leq n^2 \leq 2^{2q-2} (p_2\cdots p_k)^2,\]and on the other hand $r^{kq-1}$ divides $a^2+b^2$, so\begin{equation}\tag{1}\label{eq:ineq}r^{kq-1} \leq 2^{2q-2} (p_2\cdots p_k)^2\end{equation}If $r$ is at least 5, well, then we obtain an inequality of the form\[5^{q-1} \leq 4^{q-1} (p_2\cdots p_k)^2\]which (since the product $p_2 \cdots p_k$ is fixed... ok, not yet, but it will be fixed eventually) is impossible when $q$ is large. So $r$ is either 2 or 3. This is good, because it's the same conclusion we had in the $\omega(n)=1$ case. I know how to rule out 3: it suffices to take $(n,3)=1$. So we're saying $a^2+b^2=2^{kq-1} (\text{something})$, and \eqref{eq:ineq} gives $k \leq 2$. That IS unfortunate: before we had $k=1$ automatically. Ugh, this means one extra case. Fine, let's do it. Actually no, first let's check that the case $k=1$ generalizes. And by the way I've just realized that I'm such an idiot, I'm using $k$ both for $\omega(n)$ and for the exponent of $r$ in $a^2+b^2$. I'll need to fix this when I write an actual solution. Anyway: suppose $a+b=n=2^{q-1}(p_2\ldots p_k)$ and $a^2+b^2=2^{q-1}(\text{something})$. If $v_2(a) \neq v_2(b)$* we have $q-1=v_2(a^2+b^2)=2 \min\{v_2(a),v_2(b)\}$ and $v_2(a+b)=\min\{v_2(a),v_2(b)\}$, which leads to a contradiction, just like before. What if $v_2(a)=v_2(b)$? Then $q-1=v_2(a^2+b^2)=2v_2(a)+1$, which is impossible because $q$ is odd. Good, this also works just as before, and leaves me with the case $a+b=n=2^{q-1}(p_2\ldots p_k)$ and $a^2+b^2=2^{2q-1}(\text{something})$. This $2$-adic valuation business is working so well that I think I should probably try using it on the missing case as well. I'll need to deal with the same two cases as above:

• $v_2(a) \neq v_2(b)$: then $2q-1=v_2(a^2+b^2)=2\min\{v_2(a),v_2(b)\}$. This is odd = even, so nope!
• $v_2(a)=v_2(b)$: then $2q-1 = v_2(a^2+b^2) = 2v_2(a)+1$. This is not a contradiction per se, it just gives $v_2(a)=v_2(b)=q-1$. Hopefully this will contradict $a+b=n$, otherwise I'll throw the laptop out of the window in a fit of frustration... So: is it possible that $a+b=n$ with $v_2(a)=v_2(b)=v_2(n)=q-1$? If I write\[a+b = 2^{q-1}x + 2^{q-1} y = 2^{q-1}(x+y) = n...\](at this point I've stared at this equation for more than I care to admit, until...) I AM A TOTAL MORON. $x$ and $y$ are odd, so $x+y$ is even, and $v_2(a+b)=v_2(2^{q-1}(x+y))$ is at least $q$, contradiction.

And with this we're finally done. So, to summarise (and write a decent proof in which we try to hide all the ugliness above)

• We want to construct such an $n$ with $\omega(n)=k$. Take $n=2^{q-1} (p_2 \cdots p_k)$, where $p_2,\ldots,p_k$ are the smallest $k-1$ primes larger than $3$, and $q$ is a prime so large that $5^{q-1} > 4^{q-1} (p_2\ldots p_k)^2$.
• In this situation, $d(n)$ is divisible by $q$. We want to show that $a+b=n$ implies $d(n) \nmid d(a^2+b^2)$, so it suffices to show that $q \nmid d(a^2+b^2)$.
• Suppose $a+b=n$ are such that $q \mid d(a^2+b^2)$. Then there exist a prime $r$ and an integer (which is most definitely not called $k$, but say $e$) such that $r^{eq-1} \mid a^2+b^2$. Since $a^2+b^2 \leq n^2 = 4^{q-1} (p_2 \ldots p_k)^2 < 5^{q-1}$, this implies that we are in one of the following three situations: $r=2, e=1$; $r=2, e=2$; $r=3, e=1$.
• if $r=3$, then $3 \mid a^2+b^2$, which implies $3 \mid a, b$ (in a competition I would write down a proof for this lemma), which in turn implies $3 \mid a+b = n$, contradiction.
• if $r=2$, let $A=v_2(a), B=v_2(b)$ [notice that these were called respectively $m$ and $n$ above. Using $n$ here is maybe not such a great idea...]. Then $v_2(a^2+b^2)=eq-1$, and there are two cases:
  • $A \neq B$: then $v_2(a^2+b^2)=2 \min\{A,B\}$, which is even, so $e=1$. But then $q-1=v_2(n)=v_2(a+b) = \min\{A,B\} = \frac{1}{2} v_2(a^2+b^2)=\frac{q-1}{2}$, contradiction.
  • $A=B$: then $eq-1=v_2(a^2+b^2)=2A+1$, so $e=2$ for parity reasons. But then $q-1=v_2(n) = v_2(a+b) \geq A+1=q$, contradiction.
• Since we reach a contradiction in every case, this shows that there are no pairs of positive integers $(a,b)$ such that $a+b=n$ and $d(n) \mid (a^2+b^2)$, as required.

Closing remarks

$p$-adic valuations are your friends! Especially in a problem like this, where (almost) the only relevant property of $n$ and $a^2+b^2$ is their prime factorisation, you should definitely think in terms of valuations. And if you are not familiar with the notation $v_p(\cdot)$ and its basic properties (one above all: $v_p(x+y) \geq \min\{v_p(x), v_p(y)\}$, with equality whenever $v_p(x) \neq v_p(y)$), you may want to read up on it (one of many possible starting points: http://s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/articles/olympiad-number-theory.pdf).

A final word of wisdom: powerful as they are, congruences (or $p$-adic valuations, in this case) can't do everything! As one of the organisers of our national Mathematical Olympiad likes to say, any good number theory problem involves both congruences and inequalities. This should be apparent in the problem we just solved!

*here $v_2(x)$ is the exponent of $2$ in the factorisation of $x$: it's called the $2$-adic valuation of $x$.