a

If the a's are odd, then N is of the form 4m-1, and if the a's are even, then N is of the form 4m+1

This means we can reduce the number of a's we need to test by a half. We also show how to calculate the a values when a-b=1

See also:

- Fermat's Prime Factorization Method
- Number Theory Contents
- Fermat Method: Odd and Even a's and b's

a

where a, b and N are integers, and a>b, and N is an odd integer. We are interested only in odd N's because we are concerned with factorization, and an even N can always be divided by 2 until it becomes odd.

We seek the a and b value when a-b=1

Clearly, either a or b must be odd and the other even.

Suppose a is odd. As every odd number can be expressed in the form 2k±1, where k is an integer. Here k is a non-negative integer. b is an even one.

Let a=2k+1, and b=2k (noting a-b=1 by assumption)

So,

a

(2k+1)

4k

4k+1=N

Therefore:

[1.1]

when a is odd and b is even.

On the other hand, if a is even and b is odd:

Let a=2k and b=2k-1

So:

a

(2k)

4k

4k-1=N

Therefore:

[1.2]

When a is even and b is an odd number.

4k-1=247, so k=62

a=2•62=124

124

a

where a and b are positive integers and a>b.

There is at least one a and a corresponding b and there may be several such pairs.

Let p and q be any two factors of N. p and q are positive integers, and because N is odd, then both p and q are odd.

If a number is divided by 4, then the possible remainders are 0, 1, 2 and 3. If the remainder is 0 or 2, then the number is an even number. If the remainder is 1 or 3, the number is odd. A remainder of 3, as the least positive remainder, is equivalent to a remainder of -1, which is the least absolute remainder. Any odd number is therefore in the form 4m±1.

First we prove that if a is even (and b odd) then N is of the form 4m-1. And when a is odd (and b is even) then N is of the form 4m+1.

Then we prove the converse, the if N is of the form 4m+1, then a is even, and when N is of the form 4m-1, then a is odd.

As N is an odd number, it must be in

We note that:

p=a+b, and q=a-b (q is therefore the smaller factor of the pair). [2.2]

b=a-q [2.3]

a

2aq+q

We note that q is an odd number, and when squared it is of the form 4m+1, where m is any positive integer. For instance, if q=2m+1, then

q^{2}=(2m+1)^{2}=

4m^{2}+4m+1=

4m(m+1)+1=

4mn+1 (where n=m+1)

4m

4m(m+1)+1=

4mn+1 (where n=m+1)

So q

Back to Equation 2.5. The square of q is of the form 4m+1. 2aq is clearly an even number, whatever the sign of a and q. (Of course q is always odd). a can be even or odd. If a is even, then 2aq will be of the form 4k,

because if a=2l,

then 2•2l•q=4lq

And

4m+4lq+1=4(m+lq)+1, which is in the form 4m+1

So, if a is an even number (and b is odd) then the number N will be in
the form 4m+1then 2•2l•q=4lq

And

4m+4lq+1=4(m+lq)+1, which is in the form 4m+1

On the other hand, if a is an odd number, then if we write the odd part, aq as 2k+1, then

2aq=2(2k+1)=4k+2

And

2aq+q^{2}=4k+2+4m+1≡

4m+3≡

4m-1

So, if a is an odd number, then N is of the form 4m-1And

2aq+q

4m+3≡

4m-1

Now we prove the converse. First, if N is of the form 4m+1, then a is an even number.

2aq+q

Let N=4m+1, and q, an odd number is 2k+1

So

2a(2k+1)+(2k+1)

Left hand side equals

4ak+2a+4k

4m+1

So,

4k(a+k+1)+2a=4m

As the right-hand-side is divisible by 4, and 4k(a+k+1) is divisible by 4, then so must

2a

be divisible by 4. In which case, a must be an even number.

So, if N is of the form 4m+1, then a must be an even number.

Now we wish to prove that if N is of the form 4m-1, then a is an odd number.

2aq+q

Let N=4m-1, and q, an odd number is 2k+1, where k is any positive integer.

So

2a(2k+1)+(2k+1)

Left hand side equals

4ak+2a+4k

4m-1

So,

4k(a+k+1)+2(a+1)=4m

Now 4 divides the right-hand-side, and it divides 4k(a+k+1), so it must divide 2(a+1), in which case, a+1 must be an even number, and a is an odd number.

Therefore if N is of the form 4m-1, then a is an odd number.

■

N=533=4•13+1

So the a is odd. We seek therefore the a's which are odd.

√433<24, so we begin with the first odd numbers: 25, 27, ...

In fact, 27 is the a we seek:

27

And the roots are 27+14=41, and 27-14=13.

38

40

42

So the roots are:

42+19=61, and 42-19=23

In both examples, we needed to check only half the number of squares.

Ken Ward's Mathematics Pages

Number Theory Contents

No script follows:

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle: