Primeiras tentativas

Uma primeira tentativa poderia ser este programa.

Ao tentarmos executar o programa, vimos que ele corretamente disse que M₂ = 3, M₃ = 7 e M₅ = 31 são primos mas incorretamente disse que M₇ = 127 é composto! O que aconteceu? Ao mandarmos o programa imprimir os valores de S_n, vimos $4, 14, 194, 37634, 1416317954, -264425470, -1443577854, \ldots$e fica evidente que algo está muito errado. De fato, o que os computadores chamam de int é um elemento de ${\mathbb{Z} }/(2^N)$ para algum valor de N; no nosso caso, N = 32. Como S_n cresce muito rápido, em poucos passos ultrapassamos o limite de 2^N e os valores de s calculados passam a estar errados.

A solução para o problema é fazer todas as contas modulo M_p, já que só precisamos saber no final se S_p-2 é ou não múltiplo de M_p. Uma versão levemente melhorada do nosso programa seria ll2.c; esta versão do programa agora verifica corretamente que M₂ = 3, M₃ = 7, M₅ = 31, M₇ = 127 são primos, que $M_{11} = 2047 = 23 \cdot 89$ é composto e que M₁₃ = 8191 é primo mas afirma incorretamente que M₁₇ = 131071 é composto. O que ocorre é que apesar de M₁₇ ainda ser bem menor do que 2³², o limite de tamanho de ints, em contas intermediárias elevamos números na faixa de 0 a 131070 ao quadrado, e isto nos joga fora da margem de bom funcionamento de ints.