Number Theory

Number theory is the branch of mathematics which deals with the properties of integers.

Properties of integers:

For all a, b ∈ Z, we say that a divides b (denoted by a/b)  iff b=ka for some integer k.

Example:

Is 4/20? Yes, since 4 x 5=20

Results:

(i) If a/b, then a/kb, ka/kb.

(ii) If ka/kb and k≠0, then a/b.

(iii) If a/b and b/c, then a/c.

Example: 4/12 and 12/24. Is it true that 4/24? Yes, since 4 x 6 = 24

(iv) If a/b and a/c , then a/ (mb+nc).

Example: 7/21 and 7/35. Is it true that 7/56? Yes , since 7 x 8 = 56

(v) If a/b and b/a , then a=±b

(vi) If a/b, a,b > 0, then a ≥ b.

(vii) For any choice of a and b, there exists a unique q, r, 0 ≤ r < a  such that b = qa + r, and r=0 ⇔ a/b.

The fundamental theorem of arithmetic:

Every positive integer can be written in a unique way as the product of prime numbers.

Example:  6765 = 5 x 1353 = 5 x 3 x 451 = 5 x 3 x 11 x 41.

Bezout’s Identity:

 Given integers a, b, then GCD(a, b) = g iff there exist  integers x and  y such that ax+by = g. In general GCD(a_1,a₂, ……, a_n)=g iff there exist integers x_1, x₂, ……x_n such that a₁x₁+a₂x₂+……+a_nx_n=g.

For any two integers a, b, the greatest common divisor is the largest number that is a divisor of both a and b.

Example: gcd( 24, 28) = 4 here 4/ 24 and 4/ 28.

Two numbers a and b are relatively prime if gcd( a, b) = 1

Steps to find out gcd:

(i) List the prime factors of each number.

(ii) Then list all prime factors that are common to each number.

(iii) The product of these common prime factors is the greatest common divisor.

Example: 25, 35

25 = 5 x 5

35 = 5 x 7

gcd = 5