A central concept in number theory is divisibility.<\/p>\n
Consider the integers<\/a> Z = {. . . ,\u22122,\u22121, 0, 1, 2, . . .}. For\u00a0a<\/i>,\u00a0b\u00a0<\/i>\u2208 Z, we say that\u00a0a\u00a0<\/i>divides\u00a0b\u00a0<\/i>if\u00a0az\u00a0<\/i>=\u00a0b\u00a0<\/i>for some\u00a0z\u00a0<\/i>\u2208 Z. If\u00a0a\u00a0<\/i>divides\u00a0b<\/i>, we write\u00a0a\u00a0<\/i>|\u00a0b<\/i>, and we may say that\u00a0a\u00a0<\/i>is a divisor of\u00a0b<\/i>, or that\u00a0b\u00a0<\/i>is a multiple of\u00a0a<\/i>, or that\u00a0b\u00a0<\/i>is divisible by\u00a0a<\/i>. If\u00a0a\u00a0<\/i>does not divide\u00a0b<\/i>, then we write\u00a0a\u00a0<\/i>–\u00a0b<\/i>.<\/p>\n We first state some simple facts about divisibility<\/a>:<\/p>\n Theorem 1.1.<\/strong> For all\u00a0a<\/i>,\u00a0b<\/i>,\u00a0c\u00a0<\/i>\u2208 Z, we have<\/p>\n (i)\u00a0a\u00a0<\/i>|\u00a0a<\/i>, 1 |\u00a0a<\/i>, and\u00a0a\u00a0<\/i>| 0;<\/p>\n (ii) 0 |\u00a0a\u00a0<\/i>if and only if\u00a0a\u00a0<\/i>= 0;<\/p>\n (iii)\u00a0a\u00a0<\/i>|\u00a0b\u00a0<\/i>if and only if \u2212a\u00a0<\/i>|\u00a0b\u00a0<\/i>if and only if\u00a0a\u00a0<\/i>| \u2212b<\/i>;<\/p>\n (iv)\u00a0a\u00a0<\/i>|\u00a0b\u00a0<\/i>and\u00a0a\u00a0<\/i>|\u00a0c\u00a0<\/i>implies\u00a0a\u00a0<\/i>| (b\u00a0<\/i>+\u00a0c<\/i>);<\/p>\n (v)\u00a0a\u00a0<\/i>|\u00a0b\u00a0<\/i>and\u00a0b\u00a0<\/i>|\u00a0c\u00a0<\/i>implies\u00a0a\u00a0<\/i>|\u00a0c<\/i>.<\/p>\n Proof. These properties can be easily derived from the definition of divisibility, using elementary algebraic properties<\/a> of the integers. For example,\u00a0a\u00a0<\/i>|\u00a0a\u00a0<\/i>because we can write\u00a0a\u00a0<\/i>\u00b7 1 =\u00a0a<\/i>; 1 |\u00a0a\u00a0<\/i>because we can write 1 \u00b7\u00a0a\u00a0<\/i>=\u00a0a<\/i>;\u00a0a\u00a0<\/i>| 0 because we can write\u00a0a\u00a0<\/i>\u00b70 = 0. We leave it as an easy exercise for the reader to verify the remaining properties. 2<\/p>\n We make a simple observation: if\u00a0a\u00a0<\/i>|\u00a0b\u00a0<\/i>and\u00a0b\u00a0<\/i>6= 0, then 1 \u2264 |a<\/i>| \u2264 |b<\/i>|. Indeed, if\u00a0az\u00a0<\/i>=\u00a0b\u00a0<\/i>6= 0 for some integer\u00a0z<\/i>, then\u00a0a\u00a0<\/i>6= 0 and\u00a0z\u00a0<\/i>6= 0; it follows that |a<\/i>| \u2265 1, |z<\/i>| \u2265 1, and so |a<\/i>| \u2264 |a<\/i>||z<\/i>| = |b<\/i>|.<\/p>\n Theorem 1.2.<\/strong> For all\u00a0a<\/i>,\u00a0b\u00a0<\/i>\u2208 Z, we have\u00a0a\u00a0<\/i>|\u00a0b\u00a0<\/i>and\u00a0b\u00a0<\/i>|\u00a0a\u00a0<\/i>if and only if\u00a0a\u00a0<\/i>= \u00b1b<\/i>. In particular, for every\u00a0a\u00a0<\/i>\u2208 Z, we have\u00a0a\u00a0<\/i>| 1 if and only if\u00a0a\u00a0<\/i>= \u00b11.<\/p>\n Proof. Clearly, if\u00a0a\u00a0<\/i>= \u00b1b<\/i>, then\u00a0a\u00a0<\/i>|\u00a0b\u00a0<\/i>and\u00a0b\u00a0<\/i>|\u00a0a<\/i>. So let us assume that\u00a0a\u00a0<\/i>|\u00a0b\u00a0<\/i>and\u00a0b\u00a0<\/i>|\u00a0a<\/i>, and prove that\u00a0a\u00a0<\/i>= \u00b1b<\/i>. If either of\u00a0a\u00a0<\/i>or\u00a0b\u00a0<\/i>are zero, then the other must be zero as well. So assume that neither is zero. By the above observation,\u00a0a\u00a0<\/i>|\u00a0b\u00a0<\/i>implies |a<\/i>| \u2264 |b<\/i>|, and\u00a0b\u00a0<\/i>|\u00a0a\u00a0<\/i>implies |b<\/i>| \u2264 |a<\/i>|; thus, |a<\/i>| = |b<\/i>|, and so\u00a0a\u00a0<\/i>= \u00b1b<\/i>. That proves the first statement. The second statement follows from the first by setting\u00a0b\u00a0<\/i>:= 1, and noting that 1 |\u00a0a<\/i>. 2<\/p>\n The product of any two non-zero integers is again non-zero. This implies the usual cancellation law: if\u00a0a<\/i>,\u00a0b<\/i>, and\u00a0c\u00a0<\/i>are integers such that\u00a0a\u00a0<\/i>6= 0 and\u00a0ab\u00a0<\/i>=\u00a0ac<\/i>, then we must have\u00a0b\u00a0<\/i>=\u00a0c<\/i>; indeed,\u00a0ab\u00a0<\/i>=\u00a0ac\u00a0<\/i>implies\u00a0a<\/i>(b\u00a0<\/i>\u2212\u00a0c<\/i>) = 0, and so\u00a0a\u00a0<\/i>6= 0 implies\u00a0b\u00a0<\/i>\u2212\u00a0c\u00a0<\/i>= 0, and hence\u00a0b\u00a0<\/i>=\u00a0c<\/i>.<\/p>\n Primes and composites.<\/strong> Let\u00a0n\u00a0<\/i>be a positive integer. Trivially, 1 and\u00a0n\u00a0<\/i>divide\u00a0n<\/i>. If\u00a0n >\u00a0<\/i>1 and no other positive integers besides 1 and\u00a0n\u00a0<\/i>divide\u00a0n<\/i>, then we say\u00a0n\u00a0<\/i>is prime. If\u00a0n >\u00a0<\/i>1 but\u00a0n\u00a0<\/i>is not prime<\/a>, then we say that\u00a0n\u00a0<\/i>is composite<\/a>. The number 1 is not considered to be either prime or composite. Evidently,\u00a0n\u00a0<\/i>is composite if and only if\u00a0n\u00a0<\/i>=\u00a0ab\u00a0<\/i>for some integers\u00a0a<\/i>,\u00a0b\u00a0<\/i>with 1\u00a0< a < n\u00a0<\/i>and 1\u00a0< b < n<\/i>. The first few primes are<\/p>\n 2, 3, 5, 7, 11, 13, 17, . . . .<\/p>\n While it is possible to extend the definition of prime and composite to negative integers, we shall not do so in this text: whenever we speak of a prime or composite number, we mean a positive integer.<\/p>\n","protected":false},"excerpt":{"rendered":"