chapter  4
16 Pages

Modular arithmetic

Most of the algorithms of the previous chapters prove divisibility by performing the division and checking that the remainder is zero. Now it has been shown, by a method that we will study in Chapter 9, that 5 • 223,473 + 1 is a factor of F(23,471). Since these numbers are very large, we expect that even checking the truth of the statement will take a very long time. So far, so good; but how many digits does F(23,471) have? Using logarithms, it is easy to show that it has more than 1 0 7063 digits! Thus, F(23,471) has more digits than there are particles in the visible universe. Needless to say, we will not be able to show that 5 • 223,473 + 1 is a factor of F(23,471) by performing the division. How is it done, then?