## 3.3   % n

### 3.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.

Your browser does not support java.

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.

Your browser does not support java.

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:

Your browser does not support java.

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