These questions are due Friday, April 9 at the beginning of lecture.
- Let
be the function given by
Show that
is a bijection.
- Define
by setting
and, if
then, letting
be the smallest prime such that
then
[Here,
.] Compute
for
and show that
is one-to-one.
A kind of library 
Here are some suggestions. This does not mean you have to follow them, but they may be useful.
One way of showing that
is one-to-one is to prove the following by induction on 
: For any 
if 
and 
then 
In problem 1, you need to show
is 1-1 and onto. To show onto: Prove by induction on 
that the equation 
has a solution 
So, you have to find a solution to 
and, from a solution to 
you need to construct a solution 
to 
I strongly suggest that you try a few values first, to get a good idea of what is going on. Once you have an idea, the following will make more sense:
to find 
with 
it is best to look at two cases, whether 
or whether 
Given
To show 1-1: Suppose
You need to show 
and 
Begin by showing that 
One way of doing this is to show that if 
then 
From this, and the definition of
it should now be easy for you to show that if 
then 
And then, of course, it follows that 