Number theory:

for the first lecture of Number theory kindly read: Number Theory | Set of Natural Numbers 

As number theory is a concern of a set of natural numbers and we apply different formulas on numbers like well-ordering principle.

The well-ordering principle is derived from the induction method.

Similarly that of about DMAS rule. “D” stands for divides, “M” stands for multiplication, “A” stands for addition and “S” stands for subtraction.

DIVISIBILITY:

Number Theory involves Divisibility.

Let “a” and “b” be any two integers with “a” which is not equal to zero. Then “a” is said to divide “b” written (a|b) if there is an integer “c” such that b=ac. If no such integer can be found when we say “a” does not divide “b”. “a” is called a divisor or a factor of “b” and “b” is called a multiple of “a”. Also if a|b, then there is an integer c such that b=ac

Now if b=ac

Then b= (-a)(-c)

Then –a|b

Example:-

The following examples illustrate the concept of divisibility of integers:

• 13|182
• -5|30
• 17|289
• 6 is not divided by 44
• 7 is not divided by 50
• -3|33
• 17|0

Look at the last example part 7 which is 17|0, 0 is multiple and 17 is divisor.

Uses of Natural Numbers in Real Life:-

• We use it to count anything.
• It is used for time measurement (minutes, seconds, hours, nano-second, etc.)
• Used for counting living and non-living things.
• Used for buying anything.
• Used as a time of arrival of the airplane.
• Position of anything just like Pakistan is on 3^rd position in population.

Examples:

The divisors of 6 are 1,2,3 and 6

The divisors of 17 are 1 and 17.

The divisors of 100 are 1, 2, 4, 5, 10, 20, 25, 50 and 100.

THEOREMS:

1. Reflexive property:  n|n

2. Transitive property:  d|n and n|m then d|m

3. Linearity property: d|n and d|m then d|(an+bm)

4. Multiplication property: d|n implies ad|an

5. Cancellation property: ad|an and a is not equal to zero which implies d|n

6. 1 divides every integer: 1|n

7. Every integer divides zero: n|0

8. Comparison property: d|n and n is not equal to zero implies |d|<|n|

9. Equality: d|n and n|d implies |d|=|n|

10. Division conjugate: d|n and n|d then (n|d)|n

Proposition:

If a,b and c are integers with a|b and b|c, then a|c.

Proof:

Since a|b and b|c by definition, there are integers e and f such that b=ae and c=bf

Hence bf=(ae)f    by   b=ae;

And bf=(ef)

Then bf=b|c(e(c|b))

And then bf=c

And we conclude that a|c

Example: 11|66 and 66|198   then   11|198.

Proposition:

If a, b, m and n are integers and if c|a   and c|b then c|(ma+nb)

Proof:

Since c|a   and c|b, then by definition there are integers    e   and    f   such that   a=ce    and   b=cf

Hence   ma+nb  =   m(ce) + n(cf)

Consequently we see that c|(ma+nb).

 

DIVISION OF ALGORITHM:

Number Theory involves the division of Algorithm too.

Let “a” and “b” be integers such that b is greater than zero. Then there exists a unique integer   “q”  and   “r” such that a=bq+r, where the range of r is from 0 to “b”  such that 0<r<b.  and moreover “r” is remainder and “q” is quotient.

GREATEST COMMON DIVISOR:

Let “a”   and “b”   be any two integers at least one of which is nonzero. Then their greatest common divisor  (GCD) is a positive integer “d” such that

• d|a and d|b
• If c|a and c|b then d>c that is if c is a common divisor of a and b then c|d.

For further detail of greatest common divisor read this: Greatest Common Divisor| GCD

COPRIME:

If  “a”  and “b  are any two integers such that at least one of which is a non-zero then we say “a” and “b”  are coprime if their greatest common divisor is one. It is denoted as (a,b)=1 . coprime numbers are also called relative prime numbers.

COROLLARY:

If a|c and b|c and (a, b)= 1 then ab|c. but the conclusion will be false if “a” and “b” do not have 1 as a greatest common divisor.

PROOF:

Let a|c and b|c

Then there exist intergers “r” and  “s”  such that

We can say c= ar   and     c= bs

Also (a, b)=1

This implies that there exist integers  “u” and  “v” such that

1= au+bv

This implies that c*1 = c a u + c b v

Then c= bs a u + ar b v

Then c + ab (s u + r v)

This implies ab|c

EXAMPLE:

We have a= 1 and b=4 and c=1

Then as we see (a, b)=1

As a|c = 1|1

And b|c = 4|1

Then ab|c= 4(1)|1

EXAMPLE NUMBER 2:

We have a= 5 and b= 7 then c=35

Then as we see (a, b)=1

Then a|c = 5|35

And b|c = 7|35

Then ab|c = 5(7)|35.

EXAMPLE NUMBER 3:

If we take a = 2, b= 4 and c= 12 then GCD of ab is not 1, it’s 2 so as a|c and b|c then ab does not divide c.

EUCLID’S LEMMA:

If a|bc and (a, b)=1 then a|c.

NOTE: Euclid’s Lemma is false when GCD of a and b is not 1.

LEMMA:

Let d>1 be the smallest positive divisor of an integer “n”, then d is prime.

Proof:

Let  “d’ “ by any divisor of  “d”. then 1<d’<d

Suppose d’ is not equal to 1 then d’|d and d |n then by the property d’|n but also d’<d.

But  “n” has the smallest divisor “d”. So,  d’|n and d’ < d which implies d’=d

Hence the only divisor of d are 1 and d itself

Which implies “d” is prime.

NOTE:

Thus each integer >1 is either a prime or divisible by a prime.

EXAMPLE:

2 is a prime number having 2 divisors.

3 is a prime number having 1 divisor.

4 is not a prime number yet it has 3 divisors and that is 1, 2, 4 where 1 and 2 both are prime numbers.

THEOREM:

Let  “P” be a prime number and   “a” any integer. Then either P|a or (a, P)=1

PROOF:

If P| a, we have nothing to prove but if P does not divide “a”   then we show that (a,  P) = 1.

Let  d=(a,  P)

Which implies d|a and d|P

Since P is a prime number and d=1 or d=P

If d=P then P| a, not possible

Hence d=1

So (a,  P)=1

COROLLARY:

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

PRIME DIVISIBILITY PROPERTY:

Let  “P”  be a prime number and suppose that P divides the product a1.a2.a3…ar.  Then P divides at least one of the factor a1, a2, …, ar

PROOF:

If “P” divides a1, we are done.

If not, we apply the claim to the product as a1(a2a3…ar) to conclude that P must divide a2.a3.a4…ar.

In other words, we are applying the claim with a=a1 and b= a2a3…ar, as we know that P|abs p, if P does not, divides “a” then P must divide b as P|b.

So, now we know that P divides a2a3a4…ar. If P divides a2 then we are done but if P does not divide a2 then P must divide a3a4a5…ar as a=a2 and b=a3a4a5…ar and this will continue till we find any number which is divided by any number in the product so that we will eventually find a number that is divided by P.

Number theory is the study of the set of the Natural Numbers and we can apply many operation and rules on numbers.