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
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.
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:
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. |
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