Results 1 to 4 of 4

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

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    89

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by chrisc View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    193
    Quote Originally Posted by chrisc View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by topspin1617 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a ≡ b ?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 7th 2011, 02:06 AM
  2. Replies: 0
    Last Post: June 28th 2010, 09:32 PM
  3. a^p≡1 (mod p^n) iff a≡1 (mod p^(n-1)), n≥2
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 8th 2010, 09:59 AM
  4. x≡y (mod a) => (x,a)=(y,a)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 7th 2010, 06:05 AM
  5. f(x)≡0 (mod 15) Find all roots mod 15
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: February 3rd 2010, 08:16 PM

Search Tags


/mathhelpforum @mathhelpforum