In this work there is presented the methodology of designing residue generators and arithmetic units for modern FPGA matrices. The proposed algorithms take advantage of dedicated logic for high-speed arithmetic present in Xilinx Spartan-2 and Virtex FPGA families. Comparing to implementations published so far, which are based mainly on Look Up Table solutions, new method results in better area-time efficiency, especially for medium and large moduli. The proposed units can be used in cryptography, fault tolerant computing and DSP algorithms.