Hardest Question on International Mathematical Olympiad

I actually took this test as an undergraduate.


List of The first International Mathematical Olympiads was held in Romania in 1959. It was initially founded for eastern European member countries of the Warsaw Pact, under the USSR bloc of influence, but later other countries participated as well. Because of this eastern origin, the IMOs were first hosted only in eastern European countries and gradually spread to other nations.

The examination consists of six problems. Each problem is worth seven points, so the maximum total score is 42 points. No calculators are allowed. The examination is held over two consecutive days; each day the contestants have four-and-a-half hours to solve three problems.

This question is considered to be the hardest problem ever asked. It is almost 30 years old.

If a,b are positive integers, and Etop=a^2+b^2 Ebot=ab+1 and E=Etop/Ebot then prove that whenever E is an integer, it is also a perfect square.

The test takers would not have the luxury of using a spreadsheet to look at a few cases, but I am printing one out. I highlighted the cases where E is an integer (which are also perfect squares).

a	b	Etop	Ebot	E	a	b	Etop	Ebot	E	a	b	Etop	Ebot	E	a	b	Etop	Ebot	E
1	1	2	2	1	2	1	5	3	1.67	3	1	10	4	2.50	4	1	17	5	3.40
1	2	5	3	1.67	2	2	8	5	1.60	3	2	13	7	1.86	4	2	20	9	2.22
1	3	10	4	2.50	2	3	13	7	1.86	3	3	18	10	1.80	4	3	25	13	1.92
1	4	17	5	3.40	2	4	20	9	2.22	3	4	25	13	1.92	4	4	32	17	1.88
1	5	26	6	4.33	2	5	29	11	2.64	3	5	34	16	2.13	4	5	41	21	1.95
1	6	37	7	5.29	2	6	40	13	3.08	3	6	45	19	2.37	4	6	52	25	2.08
1	7	50	8	6.25	2	7	53	15	3.53	3	7	58	22	2.64	4	7	65	29	2.24
1	8	65	9	7.22	2	8	68	17	4	3	8	73	25	2.92	4	8	80	33	2.42
1	9	82	10	8.20	2	9	85	19	4.47	3	9	90	28	3.21	4	9	97	37	2.62
1	10	101	11	9.18	2	10	104	21	4.95	3	10	109	31	3.52	4	10	116	41	2.83
1	11	122	12	10.17	2	11	125	23	5.43	3	11	130	34	3.82	4	11	137	45	3.04
1	12	145	13	11.15	2	12	148	25	5.92	3	12	153	37	4.14	4	12	160	49	3.27
1	13	170	14	12.14	2	13	173	27	6.41	3	13	178	40	4.45	4	13	185	53	3.49
1	14	197	15	13.13	2	14	200	29	6.90	3	14	205	43	4.77	4	14	212	57	3.72
1	15	226	16	14.13	2	15	229	31	7.39	3	15	234	46	5.09	4	15	241	61	3.95
1	16	257	17	15.12	2	16	260	33	7.88	3	16	265	49	5.41	4	16	272	65	4.18
1	17	290	18	16.11	2	17	293	35	8.37	3	17	298	52	5.73	4	17	305	69	4.42
1	18	325	19	17.11	2	18	328	37	8.86	3	18	333	55	6.05	4	18	340	73	4.66
1	19	362	20	18.10	2	19	365	39	9.36	3	19	370	58	6.38	4	19	377	77	4.90
1	20	401	21	19.10	2	20	404	41	9.85	3	20	409	61	6.70	4	20	416	81	5.14
1	21	442	22	20.09	2	21	445	43	10.35	3	21	450	64	7.03	4	21	457	85	5.38
1	22	485	23	21.09	2	22	488	45	10.84	3	22	493	67	7.36	4	22	500	89	5.62
1	23	530	24	22.08	2	23	533	47	11.34	3	23	538	70	7.69	4	23	545	93	5.86
1	24	577	25	23.08	2	24	580	49	11.84	3	24	585	73	8.01	4	24	592	97	6.10
1	25	626	26	24.08	2	25	629	51	12.33	3	25	634	76	8.34	4	25	641	101	6.35
1	26	677	27	25.07	2	26	680	53	12.83	3	26	685	79	8.67	4	26	692	105	6.59
1	27	730	28	26.07	2	27	733	55	13.33	3	27	738	82	9	4	27	745	109	6.83
1	28	785	29	27.07	2	28	788	57	13.82	3	28	793	85	9.33	4	28	800	113	7.08
1	29	842	30	28.07	2	29	845	59	14.32	3	29	850	88	9.66	4	29	857	117	7.32
1	30	901	31	29.06	2	30	904	61	14.82	3	30	909	91	9.99	4	30	916	121	7.57
1	31	962	32	30.06	2	31	965	63	15.32	3	31	970	94	10.32	4	31	977	125	7.82
1	32	1,025	33	31.06	2	32	1,028	65	15.82	3	32	1,033	97	10.65	4	32	1,040	129	8.06
1	33	1,090	34	32.06	2	33	1,093	67	16.31	3	33	1,098	100	10.98	4	33	1,105	133	8.31
1	34	1,157	35	33.06	2	34	1,160	69	16.81	3	34	1,165	103	11.31	4	34	1,172	137	8.55
1	35	1,226	36	34.06	2	35	1,229	71	17.31	3	35	1,234	106	11.64	4	35	1,241	141	8.80
1	36	1,297	37	35.05	2	36	1,300	73	17.81	3	36	1,305	109	11.97	4	36	1,312	145	9.05
1	37	1,370	38	36.05	2	37	1,373	75	18.31	3	37	1,378	112	12.30	4	37	1,385	149	9.30
1	38	1,445	39	37.05	2	38	1,448	77	18.81	3	38	1,453	115	12.63	4	38	1,460	153	9.54
1	39	1,522	40	38.05	2	39	1,525	79	19.30	3	39	1,530	118	12.97	4	39	1,537	157	9.79
1	40	1,601	41	39.05	2	40	1,604	81	19.80	3	40	1,609	121	13.30	4	40	1,616	161	10.04
1	41	1,682	42	40.05	2	41	1,685	83	20.30	3	41	1,690	124	13.63	4	41	1,697	165	10.28
1	42	1,765	43	41.05	2	42	1,768	85	20.80	3	42	1,773	127	13.96	4	42	1,780	169	10.53
1	43	1,850	44	42.05	2	43	1,853	87	21.30	3	43	1,858	130	14.29	4	43	1,865	173	10.78
1	44	1,937	45	43.04	2	44	1,940	89	21.80	3	44	1,945	133	14.62	4	44	1,952	177	11.03
1	45	2,026	46	44.04	2	45	2,029	91	22.30	3	45	2,034	136	14.96	4	45	2,041	181	11.28
1	46	2,117	47	45.04	2	46	2,120	93	22.80	3	46	2,125	139	15.29	4	46	2,132	185	11.52
1	47	2,210	48	46.04	2	47	2,213	95	23.29	3	47	2,218	142	15.62	4	47	2,225	189	11.77
1	48	2,305	49	47.04	2	48	2,308	97	23.79	3	48	2,313	145	15.95	4	48	2,320	193	12.02
1	49	2,402	50	48.04	2	49	2,405	99	24.29	3	49	2,410	148	16.28	4	49	2,417	197	12.27
1	50	2,501	51	49.04	2	50	2,504	101	24.79	3	50	2,509	151	16.62	4	50	2,516	201	12.52
1	51	2,602	52	50.04	2	51	2,605	103	25.29	3	51	2,610	154	16.95	4	51	2,617	205	12.77
1	52	2,705	53	51.04	2	52	2,708	105	25.79	3	52	2,713	157	17.28	4	52	2,720	209	13.01
1	53	2,810	54	52.04	2	53	2,813	107	26.29	3	53	2,818	160	17.61	4	53	2,825	213	13.26
1	54	2,917	55	53.04	2	54	2,920	109	26.79	3	54	2,925	163	17.94	4	54	2,932	217	13.51
1	55	3,026	56	54.04	2	55	3,029	111	27.29	3	55	3,034	166	18.28	4	55	3,041	221	13.76
1	56	3,137	57	55.04	2	56	3,140	113	27.79	3	56	3,145	169	18.61	4	56	3,152	225	14.01
1	57	3,250	58	56.03	2	57	3,253	115	28.29	3	57	3,258	172	18.94	4	57	3,265	229	14.26
1	58	3,365	59	57.03	2	58	3,368	117	28.79	3	58	3,373	175	19.27	4	58	3,380	233	14.51
1	59	3,482	60	58.03	2	59	3,485	119	29.29	3	59	3,490	178	19.61	4	59	3,497	237	14.76
1	60	3,601	61	59.03	2	60	3,604	121	29.79	3	60	3,609	181	19.94	4	60	3,616	241	15.00
1	61	3,722	62	60.03	2	61	3,725	123	30.28	3	61	3,730	184	20.27	4	61	3,737	245	15.25
1	62	3,845	63	61.03	2	62	3,848	125	30.78	3	62	3,853	187	20.60	4	62	3,860	249	15.50
1	63	3,970	64	62.03	2	63	3,973	127	31.28	3	63	3,978	190	20.94	4	63	3,985	253	15.75
1	64	4,097	65	63.03	2	64	4,100	129	31.78	3	64	4,105	193	21.27	4	64	4,112	257	16

