% n
% n3.3.1 Warming Up
The first experiment will help test your feel for congruences. Below are the first 30 positive integers:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 We can see the congruence classes of these numbers, say modulo 6, with the applet below. But first, try to predict what you think the result will be before executing the command.
Did you predict it correctly? Try changing the 6 to other positive integers and see if you can predict the results. Once you have this down cold, you're ready for Exercise 1 below.
Exercise 1
Identify the pattern when counting modulo n, and explain why this pattern occurs.
3.3.2 Taking Sums
We now consider the question of determining the remainder of the sum 1 + 2 + 3 +···+ n upon division by n. To get a feel for what we might expect, we begin by trying a few simple examples. (Unless the answer to a question is pretty obvious, it is almost always a good idea to try some easy examples.) The applet below takes a positive integer n as input, and produces two pieces of output: the sum 1 + 2 + 3 +···+ n, and the same sum reduced modulo n.
Try it for several different values of n. Can you find the pattern?
You may find it helpful to see several values at once. The applet below takes an integer n as input. The output is a list of the values of
1 + 2 + 3 +···+ M (mod M) from M = 1 up to M = n. Here's what we get with M = 3:
Is the pattern clear? If not, or if you want to confirm your guess, change the 3 to a larger value and execute the applet again. Once you think you know what's going on, you're ready to tackle Research Question 3.
Research Question 3
Let n be a positive integer. Find a simple formula for
(1 + 2 + 3 +···+ n) % n.
Section 3.1 | Section 3.2 | Section 3.3 | Section 3.4
Copyright © 2001 by W. H. Freeman and Company