Number Theory  Lecture 2
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 wellordering principle.
The wellordering 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 (ab) 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 ab, then there is an integer c such that b=ac
Now if b=ac
Then b= (a)(c)
Then –ab
Example:
The following examples illustrate the concept of divisibility of integers:
 13182
 530
 17289
 6 is not divided by 44
 7 is not divided by 50
 333
 170
Look at the last example part 7 which is 170, 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, nanosecond, etc.)
 Used for counting living and nonliving 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:

Reflexive property: nn

Transitive property: dn and nm then dm

Linearity property: dn and dm then d(an+bm)

Multiplication property: dn implies adan

Cancellation property: adan and a is not equal to zero which implies dn

1 divides every integer: 1n

Every integer divides zero: n0

Comparison property: dn and n is not equal to zero implies d<n

Equality: dn and nd implies d=n

Division conjugate: dn and nd then (nd)n
Proposition:
If a,b and c are integers with ab and bc, then ac.
Proof:
Since ab and bc 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=bc(e(cb))
And then bf=c
And we conclude that ac
Example: 1166 and 66198 then 11198.
Proposition:
If a, b, m and n are integers and if ca and cb then c(ma+nb)
Proof:
Since ca and cb, 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
 da and db
 If ca and cb then d>c that is if c is a common divisor of a and b then cd.
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 nonzero 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 ac and bc and (a, b)= 1 then abc. but the conclusion will be false if “a” and “b” do not have 1 as a greatest common divisor.
PROOF:
Let ac and bc
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 abc
EXAMPLE:
We have a= 1 and b=4 and c=1
Then as we see (a, b)=1
As ac = 11
And bc = 41
Then abc= 4(1)1
EXAMPLE NUMBER 2:
We have a= 5 and b= 7 then c=35
Then as we see (a, b)=1
Then ac = 535
And bc = 735
Then abc = 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 ac and bc then ab does not divide c.
EUCLID’S LEMMA:
If abc and (a, b)=1 then ac.
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 Pa 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 da and dP
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 Pab then Pa or Pb.
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 Pabs p, if P does not, divides “a” then P must divide b as Pb.
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.