Math 320
Fall 04
Group Exam
1. For n a natural
number, let represent the number of factors of
. For example,
,
because 6 has four factors: 1, 2, 3, and 6.
a. Make
a table of and
for
=1 to
=25.
Describe any patterns you notice in your table
b. Let
be a prime.
Find
and prove your result.
c. Find
and
and prove your results.
d. Find
and prove your result.
e. Now
let and
be primes.
Find
,
and
and prove your results.
f.
How can you find ,
for any
?
2. For a natural number, let
represent the number of natural numbers less
than
and relatively prime to it. For example,
= 4, because 1,2, 3, and 4 are less than 5 and
the greatest common factor of 5 and each of these numbers is 1. Also,
= 4, because 1, 5, 7, and 11 are the only four
natural numbers less than 12 that are relatively prime to 12.
a. Make
a table of and
for n=1 to n=25. Describe any patterns you notice in your
table.
b. Let
be a prime.
Find
and prove your result.
c. Find and
and prove your results.
d. Find
and prove your result.
e. From
your table and your results above, can you find a method for determining for any
?
f.
Below is an example that we will use to illustrate an
amazing property of .
We illustrate for
=12.
Start by writing all fractions with denominator
and numerators from 0 to
-1:
Now simplify and group by
denominators (simplify to
):
For any n, how many groups will there be (i.e. how many different denominators)?
Given the denominator of a group, within the group, how many different numerators will there be?
Use the above to illustrate an
amazing property of .
3. In this problem, we will explore powers in various modulos.
a. Either
using Excel (or by hand), for each from 3 to 12, make a table of the first 2
powers of 2, 3, …,
-1, mod
. For example, here is a table mod 7:
|
|
^1 |
^2 |
^3 |
^4 |
^5 |
^6 |
^7 |
^8 |
^9 |
^10 |
^11 |
^12 |
^13 |
^14 |
|
2 |
2 |
4 |
1 |
2 |
4 |
1 |
2 |
4 |
1 |
2 |
4 |
1 |
2 |
4 |
|
3 |
3 |
2 |
6 |
4 |
5 |
1 |
3 |
2 |
6 |
4 |
5 |
1 |
3 |
2 |
|
4 |
4 |
2 |
1 |
4 |
2 |
1 |
4 |
2 |
1 |
4 |
2 |
1 |
4 |
2 |
|
5 |
5 |
4 |
6 |
2 |
3 |
1 |
5 |
4 |
6 |
2 |
3 |
1 |
5 |
4 |
|
6 |
6 |
1 |
6 |
1 |
6 |
1 |
6 |
1 |
6 |
1 |
6 |
1 |
6 |
1 |
Note that it is better to reduce by the modulo, as you go along to avoid round off errors. For example, to compute 44, you can multiply 43≡1 (mod 7) by 4 to get 4, instead of computing 44=256, and then finding that 256≡4 (mod 7).
b. Look for patterns in your tables. Try to justify as many as you can.
c. The
order of mod
,
is defined as the smallest
such that
(mod n).
For example, using the table above, we can see that the order of 6 mod 7
is 2, the orders of 2 and 4 mod 7 are 3, and the orders of 3 and 5 mod 7 are
6.
The order of mod
is undefined if no power of
is ever equal to 1 mod
. Determine when the order of
is defined and when it is undefined. For which mods are the orders of 2, 3, …, n-1
always defined?