Try our Free Online Math Solver!

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, …, n1 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 