prime number.pdf

Its related with prime numbers

1. Prime Numbers
JADHAV SHAILESH SHASHIKANT
15th DECEMBER,2018
JADHAV SHAILESH SHASHIKANT () Prime Numbers 15th DECEMBER,2018 1 / 9

2. contents of presenation
Number of primes are innite
Every nonzero positive integer has atleast one prime
divisor.
Euclids lemma
JADHAV SHAILESH SHASHIKANT () Prime Numbers 15th DECEMBER,2018 2 / 9

3. 1. NUMBER OF PRIMES ARE INFINITE
Theorem
1.Number of primes are innite
Proof.
Suppose there are nitely many primes
Supposep1;p2; ;pnare the only prime numbers.
Now we construct the new number
p=p1p2 pn+ 1 (1.1)
Clearlypis larger than any of the primes, so it does not equal to any
of the primes.
Sincep1;p2; ;pnconstitute all the primespcant be a
prime.
Thus it must be divisible by atleast one of our nitely many primes
sayp1.
JADHAV SHAILESH SHASHIKANT () Prime Numbers 15th DECEMBER,2018 3 / 9

4. But from (1.1) when we dividepbyp1the remainder is1.
Which is a contradiction.So our original assumption that there are
nitely many primes must be false.
Thus there are innitely many primes.
JADHAV SHAILESH SHASHIKANT () Prime Numbers 15th DECEMBER,2018 4 / 9

5. 2. Every nonzero positive integer has atleast one prime
divisor
Theorem
2.Every nonzero positive integer has atleast one prime divisor
Proof.
We will prove the result by second principle of nite induction.
Letp(n) be the statement given bellow
p(n) :nhas prime divisor for each positive integer greater than 1.
ifn= 2 then we will verifyp(2).
2 itself a prime divisor of 2.
Hencep(2) is true.
Let m be an integer greater than 2 and assume that the statement is
true for allk<m.
We will prove result forp(m).
Ifmitself prime,then m has prime divisor m itself.
JADHAV SHAILESH SHASHIKANT () Prime Numbers 15th DECEMBER,2018 5 / 9

6. Otherwise m is composite.
Hence there exist integersm1andm2such that
m=m1m2 1<m1;m2<m
Therefore by induction hypothesism1(as well asm2) has prime
divisor, sayp
)transitivity of divisionpjm1andm1jm=)pjm
Hencemhas prime divisor.
)p(m)is true.
Hence by second principle of nite inductionp(n) is true for alln2
JADHAV SHAILESH SHASHIKANT () Prime Numbers 15th DECEMBER,2018 6 / 9

7. 3.EUCLIDS LAMMA
Theorem
3.Ifpis a prime such thatpjab=)pjaorpjb
Proof.
Letpjab.
Ifpjathen we are through.
Ifp-a, then (p;a) = 1
Now (p;a) = 1
There exist integer m,n such that
1 =mp+na
multiplying by b we get
b=mpb+nab.
Nowpjpandpjab=)pj((mb)p) andpj((n)ab)
Hencepj(mbp+nab) =)pjb
JADHAV SHAILESH SHASHIKANT () Prime Numbers 15th DECEMBER,2018 7 / 9

8. 3.1 Example
Example
Ifpis a prime such thatpjaandpj(a
2
+b
2
) then prove thatpjb.
Proof.
pjaandpj(a
2
+b
2
)
)pja
2
andpj(a
2
+b
2
)
)pj[a
2
(a
2
+b
2
)]
)pjb
2
givespjb
JADHAV SHAILESH SHASHIKANT () Prime Numbers 15th DECEMBER,2018 8 / 9

9. THANK YOU
JADHAV SHAILESH SHASHIKANT () Prime Numbers 15th DECEMBER,2018 9 / 9