This study is a contribution to the ongoing research on preservice teachers’ learning and understanding of introductory number theory. The focus of this article is on fundamental concept of factor, divisor, and multiple; the meaning students construct of these three concepts; and students’ links among the three notions as well as their connections to other concepts of elementary number theory, such as prime factors, prime decomposition and divisibility. Nineteen clinical interviews in which students in a course for preservice teachers were asked to explain and exemplify the concepts and to apply their understanding in several problem situations were analysed focusing on the connections students made among the concepts. An examination of students’ responses showed that the meaning they assign to the concepts is often different from the meaning assigned by mathematicians in the context of number theory, and that their links among the concepts are often weak or incomplete.