Định lý liên quan đến số nguyên tố

 

=====================================

Định lý: cho p là một số nguyên tố,  , .

Nếu  thì q là số nguyên tố.

Chứng minh:

Ta có  chỉ chia hết cho các số nguyên tố là ước của  ,p và các số nguyên tố có dạng  . Nếu q là hợp số, do . Nên mọi ước của q đều có dạng  . Khi đó nếu q là hợp số thì q có ít nhất 2 ước là  .Ta có:

 

Do   nên   nên  đẵng  thứ trên không xảy ra. Vậy q là số nguyên tố.

Ví dụ:

Chọn  p=127

           q=4.127+1=509

Ta có:  

Có  nên q=509 là số nguyên tố.

Nhờ định lý này, chúng ta dễ dàng xác định với một số nguyên tố p cho trước thì   có phải là số nguyên tố hay không.

Điều này giúp chúng ta tìm được các số nguyên tố cực lớn là ước của q-1, rất có ích trong hệ mã RSA khi dễ dàng tìm được các số nguyên tố cực lớn là ước của  .

Theorem: let p be a prime number, 

If  then q is a prime number.

Prove:

We have  divisible by only prime numbers is divisor of , p and prime numbers have the form . If q is a composite, due

. So all divisor of q has the form . Then if q is a composite, then q has at least 2 divisors . We have:

Due  therefore   so the above thing didn't happen. So q is a prime number.

For example:

 

Choose p=127

                   q=4.127+1=509

We have: 

have  so q = 509 is a prime number.

Thanks to this theorem, we can easily determine with a given primes p  is it a prime number or not. This helps us to find very large primes that are divisors of q-1, which is very useful in the RSA coding system when it is easy to find extremely large primes that are divisors of .