Quote: Pacomartin

If a,b are positive integers, and Etop=a^2+b^2 Ebot=ab+1 and E=Etop/Ebot then prove that whenever E is an integer, it is also a perfect square.

ABANDON SHIP!

Quote: AZDuffman

ABANDON SHIP!

Number theory questions are often easy to state, but impossible to prove.

Goldbach's conjecture, dating from 1742, is one of the oldest unsolved problems in number theory and in all of mathematics. He said every even integer greater than two is the sum of two prime numbers.
For example,
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
12 = 5 + 7
14 = 3 + 11 = 7 + 7 etc.

It's been tested up to 400 trillion and no exception can be found, but the conjecture has never been proven.

Quote: Pacomartin

Number theory questions are often easy to state, but impossible to prove.

Goldbach's conjecture, dating from 1742, is one of the oldest unsolved problems in number theory and in all of mathematics. He said every even integer greater than two is the sum of two prime numbers.
For example,
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
12 = 5 + 7
14 = 3 + 11 = 7 + 7 etc.

It's been tested up to 400 trillion and no exception can be found, but the conjecture has never been proven.

Has anyone proven that there is an infinite number of prime numbers?

Quote: AZDuffman

Has anyone proven that there is an infinite number of prime numbers?

Yes. Here it goes.

