p and q are large primes, x not equal +7 or -7 mod pq
Here is what I've done so far, if someone can help push me to the next step.
Sorry for the lack of [tex] text.
x^2 = 49 (mod pq)
x^2 - 49 = 0 (mod pq)
pq | (x - 7)(x + 7)
p | (x - 7)
q | (x + 7)
or
p | (x + 7)
q | (x - 7)
From here?
I appreciate any help. Thanks for reading.
That is true. But I suspect that the point of this question is that it deals with a method for factorising large numbers.
Suppose that you have a large number N and you suspect that it may be the product of two primes, , but you don't know p or q. It's very hard to factorise large numbers. But if you are able to solve the congruence in such a way that p|(x - 7) and q|(x + 7), then p must be a factor of x-7. This is probably a much smaller number than N, and therefore easier to factorise.