Why Modulo 11?
The book An Introduction to Diophantine Equations by Titu Andreescu and Dorin Andrica is targeted at people preparing for USAMO and IMO. It contains a lot of problems on Diophantine equations from math Olympiads used in various math Olympiads all over the world.
The first chapter discusses several methods for solving Diophantine equations: decomposition, using inequalities, using parameters, modular arithmetic, induction, infinite descent, and other miscellaneous ideas. Each sub-chapter starts with a short description of the method, accompanied by several solutions to sample problems. At the end of each sub-chapter there are a plethora of exercise problems.
The second and the third chapters are more theoretical. The former discusses some classical equations and the latter looks at Pell’s equation. These two chapters also contain problems, but the bulk of the chapters is devoted to basic theory that is essential to an understanding of Diophantine equations.
For those who are training for the Olympiads, this is an important book to own, not only because there are few other books on the subject, but because it provides so many useful problems.
I’ve long complained that most training books for math competitions leave out any discussion of how we choose a method by just looking at a problem. Andreescu and Andrica didn’t fill that gap with this book.
Perhaps in their next book they will point out clues that indicate that a particular problem might be solved by the parametric method. And explain which types of problems are best solved with induction. Let them challenge students to find those clues in a problem that help us to judge which method might be most promising, instead of randomly trying one method after another. Let me give you a sample problem from the book, which originated at the Balkan Mathematical Olympiad:
Prove that the equation x5 – y2 = 4 has no solutions in integers.
The solution is to take the equation modulo 11, and see that it is impossible.
Is there a reason to start with the modular arithmetic method and not with other methods? If we use modular arithmetic, do we recognize why it’s best to start with 11? I’m convinced that this problem has sufficient clues to suggest starting with checking this equation modulo 11.
I wonder if you, my readers, agree with me. If so, can you explain which hints in the problem lead to taking the equation modulo 11? I believe it should be a part of competition training to learn to identify clues that suggest that one direction might be preferable to the others.
Share:
Michael Lugo:
I don’t know what hints there are. But it’s not hard to write a program checking the possible residue classes of x^5 – y^2 mod n for each n up to 300; the only residue classes which don’t occur are 4 mod 11. (Nothing is special about the cutoff of 300 here; I just got tired of waiting.) That is, it appears that 11 is the only modulus for which the method works.
19 November 2009, 6:15 pmQiaochu Yuan:
11 = 2*5 + 1. That means there are only five nonzero squares and two nonzero fifth powers mod 11.
19 November 2009, 7:18 pmBoris:
@Michael: You want n so that x^5 and/or y^2 take few values modulo n. Euler’s theorem says that we should look at n so that 5 divides φ(n). The first such n is 11. (In general, one should look at primes that are 1 mod 5 and powers of 5 greater than 5, e.g. 25 or 31.)
19 November 2009, 7:37 pmGerhard:
Yes, 11 (and of course all its multiples) is the only modulus that works in this case.
This has been discussed for instance in
T. Mautsch, G.J. Woeginger
The sum of a cube and a fourth power
Crux Mathematicorum 34 (2008), pp 358-361
Here is a related problem, for which only modulus 13 (and its multiples) works:
20 November 2009, 4:57 amDo there exist 20 consecutive integers, that can all be written as the
sum of a cube and a fourth power?
I. J. Kennedy:
The fifth powers, mod 7, are 0,1,4,5,2,3,6, …
The squares mod 7 are 0,1,4,2,2,4,1, …
The differences mod 7 are 0,0,0,3,0,6,5, …
Since 4 doesn’t appear in the list of differences,
30 November 2009, 12:59 pmdoesn’t that mean considering modulo 7 works just as well as 11?
Tanya Khovanova:
I.J.
You need to take all possible combinations of the remainders. For example, x = 2, and y = 0, provide a solution mod 7.
30 November 2009, 7:01 pmmath games for the classroom:
why does x = 2, and y = 0, provide a solution mod 7?
15 July 2010, 10:28 am