In this paper we propose a modification of extended Euclid’s algorithms with aim to reduce the number of iteration steps when solving modular equations. Obtained result is used to solve the system of linear modular equations in one variable (Chinese Remainder Theorem). The proposed modification is convenient for parallel implementation.