La criba de Sundaram es una tabla de los números naturales impares compuestos compuesto por progresiones aritméticas organizadas en las columnas. La criba se basa en el principio de que, al determinar el conjunto de los números compuestos impares, se puede deducir el conjunto de los números primos. La n-ésima columna tiene por primer término (2n + 1)² y por diferencia entre términos consecutivos d = 4n + 2. Cualquier número impar, distinto de 1, que no se encuentre en la tabla, es primo.

Considérese un número compuesto impar de la forma n = (2p + 1)(2q + 1), donde p y q son números impares, no necesariamente primos, y q = p + k para algún k natural. Entonces,

con lo que n se encontraría en la p-ésima columna y la k-ésima fila

Al hacer variar p y k a lo largo de se obtiene el conjunto de los números que son producto de dos impares que se encuentran en la tabla.

Sundaram era un matemático de la India. La criba que publicó en 1934 era algo diferente al modelo aquí presentado.

Una forma cuadrática asociada

La forma cuadrática tiene por lo menos un par (k, j) de soluciones en números naturales, para cada valor de p compuesto. Cuando p es compuesto, k puede tomar cualquier valor natural y también puede ser nulo, si el número p es un cuadrado. El valor de j siempre es distinto de cero para p compuesto. Una solución (k, j) única, con j = 0, indica que p es un número primo en .

Si desarrollamos el cuadrado, el resultado es análogo a la expresión [1]: .

Las soluciones de la forma cuadrática no están acotadas todavía, por lo que esta fórmula no puede utilizarse para determinar la primalidad de un número. La criba constituye un método casi de "fuerza bruta", también impracticable para números muy grandes.

Una relación de equivalencia

Si reordenamos la criba de Sundaram y la escribimos de una manera diferente, podemos dividir a los números compuestos en clases disjuntas:

El criterio a seguir consiste en agrupar los números que tienen un mismo divisor mínimo. Comenzamos por el 9, que es un cuadrado y seguimos con todos los múltiplos de 3 que no contengan factores pares. Seguimos con 25, que también es un cuadrado, y agrupamos todos los múltiplos de 5 que no tengan factores menores que 5. Y así sucesivamente (Obsérvese que 81 está, ahora, en la clase que comenzamos con 9). Todas estas clases de números naturales compuestos quedan agrupadas en subconjuntos disjuntos dos a dos.

Ahora ampliamos algo más el contenido de la criba. Colocamos al mínimo divisor como precedente de cada cuadrado y lo aceptamos como representante de la clase (es el divisor mínimo común de la clase). Además, agregamos el 2 y todos los pares como una clase adicional y tenemos, entonces, a todos los números naturales -excepto el 1- divididos en clases disjuntas. Esto indica que se ha realizado un cociente de por una relación de equivalencia. Los representantes de esas clases son los números primos.