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

See also:

- Fermat's Prime Factorization Method
- Fermat Method: Odd and Even a's and b's
- 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^{2}−b^{2}=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^{2}−b^{2}=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.

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^{2}−N=b^{2}
[1.02]

Or, in mod 10:

a^{2}−N≡b^{2}
(mod 10) [1.03]

That is:

a^{2}−N≡b^{2}(a perfect square) (mod
10) [1.04]

So:

a^{2}≡N+b^{2}(a perfect square (mod 10) [1.05]

We write a multiplication table for our chosen modulus.

Multiplication mod 10 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |

0 | 0 |
0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

2 | 0 | 2 | 4 | 6 | 8 | 0 | 2 | 4 | 6 | 8 |

3 | 0 | 3 | 6 | 9 | 2 | 5 | 8 | 1 | 4 | 7 |

4 | 0 | 4 | 8 | 2 | 6 | 0 | 4 | 8 | 2 | 6 |

5 | 0 | 5 | 0 | 5 | 0 | 5 | 0 | 5 | 0 | 5 |

6 | 0 | 6 | 2 | 8 | 4 | 0 | 6 | 2 | 8 | 4 |

7 | 0 | 7 | 4 | 1 | 8 | 5 | 2 | 9 | 6 | 3 |

8 | 0 | 8 | 6 | 4 | 2 | 0 | 8 | 6 | 4 | 2 |

9 | 0 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |

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.

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]

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)

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.

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^{2}≡N+b^{2}, a perfect square [1.05,
repeated]

We consider the numbers modulo 10, so

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]

Because a is odd, b is even, so we require only the even numbers for b^{2}:

0,4,6

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

and using a^{2}≡N+b^{2}
[1.05 repeated]

a^{2}≡1+0 ≡1, or 9+0≡9 (mod 10)

We also require that a^{2}−b^{2}≡1
(mod 10)

if a^{2}≡1, and b^{2}≡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^{2}=4.

Substituting in a^{2}≡N+b^{2}
[1.05 repeated], for N≡1, b^{2}≡4, we get:

a^{2}≡1+4≡5 (mod 10), (a perfect square,
so a possible solution.)

We require a^{2}−b^{2}≡1, which 5−4 satisfies,
with a^{2}≡5 (mod
10)

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

5^{2} − 121 is negative,
so we check the next one, 15:

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

15^{2}−2^{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.

b^{2} |
N+b^{2} |
Perfect Square Modulo 10? |
---|---|---|

0 | 1 | Yes |

4 | 5 | Yes |

6 | 7 | No |

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^{2}≡N+b^{2} 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^{2}≡N+b^{2}, a perfect square [1.05,
repeated]

Because N is 4633, then N≡3 (mod 10) so possible values of a^{2} 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^{2}
are odd numbers. So the only possible values of a (modulo 10)
are 1 and 9

So, a^{2} is 1 or 9 is a perfect square and an odd number (modulo 10)

So a^{2}≡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^{2}−b^{2}≡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^{2}−N=b^{2} [from 1.05]

So, a^{2} 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^{2}−4633=696 (not a perfect square)

Next, try 77:

77^{2}−4633=1296=36^{2} (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.

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

Without wishing to spoil the plot, it would take about 1000 trial divisions to factorize this number.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^{2}≡N+b^{2}(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^{2}≡N+b^{2 } with N≡3, and the a^{2}
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^{2} could be 1 or 6, but because
b is odd,
then

b^{2}≡1,

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

a^{2}≡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^{2}-651^{2}=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.

See here for the Modulo 30 table.

The following are perfect squares modulo 30: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

a^{2}≡N+ b^{2},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^{2} 's modulo 30, using
[4.1] to find values where a is even,
and b odd.

Substituting in b^{2}+N≡a^{2}(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^{2}≡4, that is:

a^{2}≡4, when b^{2}≡21, so b=9 or 21

a≡2, 8

The a's and b's need to satisfy a^{2}−b^{2}≡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^{2}−651^{2}=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.

Below is a table modulo 30

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: