5.4  Applications

A special case of what you have discovered in the course of investigating the nature of solutions to the congruence equation ax === b (mod n) is the following:

If p is prime and a is not a multiple of p, then there exists an integer b such that ab === 1 (mod p).

Now fix p as a prime number, and suppose that a is an integer with 0 < a < p. Then there is an integer b, also between 0 and p, such that ab === 1 (mod p). Since ab === 1 (mod p) implies that ba === 1 (mod p), we can try to pair off the integers between 1 and p – 1 so that the product of each pair is 1. The applet below takes a prime number as input, and displays the inverse for each value of a between 1 and p – 1. Here it is in action with p = 11:

Your browser does not support java.

You may find this applet useful when working on Research Question 6.

5.4.1(a)  Factorials

Recall the definition of n factorial: n! = 1 · 2 · 3 ··· n. The on-line calculator will compute factorials using the usual notation. Try it:

Your browser does not support java.

In Research Question 6, you are asked to investigate the behavior of factorials modulo n.

Your browser does not support java.

Research Question 6

(a) Find a formula for n! % n.
(b) Find a formula for (n – 2)! % n.
(c) Find a formula for (n – 1)! % n.

5.4.1(b)  Hint:

If you have a conjecture that you believe to be correct, but are having trouble finding a proof, it may be helpful to review the proof of the formula for the sum

(1 + 2 + 3 + ··· + n) % n.

Section 5.1 | Section 5.2 | Section 5.3 | Section 5.4 | Section 5.5 | Section 5.6

Chapter 5 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company