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 :Containee problem For queries Q 1 and Q

For queries Q1 and Q2, we say Q1 is containedin Q2, denoted Q1 C Q2, iff Q1(D) C Q2

• ##### Q :Theorem-Group is unique and has unique

Let (G; o) be a group. Then the identity of the group is unique and each element of the group has a unique inverse.

In this proof, we will argue completely formally, including all the parentheses and all the occurrences of the group operation o. As we proce

• ##### Q :Numerical Analysis Hi, I was wondering

Hi, I was wondering if there is anyone who can perform numerical analysis and write a code when required. Thanks

• ##### 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 :Who had find Monte Carlo and finite

Who had find Monte Carlo and finite differences of the binomial model?

• ##### Q :Uniform scaling what is uniform scaling

what is uniform scaling in computer graphic

• ##### Q :Problem on Prime theory Suppose that p

Suppose that p and q are different primes and n = pq.

(i) Express p + q in terms of Ã˜(n) and n.

(ii) Express p - q in terms of p + q and n.

(iii) Expl

• ##### 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

• ##### Q :Logic and math The homework is attached

The homework is attached in the first two files, it's is related to Sider's book, which is "Logic for philosophy" I attached this book too, it's the third file.