## 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.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 +···+

nupon division byn. 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 integernas input, and produces two pieces of output: the sum 1 + 2 + 3 +···+n, and the same sum reduced modulon.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

nas input. The output is a list of the values of1 + 2 + 3 +···+ M(modM)from

M= 1 up toM=n. Here's what we get withM= 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

nbe 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