Predicate re-write in where clause
The easiest way would be to add a computed column to the table with your mod calculation, and then create an index or add it to an existing index.

For example:

-- Test table and values
CREATE TABLE #Test (col integer PRIMARY KEY);

INSERT #Test (col)
VALUES (1), (2), (3), (4), (5);

-- Original query (scan)
SELECT T.col 
FROM #Test AS T
WHERE col % 5 = 4;

-- Add computed column (no need for persisted)
ALTER TABLE #Test
ADD col_mod5 AS col % 5;

-- Index computed column
CREATE INDEX i
ON #Test (col_mod5)
INCLUDE (col);

-- Index seek
SELECT T.col 
FROM #Test AS T
WHERE col % 5 = 4;

-- Tidy up
DROP TABLE #Test;




Another alternative is to create an indexed view selecting what you need from the table, plus a column with the mod calculation, and refer to that in your queries. You do this by declaring the view as schemabinding and then creating a clustered index on it as if it were a table.

If you are using Enterprise Edition, you may not need to change your query to use the view. Otherwise, you will need to reference the view explicitly and use the NOEXPAND hint. The indexed computed column is the lighter weight solution.