Top

# Elementary Number Theory

Elementary number theory is a theory of pure mathematics which is related to study of number systems (mainly Integers).

Every system of numbers has its limitations and this motivates to extend some more number systems by including some more numbers to it.

The limitation of natural numbers led to the discovery of integers and the limitation of integers led to the development of the set of rational numbers and so on.

Some Important Definitions, Results and Theorems of Elementary Number Theory are as follows:

Divisibility in Integers: If a and b are any two integers such that a not equal to zero, we say that a divides b, denoted by $\frac{a}{b}$, if b = ac, for some integer c.

Greatest Common Divisor: The greatest common divisor (g.c.d) of two integers a and b is defined as a positive integer c such that
1.    $\frac{c}{a}$ and $\frac{c}{b}$
2.    If d is any integer such that $\frac{d}{a}$ and $\frac{d}{b}$, then $\frac{d}{c}$.
The g.c.d of two integers a and b is denoted by (a, b).

Two integers a and b are said to be relatively prime if the g.c.d of a and b is 1. i.e., gcd (a, b) = 1.

Prime Numbers and Composite Numbers: An integer p > 1 is called a prime number (or Prime) if its only divisor are $\pm$1, $\pm$p. An integer n > 1 which is not prime is called a composite number (or composite).

Division Algorithm: If a and b are any two integers and a not equal to zero, then there exist unique integers q and r such that b = a $\times$ q + r, 0 $\leq$ r < mod (a).

Euclid’s Lemma: Let p be a prime number such that p / ab (a, b belongs to integers). Then $\frac{p}{a}$ or $\frac{p}{b}$.
Its corollary is, let p be a prime number such that $\frac{p}{(a_1, a_2,… .., a_n) (a_i\ represents\ integers)}$. Then $\frac{p}{a}$, for some i, 1 $\leq$ i $\leq$ n.

Unique Factorization Theorem: Every positive integer is either 1 or it can be expressed uniquely as a product of prime numbers.

Linear Diophantine Equation: An equation of the form ax + by = c, where a, b, c are integers such that a and b are not both zero, is called a linear Diophantine equation, due to a mathematician Diophantine. It can be shown that the linear Diophantine equation ax + by = c has a solution in the set of integers if $\frac{d}{c}$, where d = (a, b).

 Related Calculators Number Rounding 5 Number Summary Calculator Adding Binary Numbers Calculator Adding Complex Numbers Calculator

## Solving Elementary Number Theory

### Solved Examples

Question 1: Find a solution of 243x + 189y = 27 in integers.
Solution:

First we will find greatest common divisor of 243 and 189 by division algorithm, which can be written as 243 = 189 $\times$ 1 + 54 .......(i)
189 = 54 $\times$ 3 + 27 ……….(ii)
54 = 27 $\times$ 2.
Therefore, (243, 189) = 27.
From (ii) 27 = 189 – 54 $\times$ 3
= 189 – (243 - 189) $\times$ 3 by (i)
Therefore, (-3) $\times$ 243 + (4) $\times$ 189 = 27.
Hence x = -3, and y = 4 is the required solution.

Question 2: If (a, b) = 1, then prove that (a + b, a - b) = 1 or 2.
Solution:

Let d = (a + b, a - b), then $\frac{d}{(a+b)}$ and  $\frac{d}{(a-b)}$ this implies  $\frac{d}{(a - b + a - b)}$ and  $\frac{d}{(a - b - a + b)}$. This implies $\frac{d}{2(a, b)}$ = 2 $\times$ 1 = 2.

Hence, $\frac{d}{2}$ implies d = 1 or 2.

*AP and SAT are registered trademarks of the College Board.