Primes

 

Motivation:

                     The data security problem is getting important these days due to the widespread use of networked computers.  And some properties about prime numbers are used in data encryption because of the nature of  intensive computation to handle this kind of question.  In high school,  we study basic things to build good foundation.

 

Definition  ( Prime ):

          Let  p be a natural number and p > 1 .  If p only has two divisors 1 and p, then p is a prime.

 

 

Theorem :  There exist infinitely many primes.

      

         Proof: 

 

                      Assume the number of primes is finite, say n.

                      Let  p₁, p_2, …, p_n  be all the primes.

                      Consider 

                                         p = p₁ p₂ p₃ …p_n + 1 .

 

                        All the primes can not be the divisors of p.  So, p is also a prime.

                        With n primes we already have plus this one,  we have (n+1) primes.

                         But our assumption states there exist only n primes.

                         We get contradiction here.   So, the assumption does not hold.

                 

                        Therefore, there are infinitely many primes.

 

 

Theorem :   Let q be a natural number. 

                    If q is not a prime, then there must exist d such that

                                1< d   ,  d | q .   (  Notation : d | q  means d is a divisor of q . )

 

          Proof: 

                           q is not a prime .  If  there exists a number p such that

                                   q = pr  ,    q > p   .

 

                           So, we get another divisor r.  Let’s check the range of r.

                                     r =      1 <     

                          In other words,

                                      r | q ,  1 < r     .

 

 

Example :  Check if 61 is a prime.

                    With this theorem, it is only necessary to check the numbers     ( < 8 )

                      2, 3, 5, 7 are not divisors of 61.  Thus, 61 is a prime.

 

 

 

Definition ( Relatively Prime ) :

              Let p and q be natural numbers.   If  gcd( p, q ) = 1, then we say that p and q are relatively prime to each other.

 

 

Definition ( Prime Factorization )

               For a natural number N,  if we represent it as

                              

                               where  p₁ , p₂ , … , p_n are distinct primes less than N ,

                                          a₁ , a₂ , … , a_n are positive integers

 

               then we call this process as prime factorization.

 

Example:  

                      45=3²  5

                      128 = 2⁶

 

 

Theorem ( Number of Divisors )

                If a natural number N has prime factorization representation

                           

               then  the number of  positive divisors of  N is

                         s=

 

       Proof: 

 

                          Each divisor of N should be of the form

                                  

 

                           For b₁, it can be 0, 1, 2, …, a₁;

                           for b₂, it can be 0, 1, 2, …., a_2;

                                       …

                           for b_n , it can be 0, 1, 2, …., a_n .

 

                         So, as a whole, we have

                                       choices.

 

 

Example:  How many divisors are there for  728 ?

 

                     728 = 2³  7  13

                 So,   it has  (4  2  2) divisors, i.e., 32 divisors .