We’re pretty sure that classical computers can’t break RSA (because it is hard to factor large numbers on them), but we know that quantum computers theoretically could. In this question, we will prove a fact that is a key part of Shor’s Algorithm, a quantum algorithm for factoring large numbers quickly1 . Let N = pq where p, q are primes throughout this question. (a) Prove that, for all a ∈ N, there are only four possible values for gcd(a, N). (b) Using part (a), prove that, if r 2 ≡ 1 mod N and r 6≡ ±1 (mod N) (i. e. r is a "nontrivial square root of 1" mod N), then gcd(r −1,N) is one of the prime factors of N. Hint: r2 = 1 mod N can be rewritten as r2 −1 = 0 mod N or (r +1)(r −1) = 0 mod N.