4 out of 5 dentists recommend this WordPress.com site

Some solutions

I solved two math problems today. The solutions to both were uniquely disappointing.

The first problem was the first problem from IMO 1986:

Let $d$ be a number that is not $2,5$ or $13$. Prove that out of the set $\{2,5,13,d\}$, we can select two different numbers $a,b$ such that $ab-1$ is not a square.

A quick check would show that $2.5-1, 2.13-2$ and $5.13-1$ are all squares. This shows that of the two numbers that we select from $\{2,5,13,d\}$, one of them has to be $d$. We essentially need to prove that for $d\neq 2,5,13$, $2d-1, 5d-1$ and $13d-1$ are not all squares (a maximum of two of them might be. But all three cannot).

I tried figuring out some of the implications of all of them being squares, but couldn’t come up with anything concrete, as I didn’t write anything at all, and just tried to devise a strategy mentally. Ultimately, I came up with possibly the most mundane proof of all time.

Proof: Consider squares $\mod 16$ (I couldn’t come up with any contradiction up until $\mod 8$). The possible residues for squares $\mod 16$ are $0,1,4,9$. Now my strategy was to plug in all possible residues $\mod 16$ in place of $d$, and checking that in every such instance, at least one of $2d-1, 5d-1$ and $16d-1$ gave a residue that was not $0,1,4,9\mod 16$. This I could successfully verify. Hence proved.

The solution that I could find in the IMO compendium was much smarter, but involved some algebra that would obviously involve putting pen to paper.

The second question that I solved today was proving the Koszul formula, which states that

$2g(\nabla_X Y,Z)=D_Xg(Y,Z)+D_Yg(X,Z)-D_Zg(X,Y)-g([Y,X],Z)-g([X,Z],Y)+g([Z,Y],X)$

I’d seen proofs before in textbooks, that would involve writing down expansions, and then combining all of them in some clever way. The way that I came up with was pretty algorithmic, and perhaps even more elementary. It is simply the following: Take $g(\nabla_X Y,Z)$. Use the torsion free condition to write it as $g(\nabla_Y X,Z)+g([X,Y],Z)$. Now use the formula for connection acting on a tensor to write $g(\nabla_Y X,Z)$ as $D_Y g(X,Z)-g(X,\nabla_Y Z)$. Performing the two operations, we have $D_Yg(X,Z)-g(X,\nabla_Y Z)+g([X,Y],Z)$. Performing this operation of first using the torsion free condition and then the formula for a connection on a tensor three times, we get the Koszul formula.

I’ve been obsessed with Math Olympiads and other kinds of competitive math for a loong time now. Although I should be doing more serious mathematics now that can actually get me a job, I shall ignore good sense and start my series of posts on Math Olympiad problems!

The first problem that I want to write about is a relatively easy one from IMO (International Math Olympiad) 1974. I think it was a long-listed problem, and didn’t actually make it to the test. It asks to prove the fact that

$\displaystyle 343|2^{147}-1$

(that $343$ divides $2^{147}-1$)

The important thing in this problem is to figure out that $343=7^3$ and $147=3.7^2$. Hence, we’re being asked to prove that $7^3|2^{3.7^2}-1$.

We have the following theorem for reference: If $a$ and $b$ are co-prime, then $a^{\phi(b)}\equiv 1\pmod b$, where $\phi(b)$ is the number of natural numbers that are co-prime with $b$. Fermat’s Little Theorem is a special case of this.

Now on to the calculations and number crunching. We have fleshed out the main idea that we’ll use to attack the problem. We can see that $\phi(7^3)=7^3-7^3/7=6.7^2$. Hence, as $2$ is co-prime with $7^3$, $2^{6.7^2}-1\equiv 0\pmod {7^3}$. We can factorize this as $(2^{3.7^2}+1)(2^{3.7^2}-1)\equiv 0\pmod {7^3}$. Now we have to prove that $7^3$ does not have any factors in common with $2^{3.7^2}+1$. As $2^3\equiv 1\pmod 7$, $2^{3.7^2}\equiv 1\pmod 7$ too. Hence, $2^{3.7^2}+1\equiv 2\pmod 7$. This shows that $2^{3.7^2}+1$ does not have any factors in common with $7^3$, and leads us to conclude that $7^3|(2^{3.7^2}-1)$, or $343|2^{147}-1$. Hence proved.

I realize that the formatting is pretty spotty. I shall try and re-edit this in the near future to make it more readable.