Ken Ward's Mathematics Pages

Number Theory Divisibility Fermat's Method Odd and Even a's and b's

We can reduce the number of a's we need to check in Fermat's:
a²-b²=N, where N is an odd positive integer.

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

Page Contents

1. Computing the a's and the b's when a-b=1
2. Determining the Parity of the a's and b's

Computing the a's and the b's when a-b=1

Fermat's Method uses the fact that:
a²-b²=N
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²-b²=
(2k+1)²-(2k)²=
4k²-4k²+4k+1=
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²-b²=
(2k)²-(2k-1)²=
4k²-4k²+4k-1=
4k-1=N
Therefore:
[1.2]
When a is even and b is an odd number.

Example 1

N=247. N is of the form 4k-1, so a is even.
4k-1=247, so k=62
a=2•62=124
124²-123²=247=(124+123)(124-123)

Determining the Parity of the a's and b's

We wish to prove that in Fermat's method with N as an odd positive integer, that either all the a's are even and the b's odd or all the a's are odd and the b's are even. The a's are those which satisfy:
a²-b²=(a+b)(a-b)=N [2.1]
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²-(a-q)²=N [2.4]
2aq+q²=N [2.5]

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

So q² is of the form 4m+1 (as is the square of any odd number).

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,

So, if a is an even number (and b is odd) then the number N will be 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
So, if a is an odd number, then N is of the form 4m-1

Now we prove the converse. First, if N is of the form 4m+1, then a is an even number.
2aq+q²=N  [2.5, repeated]

Let N=4m+1, and q, an odd number is 2k+1
So
2a(2k+1)+(2k+1)²=4m+1

Left hand side equals
4ak+2a+4k²+4k+1=
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²=N  [2.5, repeated]

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

Left hand side equals
4ak+2a+4k²+4k+1=
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.
■

Remark

If we need to add 1 to a number to make it divisible by 4, a is even, and if we need to subtract 1, then a is odd.

Example 2

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²-533=14²

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

Example 3

N=1403=4•351-1, so a is even. √1403<38
38²-1403=41
40²-1403=197
42²-1403=361=19²

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

---

---

Faster Arithmetic - by Ken Ward