Ken Ward's Mathematics Pages

Number Theory Fermat Method of Prime Factorization: Sieving

This page considers sieving the possible numbers that are candidates for perfect squares using modular arithmetic.

Number Theory Contents

See also:

• Fermat's Prime Factorization Method
• Fermat Method: Odd and Even a's and b's
• Fermat Method Sieve

Page Contents

1. Fermat Method Sieve
1. Perfect Squares Modulo 10
2. Computing the a's modulo 10
3. Perfect Squares Modulo 30
4. Factorizing N=6,747,883
5. Computing the a's Modulo 30

Fermat Method Sieve

A sieve attempts to separate possible solutions from impossible ones. In this case, we seek to separate the steps from the Fermat Method of Prime Factorization which do not lead to a solution, from those which might lead to a solution. The method of finding whether the a's and b's are odd or even in:

a²−b²=N

when we are trying to factorize N using Fermat's Method is a method of sieving, because when we find that a, for instance, is even, we do not need to test the odd values of a (we sieve them out), and sieving these out reduces the work involved by about one half, because we remove all the odd a's.

Here, we attempt to remove more a's from our procedure in the following way.

We recall:

a²−b²=N       [1.01]

Where a, b and N are positive integers, and N is odd. [If N is even, we divide by the factor 2, until it is odd.]

We seek to factor N by seeking a's and b's which satisfy equation [1.01], so, by factorising, we seek:

(a+b)(a−b)=N, giving us factors of N.

Use Modulo

We can work in a modulus arithmetic to limit the numbers we seek. In seeking the factors of 221, we use modulo 10 because it is easier compute than, say, modulo 15.

By considering [1.01] modulo 10, we can simplify the arithmetic and discover some properties of our a's.

By rearranging [1.01], we get:

a²−N=b²  [1.02]

Or, in mod 10:

a²−N≡b² (mod 10) [1.03]

That is:

a²−N≡b²(a perfect square) (mod 10) [1.04]

So:

