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.
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:
Given to find with it is best to look at two cases, whether or whether
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