Number Theory

Course Outlines

Divisibility theory

Division algorithm

Euclidean algorithm

Diophantine equation

Primes and their distributions

Unique factorization theorem

Goldbach's conjecture

Theory of congruence

Properties of congruence

Divisibility tests

Linear congruence

Fermat's little theorem and Wilson's theorem

Euler's theorem.

· Well ordering principle: Every non-empty set S of non-negative integers contains a least element, i.e., there is some integer a in S such that a £ b for all a, b Î S.

· Archimedean property: If a and b are any positive integers, then there exists a positive integer n such that na ³ b.

· Principle of finite induction: Let S be a set of positive integers with the properties
(i) 1 belonging to S and (ii) whenever the integer k is S, then the next integer K + 1 must also be in S, and set S is the set of all positive integers.

· Division Algorithm: Given integers a and b, with b > 0, there exist unique integers q and r satisfying a = qb + r 0 £ r < b.

The integers q and r are called, respectively the quotient and remainder in the division of a by b.

· Greatest common divisor: Let a and b be given integers, with at least one of them different from zero. The greatest common divisor of a and b denoted by gcd (a, b) is a positive integer d satisfying

i) d|a and d|b

ii) if c|a and c|b, then c £ d.

· The Diophantine equation: The equation of the form ax + by = c where a, b, c are integers and a, b not both zero.

The Diophantine equation ax + by = c admits a solution iff d|c where d = gcd
(a, b).

· Prime number: An integer p > 1 is called a prime number, or simply a prime if its only positive divisors 1 and p. An integer greater than 1 which is not prime is termed composite.

· Twin prime: The pair of successive odd integers p and p + 2 which are both primes are called twin primes. For example 3 and 5, 5 and 7, 11 and 13 etc are twin primes.

· Congruence modulo n: Let n be a fixed positive integer. Two integers a and b are said to be congruent modulo n, symbolized by a º b (mod n)

If n divides the difference a – b; that is provided that a – b = Kn for some integer k.

· Fermat's Little theorem: If p is a prime and p a, then a^{p –1}º 1 (mod p).

· Fundamental theorem of arithmetic: Every positive integer n > 1 can be expressed as a product of primes, this representation is unique, apart form the order in which the factors occur.

· Relatively prime: Two integers a and b, not both of which are zero are said to be relatively prime whenever gcd (a, b) = 1.

· Wilson's theorem: If p is a prime integer than (p – 1) ! º – 1 (mod p).

Some Solved Problems

Q.1. Use Euclidean Algorithm to express gcd (4076, 1024) as a linear combination of 4076 and 1024. [T.U. 2075]

Soln: To find gcd (4076, 1024):

By the successive application of division algorithm, we have

4076 = 3 ´ 1024 + 1004

1024 = 1 ´ 1004 + 20

1004 = 50 ´ 20 + 4

20 = 5 ´ 4 + 0

Since the last non-zero remainder is 4, gcd (4076, 1025) = 4.

To express gcd (4076, 1024) as linear combination of 4076 and 1025: