There is no end to the divisibility tests we can devise. Let's focus on the ones we encountered in the preceding pages and see how they apply to a few simple arithmetic problems.
The Fibonacci sequence revisited
Let's begin, fittingly, with the Fibonacci sequence. It starts with 0 and then 1, and each subsequent term is the sum of the two preceding terms. The sequence is therefore built up term by term: 0, 1, 1 (= 1 + 0), 2 (= 1 + 1), 3 (= 1 + 2), 5 (= 2 + 3), 8 (= 3 + 5), 13 (= 5 + 8)…
Start with the first term, multiply it by 10 and add the second. Multiply the result by 10 and add the third. Continue in this way. This yields, in turn, 1, 11, 112, 1,123, 11,235, 112,358, 1,123,593… As the process continues, large numbers appear whose digit strings are periodic, with blocks of digits repeating one after another. Feel free to carry on and see for yourself. What is the minimum number of digits in a period?
Let (Ni)i ≥0 denote the successive terms of the Fibonacci sequence. We have N0 = 0, N1 = 1, N2 = 1, and Ni+2 = Ni+1 + Niwhen i ≥ 0. Now, 89 (10–2 × N1 + 10–3 × N2 + 10–4 × N3) is equal to 100 (10–2 N1 + 10–3 N2 + 10–4 N3 +…) – 10 (10–2 N1 + 10–3 N2 + 10–4 N3 + …) – (10–2 N1 + 10–3 N2 + 10–4 N3 + …), which in turn equals N1 + (N2 – N1)10–1 + (N3 – N2 – N1)10–4 + … This last quantity is simply 1 + 0 + 0 + …, namely 1. In other words, the digit strings of the large numbers obtained begin with the integer parts of large powers of 10 multiplied by 1 / 89 = 0.0112359550… The problem thus amounts to finding the smallest integer p such that (10p – 1) is divisible by 89.
