--%>
Assignment Help - homework help

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 : 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????

    		•
  • 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 Datalog for defining

    The focus is on  the use of Datalog for defining properties  and queries on graphs. (a) Assume that P is some property of graphs  definable in the Datalog. Show that P is preserved beneath extensions  and homomo

    		•
  • Q : Explain a rigorous theory for Brownian

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

    		•
  • Q : Law of iterated expectations for

     Prove the law of iterated expectations for continuous random variables. 2. Prove that the bounds in Chebyshev's theorem cannot be improved upon. I.e., provide a distribution that satisfies the bounds exactly for k ≥1, show that it satisfies the bounds exactly, and draw its PDF. T

    		•
  • Q : 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.

    		•
  • Q : Problem on Nash equilibrium In a

    In a project, employee and boss are working altogether. The employee can be sincere or insincere, and the Boss can either reward or penalize. The employee gets no benefit for being sincere but gets utility for being insincere (30), for getting rewarded (10) and for be

    		•
  • Q : What is the definition of a group Group

    Group: Let G be a set. When we say that o is a binary operation on G, we mean that o is a function from GxG into G. Informally, o takes pairs of elements of G as input and produces single elements of G as output. Examples are the operations + and x of

    		•
  • Q : Set Theory & Model of a Boolean Algebra

    II. Prove that Set Theory is a Model of a Boolean Algebra The three Boolean operations of Set Theory are the three set operations of union (U), intersection (upside down U), and complement ~.  Addition is set

    		•
  • Q : Who developed a rigorous theory for

    Who developed a rigorous theory for Brownian motion?

    		•