[ Background required: standard modular arithmetic. ]
Consider the following two problems:
Problem 1. Prove that if p > 2 is prime, then when is expressed in lowest terms , m must be a multiple of p.
Problem 2. Prove that if p > 3 is prime, then when is expressed in lowest terms , m must be a multiple of .
Solution to Problem 1. Since there are an even number of terms, we pair up first and last terms, second and second-to-last terms etc, thus obtaining:
, … .
Hence, the overall sum is . The sum in parenthesis simplifies to a fraction in lowest terms, where s is not divisible by p. Hence the sum is in lowest terms, so m = pr is a multiple of p. ♦
Pause for a moment. The natural approach to solve problems regarding divisibility is via modular arithmetic. Of course, for problem 1, we don’t need to go to that extent, but wouldn’t it be useful to have some form of modular arithmetic for rational numbers? Maybe that would help us solve the second problem, which appears far more daunting than the first.
Indeed, there is!
To be specific, we have to fix a prime p ahead and compromise a little by restricting to the following subset of :
= the set of all rational numbers of the form , where b is not divisible by p.
The reader can easily check that this set is closed under addition, subtraction and multiplication (i.e. if x and y are in this set, so are their sum, difference and product). Equally clear is the fact that .
Next we proceed to define divisibility by powers of p :
Definition. An element is said to be divisible by (for positive integer n) if we can find such that .
Examples. Suppose p=5. Then the rational numbers are all elements of . Clearly, the first two numbers are not divisible by p, while the last is divisible by p2.
For the set , divisibility really only makes sense for powers of p. To see why, let’s suppose p=5 and we say that an element is divisible by q=7 if there is a such that x = 7y. What happens? Why, then every element of is a multiple of 7 and the definition is meaningless.
Now we are ready to talk about modular arithmetic for elements of . Given two elements x, y, from this set, we write if the difference is divisible by , as defined earlier.
For example, you can easily check that for p=7, and .
Basic Properties I. Easy exercise: prove that the following are true for any .
- (Reflexive) .
- (Symmetric) If , then .
- (Transitive) If and , then .
Once again, these three properties are the crux of any “equivalence” property. Next, we need to ensure that congruence modulo respects the arithmetic operations.
Basic Properties II. More easy exercises: prove that the following are true for any such that and . [ The proofs for the first 3 properties are identical to the case of integers! ]
- for m = 1, 2, …, we get ;
- if c (and hence d) is not a multiple of p, then .
Important conceptual exercise for last property: if c and d are divisible by p, what goes wrong in the proof? Careful: it’s rather subtle.
Finally, we show that we haven’t really made things more complicated in extending our definition of congruence.
Basic Property III. Any element is congruent to exactly one of modulo .
Proof : It suffices to show x is congruent to some integer modulo . Writing , where b is not divisible by p, it suffices to show is congruent to some integer integer mod . Now Bezout’s identity helps us out: since b and pn are coprime, write for some integers r and s. Now we get and our job is done. ♦
In short, we have extended our definition of modular arithmetic to the larger set instead of the usual . As a tradeoff, however, now we can only talk about congruence modulo powers of p, instead of general n.
Without further delay, let’s dive into the proof of problem 2.
Solution to Problem 2. Pair up the terms as earlier, thus giving:
We need to show that the sum in parenthesis is a multiple of p. But note that each summand is of the form . So we need to show . This is not hard:
- For , the squares are all distinct (if not, then , so is a multiple of p and either or is a multiple of p).
- This also means the reciprocals for are also distinct. (*)
- Since , the squares cover all the possible non-zero squares mod p and they’re all distinct.
- By (*), we see that the same holds for , .
In other words, the reciprocals are congruent to modulo p, after some permutation. Hence, modulo p, our sum is congruent to
which is a multiple of p since the denominator is coprime to p when p>3. ♦
Problem 3. (USAMO 2010 Q5) Let p be an odd prime and . Define the sum:
Prove that if in lowest terms, then .
Hint. [Highlight start] Write the fraction 2/i(i+1)(i+2) = 1/i(i+1) – 1/(i+1)(i+2). Split each 1/j(j+1) = 1/j – 1/(j+1) further, thus giving (1/2 – 2/3 + 1/4) + (1/5 – 2/6 + 1/7) + …. [Highlight end]
Problem 4. (IMO 2005 Q4) Let for positive integer n. Find all positive integers k which are coprime to all in the sequence.
Hint. [Highlight start] Note that 1/2 + 1/3 + 1/6 – 1 = 0. [Highlight end]
We’ve just seen a simple example of theory-building: we find that the existing language is inconvenient / inadequate in solving the problem, so we decide to extend it via new definitions, propositions, theorems etc. Could we have solved the problem without such machinery? Certainly, since we’ve not added any axioms, logically the set of provable theorems must remain identical. But not only is the new language more convenient, it inspires us to think about a problem in an entirely new light.
Finally, we end this post with the following quote by Alexander Grothendieck regarding theory-building, as opposed to problem-solving (the “first approach”).
“I can illustrate the second approach with the same image of a nut to be opened. The first analogy that came to my mind is of immersing the nut in some softening liquid, and why not simply water? From time to time you rub so the liquid penetrates better, and otherwise you let time pass. The shell becomes more flexible through weeks and months—when the time is ripe, hand pressure is enough, the shell opens like a perfectly ripened avocado! A different image came to me a few weeks ago. The unknown thing to be known appeared to me as some stretch of earth or hard marl, resisting penetration… the sea advances insensibly in silence, nothing seems to happen, nothing moves, the water is so far off you hardly hear it… yet it finally surrounds the resistant substance.” – Alexander Grothendieck.