If there were a finite number of primes, numbered p1, p2, p3, etc. Then consider a number q such that

q = p1 * p2 * p3 *... + 1, where q is the product of every prime, plus 1.

q cannot divide any one of the known primes evenly, because there will always be a remainder of 1.

Thus, there must be some other prime not on the list that it divides, if q isn't prime, or it is prime itself.

Usually, this is stated as a proof there is no largest prime, but the same proof shows there must always be more primes out there.

Quote: Pacomartin

Number theory questions are often easy to state, but impossible to prove.

Goldbach's conjecture, dating from 1742, is one of the oldest unsolved problems in number theory and in all of mathematics. He said every even integer greater than two is the sum of two prime numbers.
For example,
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
12 = 5 + 7
14 = 3 + 11 = 7 + 7 etc.

It's been tested up to 400 trillion and no exception can be found, but the conjecture has never been proven.

Thank you. That is a new one to me.

Quote: Wizard

Yes. Here it goes.

If there were a finite number of primes, numbered p1, p2, p3, etc. Then consider a number q such that

q = p1 * p2 * p3 *... + 1, where q is the product of every prime, plus 1.

q cannot divide any one of the known primes evenly, because there will always be a remainder of 1.

Thus, there must be some other prime not on the list that it divides, if q isn't prime, or it is prime itself.

Usually, this is stated as a proof there is no largest prime, but the same proof shows there must always be more primes out there.

This is a ton to take in on Christmas Morning. Theoretical math was never my strong suit, always had to have it practical. I did some other research and saw that any whole number can be factored down to a series of primes multiplied together. I remember doing those factor trees in about third grade, never to be looked at again.

"Thus, there must be some other prime not on the list that it divides, if q isn't prime, or it is prime itself."
I am not getting my arms around that.

q can never be prime here because odd times odd is always odd and adding one always makes it even.

So I can take any prime in the series and divide it into q and I will always have a remainder of 1.

Got those two parts, I assume.

I just feel the rest is saying "there are infinite primes because there are infinite numbers so there have to be infinite primes."

Which is in danger of taking me down a math vs. logic discussion.

Example
Q = p1 * p2 + 1

7 = 2 * 3 + 1

Most prime number stuff has to account for 2

Quote: AZDuffman

"Thus, there must be some other prime not on the list that it divides, if q isn't prime, or it is prime itself."
I am not getting my arms around that.

Let's say the only primes we know about are 2, 3, 5, and 7.

Then let q = 2*3*5*7 + 1 = 211, which turns out to be prime.

Lets consider q=2*3*5*7*11+1 = 2311, which turns out to be prime too.

How about q=2*3*5*7*11*13+1 = 30031, which has prime factorization 59*509 (source).

So in using this method we always find a new prime bigger than the last known largest one. q will never divide a prime on the known primes list, because of that +1, it will cause a remainder of 1 when you divide. Because you can always add more primes to the list, there must be an infinite number of them.

Back to the subject of the thread

Quote: Question #6

If a,b are positive integers, and Etop=a^2+b^2 Ebot=ab+1 and E=Etop/Ebot then prove that whenever E is an integer, it is also a perfect square.

It's fairly easy to see that if one of the two positive integers is the cube of the other, then E is a perfect square.
For instance,
if b=a^3 then Etop=a^2+b^2 = a^2(1+a^4) and Ebot=ab+1= a^4+1 so E=Etop/Ebot = a^2
if a=b^3 then Etop=a^2+b^2 = b^2(1+b^4) and Ebot=ab+1= b^4+1 so E=Etop/Ebot = b^2

Using the GCD (greatest common divisor) function in spread-sheet you can see that the ONLY integer results for E are when b=a^3 or a=b^3. But it would seem to be one of the most difficult problems in the world to prove (in under three hours).

You can google "international mathematical olympiad question 6" to see articles and videos about this problem.