# Math 320 Group Exam

1. For n a natural number, let f (n) represent the number
of factors of n . For example,

f (6) = 4, because 6 has four factors : 1, 2, 3, and 6.

a. Make a table of n and f (n) for n =1 to n =25. Describe
any patterns you

notice in your table

b. Let p be a prime. Find f ( p) and prove your result.

c. Find f ( p^{2} ) and f ( p^{3} ) and prove your results.

d. Find f ( p^{n} ) and prove your result.

e. Now let p,q and r be primes. Find f ( pq) , f ( p^{2}q)
and f ( pqr) and prove

your results.

f. How can you find f (n) , for any n ?

2. For n a natural number, let g(n) represent the number
of natural numbers less than n

and relatively prime to it. For example, g(5) = 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, g(12)
= 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 n and g(n) for n=1 to n=25. Describe
any patterns you

notice in your table.

b. Let p be a prime. Find g( p) and prove your result.

c. Find g( p^{2} ) and g( p^{3} ) and prove your results.

d. Find g( p^{n} ) and prove your result.

e. From your table and your results above, can you find a
method for

determining g(n) for any n ?

f. Below is an example that we will use to illustrate an
amazing property of

g (n) . We illustrate for n =12. Start by writing all fractions with denominator

n and numerators from 0 to n -1:

Now simplify and group by denominators (simplify 0/n to 0/1 ):

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 g(n) .

3. In this problem, we will explore powers in various modulos.

a. Either using Excel (or by hand), for each n from 3 to
12, make a table of the

first 2 n powers of 2, 3, …, n -1, mod n . For example, here is a table mod 7:

Note that it is better to reduce by the modulo , as you go
along to avoid

round off errors. For example, to compute 4^{4}, you can multiply 4^{3} ≡1 (mod 7)
by 4 to get

4, instead of computing 4^{4}=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 a mod n , is defined as the smallest k
such that a^{k} ≡1(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 a mod n is undefined if no power of a is ever
equal to 1 mod

n . Determine when the order of a is defined and when it is undefined. For

which mods are the orders of 2, 3, …, n-1 always defined?

d. For this part of the problem, only use mods, n , for
which the orders of 2, 3,

…, n -1 are always defined. What are the possible orders in each of these

mods? How many numbers have each order? Prove as much as you can, and

also relate to the first few problems.

e. Now explore the a ’s that do have a defined order, in
the mods where some

a ’s don’t have a defined order (for example, in mod 4, the order of 3 is 2, but

the order of 2 is undefined). How many such a ’s are there? What orders do

they have?

f. In the chart in part a, the 6^{th}and 12^{th}powers mod 7
are 1 for all a ’s. Explore

similar patterns other modulos. Here is an example that might help you prove

a result here:

Note that mod 7, we have: 3*1=3, 3*2=6, 3*3=2, 3*4=5,
3*5=1, and

3*6=4. Now if we multiply all of the above together, we get

3*1*3*2* 3*3* 3*4* 3*5* 3*6. Rearranging, we get 3^{6}*(1*2*3*4*5*6). Now we also

know that this product is equal to 1*2*3*4*5*6. Fill in the details…and make
more

general.

4. In this problem, we relate the results of the first few
problems to patterns in decimals

and expansions in various bases.

a. Read the attached handout about why the standard long
division algorithm

works. Use the standard long division algorithm to show that
and explain

why the algorithm works.

b. Note that 10 ≡ 3(mod 7),10^{2} = 2(mod 7),10^{3} ≡ 6(mod 7)
, 10^{4} ≡ 4(mod 7),

10^{5} ≡ 5(mod 7) , and 10^{6} ≡1(mod 7) . Show where the set of remainders, {3, 2,
6, 4, 5, 1}

appear in the division algorithm for computing the expansion of 1/7 in part a.
Adapt this

connection to show how to compute the period of 1/13 without actually finding
the

decimal expansion of 1/13 .

c. Explain how to find the period of 1/p for any prime p
in any base b , without

actually computing the expansion of 1/p. Make up a few examples to illustrate
your

method.

d. What connections do you see between your results in the
first three problems

and patterns you observed in looking at the expansions of unit fractions in
various bases?

e. The expansions of
and are all strictly repeating, with shifted

versions of the same six digits. The computations below give insight into this
pattern:

Note that the numerators of the fractions appear in the
same order {3, 2, 6, 4, 5, 1} as the

example in part b; is this a coincidence?

The expansions
are not all shifts of the same pattern, as was the case for

fractions with denominator 7. Why doesn’t the same method work in this case?
Find

another fraction with prime denominator where
are all shifts of the

same digits. What characterizes denominators with this property?

f. Notice that and
all have repeating digits in their
expansions that

are some shift of , but
and have
different digits (and the latter has period

42). Note also that and
Which

fractions of the form will have repeating
digits that are shifts of Explain.

g. Now use the above to say something more general.

Copyright 2005, Debra K. Borkovitz. You may copy or edit
this material for nonprofit,

educational use only.

Prev | Next |