Results 1 to 3 of 3

Math Help - Fermat's Algorithm

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    college station
    Posts
    1

    Fermat's Algorithm

    Use Fermat's algorithm to find factors for the following integers: 175,557

    I know that Fermat's algorithm shows you that, given a number n, for integers x and y, n= x2+y2 so n= (x+y)(x-y)

    Using a method I was shown:
    I took [√175,557] which is 419.
    4192 is not 175,557,
    so I took n+1 (which is 420) and computed 4202 - 4192= 823 which is also not a perfect square, and therefore not a factor of 175,577.

    I continued this pattern for a ton of numbers, increasing by one each time, the way we had been shown in class. After 40 test numbers, I realized I am obviously doing something wrong. I would greatly appreciate it if someone could help redirect me in the correct way to use Fermat's algorithm on prime factorization.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,612
    Thanks
    591

    Re: Fermat's Algorithm

    Hey melissa2.

    I think the main mistake you have made is that n = (x-y)(x+y) = x^2 - y^2 and not x^2 + y^2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    65

    Re: Fermat's Algorithm

    Here's another example.

    243

    sqrt(243)=15.588...

    Calculate
    16^2-243 = 13
    17^2-243 = 46
    18^2-243 = 81 = 9^2

    So now you know 243 = 18^2 - 9^2 = 27*9.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermat's little theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 17th 2011, 02:09 AM
  2. fermat's little thm
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 28th 2009, 10:37 AM
  3. Fermat's
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 24th 2008, 06:36 PM
  4. Fermatís Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 25th 2008, 07:12 AM
  5. fermat...or not fermat?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 22nd 2006, 09:16 AM

Search Tags


/mathhelpforum @mathhelpforum