# Math Help - Find x such that x^2≡49 (mod pq)

1. ## 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.

2. 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 $ap-bq = \pm14$ for some integers $a, b$. Use Euclid's algorithm to find a and b. Then $x = ap\pm7$.

3. 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.

4. 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, $N=pq$, 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 $x^2\equiv49\pmod N$ 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.