Hand written solution required

Let n be a positive integer of which you would like to prove that it is prime. Suppose you have successfully factored "most" of n - 1 into distinct primes pi: n-1 =PI P2 naz . . . pasm with p; I'm for all i = 1, 2, . . ., s and p, p2 . . PS as > m . Suppose, further, that you have happened upon an integer a such that (i) an-1 = 1 mod n and (ii) god(a Pi - 1, n) = 1 for all i = 1, 2, . . ., S. Prove that n must indeed be prime