Among all natural numbers we can distinguish prime and composite numbers.
A number is composite if it is a product of two smaller, natural numbers. For example, \(6 = 2\times3\). Otherwise, and if the number is not equal to 1, it is called prime. The number 1 is neither prime nor composite.
The Fundamental Theorem of Arithmetic says that any natural number greater than 1 can be uniquely expressed as a product of prime numbers in non-decreasing order. For example: \[630=2\times3\times3\times5\times7=2\times3^2\times5\times7.\]
Modulo operation: Given any two natural numbers \(a\) and \(b\), called the dividend and the divisor respectively, we can divide \(a\) by \(b\) with the remainder. That is to find such non-negative integer numbers \(c\) and \(d\) (\(d<b\)), called the quotient and the remainder respectively, that \(a=c\times b+d\). For example \(41=2\times15+11\) is the division of 41 by 15 with the remainder 11, and \(5=0\times7+5\) is the division of 5 by 7 with the remainder 5.
If \(a\) is divided by \(b\) with zero remainder (without a remainder) we say that "\(a\) is divisible by \(b\)"\(\;\)or "\(b\) divides \(a\)". From the definition of modulo operation for \(a\) the property to be divisible by \(b\) is equivalent to the existence of non-negative integer \(c\) such that \(a=c\times b\). We denote it by \(b|a\) for "\(b\) divides \(a\)". For example \(7 \mid 105\) and \(9|111111111\) because \(105=15\times7\) and \(111111111=12345679\times9\).
We immediately deduce from the Fundamental Theorem of Arithmetic that if a product of two natural numbers is divisible by a prime number, then one of these numbers is divisible by this prime number.