The presented paper is devoted to the new teaching model of congruences of computer science students within the subject of discrete mathematics at universities. The main goal was to create a new model of teaching congruences on the basis of their connection with Diophantine equations and subsequently to verify the effectiveness and efficiency of the proposed model experimentally. The teaching of congruences was realized in two phases: acquisition of procedural knowledge and use of Diophantine equations to obtain conceptual knowledge of congruences. Experiments confirmed that conceptual understanding of congruences is positively related to increasing the procedural fluidity of congruence resolution. Research also demonstrated the suitability of using Diophantine equations to link congruences and equations. Among other things, the presented research has confirmed the justification of teaching mathematics in computer-oriented study programs.