Thread: Find x such that x^2≡49 (mod pq)

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.

Originally Posted by chrisc

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.

Those equations imply that for some integers . Use Euclid's algorithm to find a and b. Then .

Originally Posted by chrisc

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.

Aren't there a couple more cases? Both primes could simultaneously divide one factor or the other.

Originally Posted by topspin1617

Aren't there a couple more cases? Both primes could simultaneously divide one factor or the other.

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.