--%>
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 : 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 : Numerical solution of PDE i want you to

    i want you to solve this assignment. this consist of two parts theoretical and coding. the code has to be created by you. no modified or copying code. you have to mention the exact solution and the proportion error. also you have to explain the sketch that you get from the code. these information

    		•
  • Q : State Prime number theorem Prime number

    Prime number theorem: A big deal is known about the distribution of prime numbers and of the prime factors of a typical number. Most of the mathematics, although, is deep: while the results are often not too hard to state, the proofs are often diffic

    		•
  • Q : Problem on Linear equations Anny, Betti

    Anny, Betti and Karol went to their local produce store to bpought some fruit. Anny bought 1 pound of apples and 2 pounds of bananas and paid $2.11.  Betti bought 2 pounds of apples and 1 pound of grapes and paid $4.06.  Karol bought 1 pound of bananas and 2

    		•
  • Q : Explain the work and model proposed by

    Explain the work and model proposed by Richardson.

    		•
  • Q : Problem on reduced row-echelon The

    The augmented matrix from a system of linear equations has the following reduced row-echelon form. 280_row echelon method.jpg

    		•
  • Q : Who independently developed

    Who independently developed a model for simply pricing risky assets?

    		•
  • Q : Simulation with Arena An office of

    An office of state license bureau has two types of arrivals. Individuals interested in purchasing new plates are characterized to have inter-arrival times distributed as EXPO(6.8) and service times as TRIA(808, 13.7, 15.2); all times are in minutes. Individuals who want to renew or apply for a new d

    		•
  • Q : Use MS Excel to do the computations

    Select a dataset of your interest (preferably related to your company/job), containing one variable and atleast 100 data points. [Example: Annual profit figures of 100 companies for the last financial year]. Once you select the data, you should compute 4-5 summary sta

    		•
  • Q : Probability assignments 1. Smith keeps

    1. Smith keeps track of poor work. Often on afternoon it is 5%. If he checks 300 of 7500 instruments what is probability he will find less than 20substandard? 2. Realtors estimate that 23% of homes purchased in 2004 were considered investment properties. If a sample of 800 homes sold in 2

    		•