--%>

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 assignment complete assignment

    complete assignment with clear solution and explanation

  • Q : Explain lognormal stochastic

    Explain lognormal stochastic differential equation for evolution of an asset.

  • Q : Who derived the Black–Scholes Equation

    Who derived the Black–Scholes Equation?

  • Q : Explain the work and model proposed by

    Explain the work and model proposed by Richardson.

  • Q : What is Non-Logical Vocabulary

    Non-Logical Vocabulary: 1. Predicates, called also relation symbols, each with its associated arity. For our needs, we may assume that the number of predicates is finite. But this is not essential. We can have an infinite list of predicates, P

  • Q : Formulating linear program of a

    A software company has a new product specifically designed for the lumber industry. The VP of marketing has been given a budget of $1,35,00to market the product over the quarter. She has decided that $35,000 of the budget will be spent promoting the product at the nat

  • Q : Test Please read the assignment

    Please read the assignment carefully and confirm only if you are 100% sure. Please go through below mentioned guidelines and penalties: • Your solution must be accurate and complete. • Please do not change Subject Title of the Email. • Penalty clause will be applied in case of delayed or plag

  • Q : Probability and Stochastic assignment

    Introduction to Probability and Stochastic Assignment 1: 1. Consider an experiment in which one of three boxes containing microchips is chosen at random and a microchip is randomly selected from the box.

  • Q : How to calculate area of pyramid

    Calculate area of pyramid, prove equation?

  • Q : Profit-loss based problems A leather

    A leather wholesaler supplies leather to shoe companies. The manufacturing quantity requirements of leather differ depending upon the amount of leather ordered by the shoe companies to him. Due to the volatility in orders, he is unable to precisely predict what will b