--%>

Explain Factorisation by Fermats method

Factorisation by Fermat's method: This method, dating from 1643, depends on a simple and standard algebraic identity. Fermat's observation is that if we wish to nd two factors of n, it is enough if we can express n as the di fference of two squares. This is because if n = a2 - b2, then we have immediately

n = a2 - b2 = (a+b)(a - b);

and so we have found two factors, a+b and a - b, of n.

It is possible here that a - b might equal 1, in which case we will only have found the trivial factorisation n = n x 1, but we can arrange matters so that this will only happen if n has no other factorisation - i.e., is prime.

At first glance, it may seem over-optimistic to hope that an expression for n as the di fference of two squares will exist.

But assume that n is odd, which we can always do if we are trying to factorise n. Then if n = uv and we put

a = 1/2(u+v) and b = 1/2(u - v);

we have n = a2 - b2 (note that a and b are both integers if n is odd), so that a representation of n as the difference of two squares does exist. (In fact, it is easy to see that the above formulae define a one-to-one correspondence between representations of n as the di erence of two squares and as the product of two factors - exercise.)

   Related Questions in Mathematics

  • Q : Linear programming model of a Cabinet

    A cabinet company produces cabinets used in mobile and motor homes. Cabinets produced for motor homes are smaller and made from less expensive materials than those for mobile homes. The home office in Dayton Ohio has just distributed to its individual manufacturing ce

  • Q : Competitive equilibrium 8. Halloween is

    8. Halloween is an old American tradition. Kids go out dressed in costume and neighbors give them candy when they come to the door. Spike and Cinderella are brother and sister. After a long night collecting candy, they sit down as examine what they have. Spike fi

  • Q : Mathematical Method for Engineers The

     The function is clearly undefined at , but despite all of this the function does have a limit as approaches 0. a) Use MATLAB and ezplot to sketch for , and use the zoom on facility to guess the . You need to include you M-file, outp

  • Q : Problem on augmented matrix Consider

    Consider the following system of linear equations.  (a) Write out t

  • Q : Explain a rigorous theory for Brownian

    Explain a rigorous theory for Brownian motion developed by Wiener Norbert.

  • Q : Explain Factorisation by trial division

    Factorisation by trial division: The essential idea of factorisation by trial division is straightforward. Let n be a positive integer. We know that n is either prime or has a prime divisor less than or equal to √n. Therefore, if we divide n in

  • Q : Statistics math Detailed explanation of

    Detailed explanation of requirements for Part C-1 The assignment states the following requirement for Part 1, which is due at the end of Week 4: “Choose a topic from your field of study. Keep in mind you will need to collect at least [sic] 3- points of data for this project. Construct the sheet y

  • Q : State Fermat algorithm The basic Fermat

    The basic Fermat algorithm is as follows: Assume that n is an odd positive integer. Set c = [√n] (`ceiling of √n '). Then we consider in turn the numbers c2 - n; (c+1)2 - n; (c+2)2 - n..... until a perfect square is found. If th

  • Q : First-order formulas over the

    Consider the unary relational symbols P and L, and the binary relational symbol On, where P(a) and I(a) encode that a is apoint and a (sraight) line in the 2-dimensional space, respectively, while On(a,b) encodes  that a is a point, b is a line, and o lies on b.

  • Q : Maths A cricketer cn throw a ball to a

    A cricketer cn throw a ball to a max horizontl distnce of 100m. If he throws d same ball vertically upwards then the max height upto which he can throw is????