CS-235. Problem Set 7
- 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!)
- How many square roots does 1 have modulo 5, 7, 15, 27, 105, and
- Same as the previous question, but now for cubic (rather than square)
How many cubic roots does 2 have modulo 3, 5, 7, 15, 105? Compute them.
- 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
Verify your method by factoring n=25651, given that