Loading [MathJax]/jax/element/mml/optable/BasicLatin.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

1.1: Divisibility and Primality

( \newcommand{\kernel}{\mathrm{null}\,}\)

A central concept in number theory is divisibility.

Consider the integer Z={...,2,1,0,1,2,...}. For a,bZ, we say that a divides b if az=b for some zZ. If a divides b, we write ab, and we may say that a is a divisor of b, or that b is a multiple of a, or that b is a divisible of a. If a does not divide b, then we write ab.

We first state some simple facts about divisibility:

Theorem 1.1.1

For all a,b,cZ, we have

  1. aa, 1a, and a0;
  2. a0 if and only if a=0;
  3. ab if and only if ab if and only if ab;
  4. ab and ac implies a(b+c);
  5. ab and bc implies ac.

Proof

These properties can be easily derived from the definition of divisibility, using elementary algebraic properties of the integers. For example, aa because we can write a1=a; 1a because we can write 1a=a; a0 because we can write a0=0. We leave it as an easy exercise for the reader to verify the remaining properties.

We make a simple observation: if ab and b0, then 1|a||b|. Indeed, if az=b0 for some integer z, then a0 and z0; it follows that |a|1, |z|1, and so

|a||a||z|=|b|.

Theorem 1.1.2

For all a,bZ, we have ab and ba if and only if a=±b. In particular, for every aZ, we have a1 if and only if a=±1.

Proof

Clearly, if a=±b, then ab and ba. So let us assume that ab and ba, and prove that a=±b. If either of a or b are zero, then the other must be zero as well. So assume that neither is zero. By the above observation, ab implies |a||b|, and ba implies |b||a|; Thus, |a|=|b|, and so a=±b. That proves the first statements. The second statement follows from the first by setting b:=1, and noting that 1a.

The product of any two non-zero integers is again non-zero. This implies the usual cancellation law: if a, b, and c are integers such that a0 and ab=ac, then we must have b=c; indeed, ab=ac implies a(bc)=0, and so a0 implies bc=0, and hence b=c.

Primes and Composites

Let n be a positive integer. Trivially, 1 and n divide n. If n>1 and no other positive integers besides 1 and n divide n, then we say n is prime. If n>1 but n is not prime, then we say that n is composite. The number 1 is not considered to be either prime or composite. Evidently, n is composite if and only if n=ab for some integers a,b with 1<a<n and 1<b<n. The first few primes are

2, 3, 5, 7, 11, 13, 17, ....

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.

A basic fact is that every non-zero integer can be expressed as a signed product of primes in an essentially unique way. More precisely:

Theorem 1.1.3: fundamental theorem of arithmetic

Every non-zero integer n can be expressed as

n=±p1e1prer ,

where p1pr are distinct primes and e1er are positive integers. Moreover, this expression is unique, up to a reordering of the primes.

Note

Note that if n=±1 in the above theorem, then r=0, and the product of zero terms is interpreted (as usual) as 1.

The theorem intuitively says that the primes act as the “building blocks” out of which all non-zero integers can be formed by multiplication (and negation). The reader may be so familiar with this fact that he may feel it is somehow “self evident,” requiring no proof; however, this feeling is simply a delusion, and most of the rest of this section and the next are devoted to developing a proof of this theorem. We shall give a quite leisurely proof, introducing a number of other very important tools and concepts along the way that will be useful later.

proof

To prove Theorem 1.3, we may clearly assume that n is positive, since otherwise, we may multiply n by −1 and reduce to the case where n is positive.

The proof of the existence part of Theorem 1.3 is easy. This amounts to showing that every positive integer n can be expressed as a product (possibly empty) of primes. We may prove this by induction on n. If n=1, the statement is true, as n is the product of zero primes. Now let n>1, and assume that every positive integer smaller than n can be expressed as a product of primes. If n is a prime, then the statement is true, as n is the product of one prime. Assume, then, that n is composite, so that there exist a,bZ with 1<a<n, 1<b<n, and n=ab. By the induction hypothesis, both a and b can be expressed as a product of primes, and so the same holds for n.

The uniqueness part of Theorem 1.3 is the hard part(Check the section 2). An essential ingredient in this proof is the following:

Theorem 1.1.4: Division with remainder property

Let a,bZ with b>0. Then there exist unique q,eZ such that a=bq+r and 0r<b.

Proof

Consider the set S of non-negative integers of the form abt with tZ. This set is clearly non-empty; indeed, if a0, set t:=0, and if a<0, set t:=a. Since every non-empty set of non-negative integers contains a minimum, we define r to be the smallest element of S. By definition, r is of the form r=abq for some qZ, and r0. Also, we must have r<b, since otherwise, rb would be an element of S smaller than r, contradicting the minimality of r; indeed, if rb, then we would have 0rb=ab(q+1).

That proves the existence of r and q. For uniqueness, suppose that a=bq+r and a=bq+r, where 0r<b and 0r<b. Then subtracting these two equations and rearranging terms, we obtain

rr=b(qq).

Thus, rr is a multiple of b; however, 0leqr<b and 0r<b implies |rr|<b; therefore, the only possibility is rr=0. Moreover, 0=b(qq) and b0 implies qq=0.

Theorem 1.1.4 can be visualized as follows:

clipboard_ee6c52daf271dc61069a884c0b9e51902.png

Starting with a, we subtract (or add, if a is negative) the value b until we end up with a number in the interval [0,b).

Floor and Ceilings

Let us briefly recall the usual floor and ceiling functions, denote . and ., respectively. These are functions from R (the real numbers) to Z. For xR, x is the greatest integer mx; equivalently, x is the unique integer m such that mx<m+1, or put another way, such that x=m+ε for some ε[0,1). Also, x is the smallest integer mx; equivalently, x is the unique integer m such that m1<xm, or put another way, such that x=mε for some ε[0,1).

The mod operator

Now let a,bZ with b>0. If q and r are the unique integers from Theorem 1.4 that satisfy a=bq+r and 0r<b, we define

(amod

that is, a \bmod b denotes the remainder in dividing a by b. It is clear that b \mid a if and only if a mod b =0. Dividing both sides of the equation a=bq+r by b, we obtain a/b=q+r/b. Since q \in \mathbb{Z} and r/b \in [0,1), we see that q= \lfloor a/b \rfloor. Thus,

(a \bmod b)=a-b \lfloor a/b \rfloor .

One can use this equation to extend the definition of a \bmod b to all integers a and b, with b \neq 0; that is, for b<0, we simply define a \bmod b to be a-b \lfloor a/b \rfloor.

Theorem \PageIndex{4} may be generalized so that when dividing an integer a by a positive integer b, the remainder is placed in an interval other than [0,b). Let x be any real number, and consider the interval [x,x+b). As the reader may easily verify, this interval contains precisely b integers, namely, \lceil x \rceil , \dotsc , \lceil x \rceil+b-1. Applying Theorem 1.4 with a - \lceil x \rceil in place of a, we obtain:

Theorem \PageIndex{5}

Let a,b \in \mathbb{Z} with b>0, and let x \in \mathbb{R}. Then there exist unique q,r \in \mathbb{Z} such that a=bq+r and r \in [x,x+b).

EXERCISE 1.1 Let a,b,d \in \mathbb{Z} with d \neq 0 . Show that a \mid b if and only if da \mid db.

EXERCISE 1.2 Let n be a composite integer. Show that there exists a prime p dividing n, with p \leq n^{1/2}.

EXERCISE 1.3 Let m be a positive integer. Show that for every real number x \geq 1, the number of multiples of m in the interval [1,x] is \lfloor x/m \rfloor; in particular, for every interger n \geq 1, the number of multiples of m among 1\, \dotsc , n is \lfloor n/m \rfloor .

EXERCISE 1.4 Let x \in \mathbb{R}. Show that 2 \lfloor x \rfloor \leq \lfloor 2x \rfloor \leq 2 \lfloor x \rfloor +1.

EXERCISE 1.5 Let x \in \mathbb{R} and n \in \mathbb{Z} with n>0. Show that \lfloor \lfloor x \rfloor /n \rfloor = \lfloor x/n \rfloor; in particular, \lfloor \lfloor a/b \rfloor /c \rfloor = \lfloor a/bc \rfloor for all positive integers a,b,c.

EXERCISE 1.6 Let a,b \in \mathbb{Z} with b<0. Show that (a \bmod b) \in (b,0].

EXERCISE 1.7 Show that Theorem 1.5 also holds for the interval (x,x+b]. Does it hold in general for the intervals [x,x+b] or (x,x+b)?


1.1: Divisibility and Primality is shared under a CC BY-NC-ND license and was authored, remixed, and/or curated by LibreTexts.

Support Center

How can we help?