CS-235. Problem Set 7


  1. Compute all square roots of 1,2,3,4,5, 6 (mod 77). Show your work; If there is no root, explain why.
    (Do not use exhaustive search!)
  2. How many square roots does 1 have modulo 5, 7, 15, 27, 105,  and 315? Explain.
  3. Same as the previous question, but now for cubic (rather than square) roots.
    How many cubic roots does 2 have modulo 3, 5, 7, 15, 105? Compute them.
  4. Suppose that you have an quadratic equation with roots a, b.
    Then this equation can be written as (x-a)(x-b)=0 :  clearly, it has exactly two solutions (x=a and x=b).
    If you open parentheses then you have x2 - (a+b)x +ab=0.
    Use this and the formula for solving quadratic equations to factor n which is a product of two primes, given n and φ(n).
    Verify your method by factoring n=25651, given that φ(n)=25312.
    (No guesswork!)