Modular Arithmetic Deluxe Edition

[ Background required: standard modular arithmetic. ]

Consider the following two problems:

Problem 1. Prove that if p > 2 is prime, then when $1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 {p-1}$ is expressed in lowest terms $\frac m n$ , m must be a multiple of p.

Problem 2. Prove that if p > 3 is prime, then when $1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 {p-1}$ is expressed in lowest terms $\frac m n$ , m must be a multiple of $p^2$ .

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:

$\frac 1 1 + \frac 1 {p-1} = \frac p {p-1}, \quad \frac 1 2 + \frac 1 {p-2} = \frac p {2(p-2)}$ , … .

Hence, the overall sum is $p(\frac 1 {1\times {p-1}} + \frac 1 {2\times {p-2}} + \dots + \frac 1 {(p-1)/2 \times (p+1)/2})$ . The sum in parenthesis simplifies to a fraction $\frac r s$ in lowest terms, where s is not divisible by p. Hence the sum is $\frac {pr} s$ 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 $\mathbb Q$ :

$\mathbb Z_{(p)}$ = the set of all rational numbers of the form $\frac a b$ , 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 $\mathbb Z \subset \mathbb Z_{(p)}$ .

Next we proceed to define divisibility by powers of p :

Definition. An element $x \in \mathbb Z_{(p)}$ is said to be divisible by $p^n$ (for positive integer n) if we can find $y \in \mathbb Z_{(p)}$ such that $x = p^n y$ .

Examples. Suppose p=5. Then the rational numbers $\frac 1 3, \frac 2 7, \frac{25} {17}$ are all elements of $\mathbb Z_{(p)}$ . Clearly, the first two numbers are not divisible by p, while the last is divisible by p².

For the set $\mathbb Z_{(p)}$ , divisibility really only makes sense for powers of p. To see why, let’s suppose p=5 and we say that an element $x \in \mathbb Z_{(5)}$ is divisible by q=7 if there is a $y\in \mathbb Z_{(5)}$ such that x = 7y. What happens? Why, then every element of $\mathbb Z_{(5)}$ is a multiple of 7 and the definition is meaningless.

Modular Arithmetic

Now we are ready to talk about modular arithmetic for elements of $\mathbb Z_{(p)}$ . Given two elements x, y, from this set, we write $x\equiv y \pmod {p^n}$ if the difference $x-y$ is divisible by $p^n$ , as defined earlier.

For example, you can easily check that for p=7, $\frac 1 3 \equiv -2 \pmod 7$ and $\frac 3 {10} \equiv 15 \pmod {7^2}$ .

Basic Properties I. Easy exercise: prove that the following are true for any $x, y, z \in \mathbb Z_{(p)}$ .

(Reflexive) $x\equiv x \pmod {p^n}$ .
(Symmetric) If $x\equiv y \pmod {p^n}$ , then $y \equiv x \pmod {p^n}$ .
(Transitive) If $x\equiv y \pmod {p^n}$ and $y \equiv z \pmod {p^n}$ , then $x \equiv z \pmod {p^n}$ .

Once again, these three properties are the crux of any “equivalence” property. Next, we need to ensure that congruence modulo $p^n$ respects the arithmetic operations.

Basic Properties II. More easy exercises: prove that the following are true for any $a,b,c,d \in \mathbb Z_{(p)}$ such that $a\equiv b \pmod {p^n}$ and $c \equiv d \pmod {p^n}$ . [ The proofs for the first 3 properties are identical to the case of integers! ]

$a + c \equiv b + d \pmod {p^n}$ ;
$a\times c \equiv b \times d \pmod{p^n}$ ;
for m = 1, 2, …, we get $a^m \equiv b^m \pmod {p^n}$ ;
if c (and hence d) is not a multiple of p, then $\frac a c \equiv \frac b d \pmod {p^n}$ .

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 $x \in \mathbb Z_{(p)}$ is congruent to exactly one of $\{0, 1, 2, \dots, p^n-1\}$ modulo $p^n$ .

Proof : It suffices to show x is congruent to some integer modulo $p^n$ . Writing $x = \frac a b$ , where b is not divisible by p, it suffices to show $\frac 1 b$ is congruent to some integer integer mod $p^n$ . Now Bezout’s identity helps us out: since b and pⁿ are coprime, write $rb + sp^n = 1$ for some integers r and s. Now we get $\frac 1 b - r = \frac {1-rb} b = p^n \frac s b$ and our job is done. ♦

In short, we have extended our definition of modular arithmetic to the larger set $\mathbb Z_{(p)}$ instead of the usual $\mathbb Z$ . As a tradeoff, however, now we can only talk about congruence modulo powers of p, instead of general n.

Applications

Without further delay, let’s dive into the proof of problem 2.

Solution to Problem 2. Pair up the terms as earlier, thus giving:

$p(\frac 1 {1\times {p-1}} + \frac 1 {2\times {p-2}} + \dots + \frac 1 {(p-1)/2 \times (p+1)/2}).$

We need to show that the sum in parenthesis is a multiple of p. But note that each summand is of the form $\frac 1 {i \times(p-i)} \equiv \frac 1 {i(-i)} = -\frac 1 {i^2} \pmod p$ . So we need to show $\sum_{i=1}^{(p-1)/2} \frac 1 {i^2} \equiv 0 \pmod p$ . This is not hard:

For $i = 1, 2, \dots, \frac{p-1}2$ , the squares are all distinct (if not, then $i^2 \equiv j^2 \pmod p$ , so $i^2 - j^2 = (i-j)(i+j)$ is a multiple of p and either $i-j$ or $i+j$ is a multiple of p).
This also means the reciprocals $\frac 1 {i^2}$ for $i=1,2,\dots,\frac{p-1}2$ are also distinct. (*)
Since $x \equiv (p-x)^2 \pmod p$ , the squares $1^2, 2^2, \dots, (\frac{p-1}2)^2$ cover all the possible non-zero squares mod p and they’re all distinct.
By (*), we see that the same holds for $\frac 1 {i^2}$ , $i = 1,2,\dots, \frac{p-1}2$ .

In other words, the reciprocals $1, \frac 1 {2^2}, \frac 1 {3^2}, \dots, \frac 1 {[(p-1)/2]^2}$ are congruent to $1, 2^2, 3^2, \dots, (\frac{p-1}2)^2$ modulo p, after some permutation. Hence, modulo p, our sum is congruent to

$1^2 + 2^2 + \dots + (\frac {p-1}2)^2 = \frac{(\frac{p-1}2)(\frac{p+1}2)p}6$

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 $q = \frac{3p-5}2$ . Define the sum:

$S_q = \frac 1 {2\times 3\times 4} + \frac 1 {5\times 6\times 7} + \dots + \frac 1 {q(q+1)(q+2)}.$

Prove that if $\frac 1 p - 2 S_q = \frac m n$ in lowest terms, then $p | (m-n)$ .

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 $a_n = 2^n + 3^n + 6^n - 1$ for positive integer n. Find all positive integers k which are coprime to all $a_n$ in the sequence.

Hint. [Highlight start] Note that 1/2 + 1/3 + 1/6 – 1 = 0. [Highlight end]

Philosophical Ramblings

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.

Modular Arithmetic Deluxe Edition

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages

Modular Arithmetic Deluxe Edition

Share this:

Like this:

Related

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages