Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

C: Elementary Number Theory

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

Here we review some basic number theoretic definitions and results. For the most part, we will just state the results. For a more detailed treatment, the student is referred references ,, or given in the bibliography. Unless otherwise stated in this appendix, all lower case letters, a, b, c, etc. will be integers. Recall that we use N to denote the set of natural numbers (also known as the positive integers) and we use Z to denote the set of all integers, i.e., N={1,2,3,} and Z={,3,2,1,0,1,2,3,}.

Definition C.1:

Let a,bZ. We say b divides a and we write b | a if there is an element cZ such that a=bc. We write b  a if b does not divide a.

If b | a we also sometimes say that b is a factor of a or that a is a multiple of b. To tell if b divides a where b0, we simply divide a by b and see if the remainder is 0 or not. More generally, we have the following fundamental result.

Lemma C.1 (The Division Algorithm)

For any integers a and b with b0 there exists unique integers q and r such that a=bq+r,0r<|b|.

Definition C.2:

The number r in the above Lemma is denoted by amodb.

For example we have

17mod5=2 since \quad 17=35+2 \ and \ 02<5 and (17)mod5=3 since \quad 17=(4)5+3 \ and \ 03<5.

Definition C.3:

An integer p is said to be prime if p2 and the only positive factors of p are p and 1.

Definition C.4:

Let a and b be integers, at least one of which is non-zero. The greatest common divisor of a and b is the greatest positive integer, gcd(a,b), that divides both a and b. We define gcd(0,0)=0.

Definition C.5:

If a and b are non-zero integers, the least common multiple of a and b is the smallest positive integer, lcm(a,b), that is a multiple of both a and b. If a=0 or b=0, we define lcm(a,b)=0.

An important property of primes is given by the following lemma.

Lemma C.2

If p is prime and p|ab then p|a or p|b.

Perhaps the most fundamental result concerning integers is the following theorem, which is sometimes called The Fundamental Theorem of Arithmetic.

Theorem C.3

If n2 is an integer, then there exists a unique list of primes p1,p2,,pk such that the following two conditions hold:

  1. p1p2pk,
  2. n=p1p2pk

For example, if n=72 the unique list of primes is 2, 2, 2, 3, 3.

Now fix a positive integer n. Recall that Zn={0,1,,n1} and that multiplication and addition in Zn are defined by

a+b= remainder when the ordinary sum of a and b is divided by n, and

ab= remainder when the ordinary product of a and b is divided by n.

To facilitate the proof that these two binary operations are associative, we temporarily denote addition in Zn by and multiplication in Zn by . This way we can use + and for ordinary addition and multiplication in Z. Thus we have ab=(a+b)modnab=(ab)modn

Theorem C.4

Let n be a positive integer. Define f:ZZn by the rule f(a)=amodn. Then

f(a+b)=f(a)f(b)

and

f(ab)=f(a)f(b).

Proof Let r1=f(a) and r2=f(b). This implies that a=nq1+r1,0r1<n and b=nq2+r2,0r2<n Hence a+b=nq1+r1+nq2+r2=n(q1+q2)+r1+r2 Now f(a)f(b)=r1r2=r where r1+r2=qn+r,0r<n Hence a+b=n(q1+q2+q)+r,0r<n and it follows that f(a+b)=(a+b)modn=r, and we conclude that f(a+b)=r=f(a)f(b). This proves (C.1). The proof of (C.2) is similar and left to the interested reader.

Corollary C.5

The binary operations and on Zn are associative.

Proof Using the notation in the theorem, we have for a,b,cZn: f(a)=a, f(b)=b and f(c)=c. Hence (ab)b=(f(a)f(b))f(c)=f(a+b)f(b)=f((a+b)+c)=f(a+(b+c))=f(a)f(b+c)=f(a)(f(b)f(c))=a(bc) This proves that is associative on Zn. The proof for is similar and left to the interested reader.


This page titled C: Elementary Number Theory is shared under a not declared license and was authored, remixed, and/or curated by W. Edwin Clark via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?