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:
You may find this applet useful when working on Research Question 6.
Recall the definition of n factorial: n! = 1 · 2 · 3 ··· n. The on-line calculator will compute factorials using the usual notation. Try it:
In Research Question 6, you are asked to investigate the behavior of factorials modulo n.
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.
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