Homework Number Four

This is due on Fri 28 Feb.

Note: when I say "describe" a Turing machine, I mean write down the set of states and convince me that you could (if I pressed you) write down the function which says what the machine is to do when in a given state and reading a given symbol. You do not need to write down the function explicitly (though that is certainly the nmost direct way of convincing me that you could write it down), a clear explanation of the behaviour of the machine given in informal language is sufficient.

1. (20 points)
   1. (5 points) Find the multiplicative inverse of 16 + 105 Z in the structure Z/105 Z (the set of congruence classes mod 105)
   2. (5 points) Find the multiplicative inverse of 80845 + 962829 Z in Z/962829 Z.
   3. (10 points) Let $n > 1$ be an integer. How many elements of A of Z/n Z have the property that A^m = 0 + n Z for some integer m greater than 0?
2. (10 points) A naive algorithm for testing a number n > 1 for being prime is to try dividing n by every m with 1 < m < n in turn; if we find an m which divides n we stop and conclude that n is composite, otherwise we conclude n is prime.
   1. (5 points) Show that we can improve this algorithm by only checking for divisors m which are less than or equal to the square root of n.
   2. (5 points) Is the number of steps in the first algorithm I described bounded by some polynomial function of the size of n? What about the impoved algorithm where we only go up to the square root of n? (Each division counts as one step here)
3. (10 points) Describe a Turing machine which implements the successor function. More precisely it must have the following properties
   1. Its alphabet must consist of the symbols 0, 1 and BLANK.
   2. For any integer n > 0 let the binary expression of n be a_0 .... a_K and let the binary expression of n +1 be b_0 ..... b_L

      If the machine is started with a_i in cell i+1 for each i between 0 and K and BLANK's elsewhere, then it must stop with b_j in cell j - L - 1 for every j between 0 and L and BLANK in cell 0 and cell -L-2.

4. (20 points) Describe a Turing machine which implements the function of addition for two positive integers. This time I leave the details of how to organise the input and the output to you.
5. (15 points) Let p be prime.
   1. (5 points) Show if A is in Z/p Z and A is not the class 0 + p Z then A has a multiplicative inverse in Z/p Z.
   2. (5 points) Show there are exactly two elements A in Z/p Z such that A^2 = 1 + p Z and identify them.
   3. (5 points) Is it true that for some n there are are more than two elements A of Z/n Z such that A^2 = 1 + n Z ?
6. (15 points) Let n > 1 and let A be a class in Z/n Z which has a multiplicative inverse. Show that A^m = 1 + n Z for some integer m > 1.

   Hint: look at the sequence A, A^2, A^3, A4 ....