Results 1 to 2 of 2

Math Help - Please It is urgent I should submit it tomorrow!!!

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    1

    Please It is urgent I should submit it tomorrow!!!

    Hi all:

    I will be really appreciated if someone can help me solving this homework.


    imagine n = p * q where p and q are primes and are in the form of p = 2t + 1 and q = 2y + 1 where t and y are also prime.

    we are given n and a number b which we know gcd(b, t * y) <> 1. (is not equal to one)

    How can we efficiently factorize n?

    I have some part of the solution.

    n can be written as

    n = 4 * t * y + 2 * t + 2 * y + 1

    now n - 1 = 4 * t * y + 2 * t + 2 * y

    now we should do sth with this and knowing the b to factor n. but what I do not know.

    Thanks for your help in advance.
    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
    If t and y are prime then the only factors of t*y are 1, t, y and t*y. So the only possibilities for b are b=t, b=y or b=t*y.

    If b = t or y then 2b+1 will be a factor of n. So start by dividing n by 2b+1. If the answer is an integer then you have already factorised n.

    If n/(2b+1) is not an integer then you know that b must be t*y. Since n-1 = 4t*y + 2(t+y) it follows that t+y = (1/2)(n-1-4b). Thus you now know t*y and t+y. But t and y are the roots of the quadratic equation x^2-(t+y)x+ty=0. So all you have to do to determine t and y is to solve a quadratic equation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Urgent HW Project Due tomorrow =(
    Posted in the Statistics Forum
    Replies: 5
    Last Post: November 22nd 2009, 06:15 PM
  2. Isolating Variables - urgent (due tomorrow)
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 24th 2008, 11:39 AM
  3. [SOLVED] urgent please.needed for tomorrow
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: July 24th 2008, 05:55 AM
  4. Algebra Help, URGENT! DUE TOMORROW!
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 27th 2008, 03:11 PM
  5. Urgent Math Help, due tomorrow!!!
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: October 20th 2006, 05:18 AM

Search Tags


/mathhelpforum @mathhelpforum