In article <99b89r$lgd$1@abraham.cs.berkeley.edu>, Ian Goldberg <iang@cs.berkeley.edu> wrote:

If p is wrong, the result S' will be correct mod q but incorrect mod p. so S' ^ e mod q = M mod q, but S' ^ e mod p != M mod p.

Therefore GCD(S' ^ e mod n, M) = q, and we're done.

I think you meant GCD((S'^e mod n)-M, n) = q. I don't think what you said is true, since q does not necessarily divide M. - Nikita