a²≡N+b²(a perfect square (mod 10) [1.05]

We write a multiplication table for our chosen modulus.

Table Mod 10

Perfect Squares Modulo 10

The following six integers are perfect squares modulo 10 (They lie on the diagonal of the above table, 0,0; 9,9):

0, 1, 4, 5, 6, 9    [2.01]

That is, any integer, modulo 10, when squared, produces one of these six integers.

Square Roots Modulo 10

The square roots of each of these numbers (modulo 10) are (from the table):

√0=0

√1=1 or 9

√4=2, or 8

√5=5

√6=4, or 6

√9=3 or 7

[ List 2.2]

Computing the a's modulo 10

Example 1.01

First we can compute k=(221−1)/4=50, so a=2k+1=111, and b=2k=100 giving us:

(111-110)(111+110)=221 (See here for a reminder)

Square Root

We proceed to compute the root of N because one factor of the number must be less than or equal to the square root of that number, which we can find using a calculator or by arithmetic. Calculating the square root enables us to find the upper limit of one factor and so to eliminate larger numbers. We find:

√(N)=√(221)<15

So one factor must be less than 15.

Is a odd or even?

See: Determining the Parity of the a's

We note that because 221 (mod 4)=1, a is odd (and b is even). [If it were -1, then a would be even, and b odd.] So we need to test the odd values of the a's only.

We now know that the a, below, is odd:

a²≡N+b², a perfect square [1.05, repeated]

Modulo 10

We consider the numbers modulo 10, so

Find upper limit for factors:

221≡1 (mod 10)

√(221)<1, or 9 (mod 10)

And noting the perfect squares modulo 10 (from our multiplication table for modulo 10):

0, 1, 4, 5, 6, 9    [2.01, repeated]

Possible values for b²  and a² (modulo 10)

Because a is odd, b is even, so we require only the even numbers for b²:

0,4,6

Starting with b=0, because b² is an even number (a is odd) and a perfect square, and 0 is the first even square modulo 10.

and using a²≡N+b² [1.05 repeated]

a²≡1+0 ≡1, or 9+0≡9 (mod 10)

We also require that a²−b²≡1 (mod 10)

if a²≡1, and b²≡0, the equation above is satisfied.

We have already computed this value, a=111,b=110, which is a trivial solution (1·221=221).

We proceed with the next possible value of b. Which is b²=4.

Substituting in a²≡N+b² [1.05 repeated], for N≡1, b²≡4, we get:

a²≡1+4≡5 (mod 10), (a perfect square, so a possible solution.)

We require a²−b²≡1, which 5−4 satisfies, with a²≡5 (mod 10)

So a will end in 5, and in base 10, this gives us 5, 15, 25 ...

5² − 121 is negative, so we check the next one, 15:

15² −121=4, a perfect square. So a=15 and b=2 are possible solutions. And:

15²−2²=121, so this is one solution. Factorising:

(15+2)(15−2)=17·13=221

gives us the factors of 121: 13 and 17. As these are primes, we have factored 121. If the factors aren't primes, we would repeat out procedure.

Example 1.02

Compute the square root, as usual to find the upper limit of one factor:

√(4633) ≤69

Now we take modulo 10 of the relevant numbers

4633 (mod 10)≡3

Using formula [1.05]:

a²≡N+b² perfect square  [1.05, repeated]

And noting the perfect squares modulo 10:

0, 1, 4, 5, 6, 9    [2.01, repeated]

In order to find out if a is odd or even, we compute k=(4633-1)/4=1158. We know a is odd because, a=2k+1=2317, and, so, b=2316

The perfect squares, modulo 10 are:

0, 1, 4, 5, 6, 9    [2.01, repeated, perfect squares mod 10] We can copy these perfect squares from [2.01] into [1.05]

a²≡N+b², a perfect square [1.05, repeated]

Because N is 4633, then N≡3 (mod 10) so possible values of a² are:

0+3=3 (not a perfect square)

1+3=4 (perfect square, mod 10)

4+3=7 (not a perfect square)

5+3=8 (not a perfect square)

6+3=9 (perfect square, mod 10)

9+3=2 (mod 10)

Using odd/even , we note that 4633=−1 (mod 4), so N is of the form 4m+1, which means a and a² are odd numbers. So the only possible values of a (modulo 10) are 1 and 9

So, a² is 1 or 9 is a perfect square and an odd number (modulo 10)

So a²≡1, or 9 (mod 10)

√1≡1, or 9 (mod 10) and

√9≡3 or 7

The a's and b's need to satisfy a²−b²≡3 (mod 10), we take 9 and 6 as our values

√9≡3 or 7

√6≡4 or 6

So a ends in the digit 3 or 7, and b ends in 4 or 6.

Because  √(4633) ≤69 (=68.0661, 4 decimals)

We have, with a an odd number:

a²−N=b² [from 1.05]

So, a² must be bigger than N (4633) and end in 3 or 7. The first number to check is a=73 (the first number bigger than 69 and ending in 3):

73²−4633=696 (not a perfect square)

Next, try 77:

77²−4633=1296=36² (A perfect square)

So checking only a few numbers (relatively), we discover the factors we seek:

(77-36)(77+36)=

4633=41•113

Which in this case, we could have discovered much faster by applying Fermat to 8 numbers, 69-77, or even faster using trial division of about 15 numbers. However, with slightly larger numbers, trial division can become extremely tedious, as can the Fermat Method.

Factorizing N=6,747,883

Now, we are getting serious and using a largish number, one which pocket calculators may not be able to factorize.

N=6747883

√(6,747,883)<2598

The number is of the form 4m-1, so the a's are even numbers (6747883 mod 4≡ 3, or -1).

We recall:

a²≡N+b²(a perfect square (mod 10) [1.5, repeated]

And the perfect squares, mod 10 are:

0, 1, 4, 5, 6, 9    [2.1, repeated]

And note that:

6747883=3 (mod 10)

So we search for possible a's modulo 10, using a²≡N+b² with N≡3, and the a² perfect squares (mod 10)

3+0≡3 (mod 10), not a perfect square

3+1≡4 (mod 10)

3+4≡7 (mod 10), not a perfect square

3+5≡8 (mod 10), not a perfect square

3+6≡ 9 (mod 10)

3+9≡2 (mod 10), not a perfect square

So, eliminating values that aren't perfect squares, b² could be 1 or 6, but because b is odd, then

b²≡1,

and b≡1 or 9 (mod 10). So:

a²≡4, a≡2 or 8 (mod 10)

The a's will therefore end in 2 or 8.

The checking begins at √(6,747,883)<2598

In fact we need to check 17 numbers until we find:

2678²-651²=6747883

And discover that the factors are (2678+651) and (2678-651), or 3329, and 2027 (see Fermat Method)

This means we would have had to check using the Fermat Method (2678-2598 + 1)=81 terms, and using odd/even, 41 terms.

Let us consider modulo 30, to see if we can reduce the number of items to check. The choice of modulo is somewhat arbitrary. Other bases could be used.

Perfect Squares Modulo 30

See here for the Modulo 30 table.

0, 1, 4, 6, 9,

10, 15, 16, 19

21, 24, 25

The square roots of these numbers, modulo 30 are:

√0≡0

√1≡1, 11, 19 or 29

√4≡2, 8, 22, 28 

√6≡6, 24

√9≡3, 27

√10≡10, 20,

√15≡ 15

√16≡4, 14, 16, 26

√19≡7, 13, 17, 23

√21≡9, 21 

√24≡12, 18

√25≡5, 25 

Computing the a's Modulo 30

a²≡N+ b²,a perfect square (mod 30) [4.1]

We note that N=6747883, and

√(6,747,883)<2598

We compute:

6747883≡13 (mod 30)

We search for possible a² 's modulo 30, using [4.1] to find values where a is even, and b odd.

Substituting in  b²+N≡a²(modulo 30)

0+13≡ 13

1 +13≡ 14

4+13≡ 17

6+13≡ 19 (Perfect Square, but b=6 is even)

9+13≡ 22

10+13≡ 23

15+13≡ 28

16+13≡ 29

19+13≡ 2

21+13≡ 4 (Perfect Square, a=4 is even, and b=21 is odd, as required)

24+13≡ 7

25+13≡ 8

As the a's are even, then of the possible squares, we have a²≡4, that is:

a²≡4, when b²≡21, so b=9 or 21

a≡2, 8

The a's and b's need to satisfy a²−b²≡13 (mod 30), and 4 and 21 satisfy this, 4-21=13 (mod 30)

Because

√(N)=√(6,747,883)<2598, and

2598=86•30+18

We need to check the a's beginning with 87•30+2, up to 2678, which are:

87•30+2=2612

87•30+8=2618

88•30+2=2642

88•30+8=2648

89•30+2=2672

89·30+8=2678

and this last one gives us:

2678²−651²=6747883

So the factors are: (2678+651)(2678−651), or

3329, and 2027

So we needed only 6 numbers, compared with 17 using the modulo 10 method.

Mod 30 Table

Below is a table modulo 30

Number Theory Contents

Ken Ward's Mathematics Pages