4. Factoring with square roots Let x ∈ (2, 3, ..., n-2] be a nontrivial square root of 1 modulo n. Show that gcd(x-1,n) is a factor of n. Can you even show n = gcd(x-1,n) gcd(x+1, n)?

Explain how knowledge of such an x allows one to factor n efficiently.