Teorema Chinês dos Restos (com SQL)

Lendo vários textos sobre o Teorema Chinês dos Restos, cheguei à conclusão que todas as explicações estão de ponta-cabeça. Então, resolvi atacar de uma maneira que eu pudesse entender.

Se pegarmos dois números p e q, primos entre si, sabemos que eles só vão se encontrar em p*q. Por exemplo, 5 e 8 só são ao mesmo tempo fatores de 40; 3, 4, e 5 só são ao mesmo tempo fatores de 3*4*5=60

Se eu montar uma tabela dos restos de cada número até 6 em relação a 2 e 3, terei algo assim:

N	mod 2	mod 3
0	0	0
1	1	1
2	0	2
3	1	0
4	0	1
5	1	2
6	0	0

As combinações dos restos de 2 e 3 são a chave primária para o N (exceto quando N for 0 ou 6).

Já que misturei Álgebra Relacional no assunto, vamos escrever um pouco de SQL para resolver problemas com 3, 4, e 5 (60). A minha solução para o problema com x mod 2=2, x mod 4=2 e x mod 5=1 é:

select * from (
  select rownum, 
         mod(rownum,3) as mod3, 
         mod(rownum,4) as mod4, 
         mod(rownum,5) as mod5
  from all_tables where rownum<60
) where mod3=2 and mod4=2 and mod5=1
                                  

O resultado é 26. Se eu brincar com as cláusulas uma a uma, descubro que com mod3=2 surge uma progressão aritmética que começa em 2 (lembre que x = 2 mod 3) com diferença de 3: 2, 5, 8, 11, etc. Com mod4=2 tenho uma progressão aritmética que começa em 2 e que pula de 4 em 4: 2, 6, 10, 14, etc. Com mod5=1 tenho uma progressão aritmética que começa em 1 e pula de 5 em 5: 1, 6, 11, 16, 21, 26, etc.

A brincadeira com SQL é boa para entender o problema, mas não é nada prática para a vida real, uma vez que o objetivo é trabalhar com números realmente grandes a partir de uma lista de números menores. Desenrolar todas as combinações de, digamos, os primeiros 100 primos exigiria uma quantidade absurda de disco ou de memória.

Então, meu próximo passo é entender os algoritmos usados para resolver o problema sem enumerar todas as combinações