Resíduos Quadráticos

O resto da divisão de um quadrado por 100 só pode ter um de 22 valores distintos:

 {00,01,04,09,16,25,36,49,64,81,21,24,29,41,44,56,61,69,76,84,89,96} 

Isto acelera os testes feitos manualmente. Mas a base 100 só é realmente melhor para os humanos.

Uma verificação rápida das bases até 256, revela que algumas têm porcentagens menores de resíduos quadráticos:

80=>12 (15%)
96=>14 (14%)
112=>16 (14%)
120=>18 (15%)
144=>16 (11%)
160=>21 (13%)
168=>24 (14%)
176=>24 (13%)
180=>24 (13%)
192=>24 (12%)
208=>28 (13%)
216=>33 (15%)
224=>28 (12%)
240=>24 (10%)
252=>32 (12%)

256 tem apenas 44 (17%). Não é a melhor, mas simplifica bastante o teste: basta conferir o último byte.

Ampliando a busca para 2 bytes, aparecem alguns valores supreendentes cujos resíduos quadráticos cobrem apenas 2% das possibilidades.

Por exemplo, o mais próximo de 65.536 é 65.520=>1.344 (2%).

Se, por outro lado, contarmos os resíduos quadráticos das bases impares, encontramos 50% quando a base é um número primo, o que constitui uma forma diferente de identificar primos.

Sobre Bases e Quadrados Perfeitos

O teste de divisibilidade por 3 ou 9 consiste em somar os dígitos e verificar se o resultado é múltiplo de 3 ou 9.

Por exemplo, 25 não é divisível por 3 ou 9, porque 2+5=7. Mas 3627 é, porque 3+6+2+7=18.

O interessante deste teste é que ele pode ser generalizado para outras bases. Ele funciona em base 10, porque 9 é 10-1 (e 3 divide 9). Em base 3, ele seria o teste do 2; em base 8, seria o teste do 7.

Vejamos os seguintes múltiplos de 7 em base 8:

• 14 => 16₈
• 21 => 25₈
• 28 => 34₈
• 49 => 61₈

Outro jogo interessante com bases é que o quadrado de n tem sempre a forma [n-1,1] na base n+1:

1*1=1 (base 2)
2*2=11 (base 3)
3*3=21 (base 4)
4*4=31 (base 5)
5*5=41 (base 6)
6*6=51 (base 7)
7*7=61 (base 8)
8*8=71 (base 9)
9*9=81 (base 10)
10*10=91 (base 11)
11*11=A1 (base 12)
12*12=B1 (base 13)
13*13=C1 (base 14)
14*14=D1 (base 15)
15*15=E1 (base 16)
16*16=F1 (base 17)
17*17=G1 (base 18)
18*18=H1 (base 19)
19*19=I1 (base 20)
20*20=J1 (base 21)

Não chega a surpreender, dado que n*n=(n+1)(n-1)+1.