Definition 1. Prime number− is a natural number greater than one that is divisible only by itself and 1.

In other words, a number is prime if it has only two distinct natural divisors.

Definition 2. Any natural number that has other divisors besides itself and one is called a composite number.

In other words integers numbers that are not prime numbers are called composite numbers. From Definition 1 it follows that a composite number has more than two natural factors. The number 1 is neither prime nor composite because has only one divisor 1 and, in addition, many theorems regarding prime numbers do not hold for unity.

From Definitions 1 and 2 it follows that every positive integer greater than 1 is either a prime number or a composite number.

Below is a program to display prime numbers up to 5000. Fill in the cells, click on the "Create" button and wait a few seconds.

Prime numbers table

Statement 1. If p- prime number and a any integer, then either a divided by p, or p And a coprime numbers.

Really. If p A prime number is divisible only by itself and 1 if a not divisible by p, then the greatest common divisor a And p is equal to 1. Then p And a mutually prime numbers.

Statement 2. If the product of several numbers of numbers a 1 , a 2 , a 3, ... is divisible by a prime number p, then at least one of the numbers a 1 , a 2 , a 3, ...divisible by p.

Really. If none of the numbers were divisible by p, then the numbers a 1 , a 2 , a 3, ... would be coprime numbers with respect to p. But from Corollary 3 () it follows that their product a 1 , a 2 , a 3, ... is also relatively prime with respect to p, which contradicts the condition of the statement. Therefore at least one of the numbers is divisible by p.

Theorem 1. Any composite number can always be represented and, moreover, the only way as a product of a finite number of prime numbers.

Proof. Let k composite number, and let a 1 is one of its divisors different from 1 and itself. If a 1 is composite, then has in addition to 1 and a 1 and another divisor a 2. If a 2 is a composite number, then it has, in addition to 1 and a 2 and another divisor a 3. Reasoning in this way and taking into account that the numbers a 1 , a 2 , a 3 , ... decrease and this series contains a finite number of terms, we will reach some prime number p 1 . Then k can be represented in the form

Suppose there are two decompositions of a number k:

Because k=p 1 p 2 p 3...divisible by a prime number q 1, then at least one of the factors, for example p 1 is divisible by q 1 . But p 1 is a prime number and is only divisible by 1 and itself. Hence p 1 =q 1 (because q 1 ≠1)

Then from (2) we can exclude p 1 and q 1:

Thus, we are convinced that every prime number that appears as a factor in the first expansion one or more times also appears in the second expansion at least as many times, and vice versa, any prime number that appears as a factor in the second expansion one or more times also appears in the first expansion at least the same number of times. Therefore, any prime number appears as a factor in both expansions the same number of times and, thus, these two expansions are the same.■

Expansion of a composite number k can be written in the following form

(3)

Where p 1 , p 2, ... various prime numbers, α, β, γ ... positive integers.

Expansion (3) is called canonical expansion numbers.

Prime numbers occur unevenly in the series of natural numbers. In some parts of the row there are more of them, in others - less. The further we move along the number series, the less common prime numbers are. The question arises, is there a largest prime number? The ancient Greek mathematician Euclid proved that there are infinitely many prime numbers. We present this proof below.

Theorem 2. The number of prime numbers is infinite.

Proof. Suppose there are a finite number of prime numbers, and let the largest prime number be p. Let's consider all numbers greater p. By assumption of the statement, these numbers must be composite and must be divisible by at least one of the prime numbers. Let's choose a number that is the product of all these prime numbers plus 1:

Number z more p because 2p already more p. p is not divisible by any of these prime numbers, because when divided by each of them gives a remainder of 1. Thus we come to a contradiction. Therefore there are an infinite number of prime numbers.

This theorem is a special case of a more general theorem:

Theorem 3. Let an arithmetic progression be given

Then any prime number included in n, should be included in m, therefore in n other prime factors that are not included in m and, moreover, these prime factors in n are included no more times than in m.

The opposite is also true. If every prime factor of a number n included at least as many times in the number m, That m divided by n.

Statement 3. Let a 1 ,a 2 ,a 3,... various prime numbers included in m So

Where i=0,1,...α , j=0,1,...,β , k=0,1,..., γ . notice, that αi accepts α +1 values, β j accepts β +1 values, γ k accepts γ +1 values, ... .

The article discusses the concepts of prime and composite numbers. Definitions of such numbers are given with examples. We present a proof that the number of prime numbers is unlimited and we will record it in the table of prime numbers using the method of Eratosthenes. Evidence will be given to determine whether a number is prime or composite.

Yandex.RTB R-A-339285-1

Prime and Composite Numbers - Definitions and Examples

Prime and composite numbers are classified as positive integers. They must be greater than one. Divisors are also divided into simple and composite. To understand the concept of composite numbers, you must first study the concepts of divisors and multiples.

Definition 1

Prime numbers are integers that are greater than one and have two positive divisors, that is, themselves and 1.

Definition 2

Composite numbers are integers that are greater than one and have at least three positive divisors.

One is neither a prime nor a composite number. It has only one positive divisor, so it is different from all other positive numbers. All positive integers are called natural numbers, that is, used in counting.

Definition 3

Prime numbers are natural numbers that have only two positive divisors.

Definition 4

Composite number is a natural number that has more than two positive divisors.

Any number that is greater than 1 is either prime or composite. From the property of divisibility we have that 1 and the number a will always be divisors for any number a, that is, it will be divisible by itself and by 1. Let's give a definition of integers.

Definition 5

Natural numbers that are not prime are called composite numbers.

Prime numbers: 2, 3, 11, 17, 131, 523. They are only divisible by themselves and 1. Composite numbers: 6, 63, 121, 6697. That is, the number 6 can be decomposed into 2 and 3, and 63 into 1, 3, 7, 9, 21, 63, and 121 into 11, 11, that is, its divisors will be 1, 11, 121. The number 6697 is decomposed into 37 and 181. Note that the concepts of prime numbers and coprime numbers are different concepts.

To make it easier to use prime numbers, you need to use a table:

A table for all existing natural numbers is unrealistic, since they exist infinite set. When numbers reach sizes of 10000 or 1000000000, then you should consider using the Sieve of Eratosthenes.

Let's consider the theorem that explains the last statement.

Theorem 1

The smallest positive divisor other than 1 of a natural number greater than one is a prime number.

Evidence 1

Let us assume that a is a natural number that is greater than 1, b is the smallest non-one divisor of a. It is necessary to prove that b is a prime number using the method of contradiction.

Let's assume that b is a composite number. From here we have that there is a divisor for b, which is different from 1 as well as from b. Such a divisor is denoted as b 1. It is necessary that condition 1< b 1 < b was completed.

From the condition it is clear that a is divided by b, b is divided by b 1, which means that the concept of divisibility is expressed as follows: a = b q and b = b 1 · q 1 , from where a = b 1 · (q 1 · q) , where q and q 1 are integers. According to the rule of multiplication of integers, we have that the product of integers is an integer with an equality of the form a = b 1 · (q 1 · q) . It can be seen that b 1 is the divisor for the number a. Inequality 1< b 1 < b Not corresponds, because we find that b is the smallest positive and non-1 divisor of a.

Theorem 2

There are an infinite number of prime numbers.

Evidence 2

Presumably we take a finite number of natural numbers n and denote them as p 1, p 2, …, p n. Let's consider the option of finding a prime number different from those indicated.

Let us take into consideration the number p, which is equal to p 1, p 2, ..., p n + 1. It is not equal to each of the numbers corresponding to prime numbers of the form p 1, p 2, ..., p n. The number p is prime. Then the theorem is considered to be proven. If it is composite, then you need to take the notation p n + 1 and show that the divisor does not coincide with any of p 1, p 2, ..., p n.

If this were not so, then, based on the divisibility property of the product p 1, p 2, ..., p n , we find that it would be divisible by pn + 1. Note that the expression p n + 1 dividing the number p equals the sum p 1, p 2, ..., p n + 1. We obtain that the expression p n + 1 The second term of this sum, which equals 1, must be divided, but this is impossible.

It can be seen that any prime number can be found among any number of given prime numbers. It follows that there are infinitely many prime numbers.

Since there are a lot of prime numbers, the tables are limited to the numbers 100, 1000, 10000, and so on.

When compiling a table of prime numbers, you should take into account that such a task requires sequential checking of numbers, starting from 2 to 100. If there is no divisor, it is recorded in the table; if it is composite, then it is not entered into the table.

Let's look at it step by step.

If you start with the number 2, then it has only 2 divisors: 2 and 1, which means it can be entered into the table. Same with the number 3. The number 4 is composite; it must be decomposed into 2 and 2. The number 5 is prime, which means it can be recorded in the table. Do this until the number 100.

This method inconvenient and long. You can create a table, but you will have to spend a large number of time. It is necessary to use divisibility criteria, which will speed up the process of finding divisors.

The method using the sieve of Eratosthenes is considered the most convenient. Let's look at the tables below as an example. To begin with, the numbers 2, 3, 4, ..., 50 are written down.

Now you need to cross out all the numbers that are multiples of 2. Perform sequential strikethroughs. We get a table like:

We move on to crossing out numbers that are multiples of 5. We get:

Cross out numbers that are multiples of 7, 11. Ultimately the table looks like

Let's move on to the formulation of the theorem.

Theorem 3

The smallest positive and non-1 divisor of the base number a does not exceed a, where a is the arithmetic root of the given number.

Evidence 3

Must be designated b least divisor composite number a. There is an integer q, where a = b · q, and we have that b ≤ q. Inequalities of the form are unacceptable b > q, because the condition is violated. Both sides of the inequality b ≤ q should be multiplied by any positive number b not equal to 1. We get that b · b ≤ b · q, where b 2 ≤ a and b ≤ a.

From the proven theorem it is clear that crossing out numbers in the table leads to the fact that it is necessary to start with a number that is equal to b 2 and satisfies the inequality b 2 ≤ a. That is, if you cross out numbers that are multiples of 2, then the process begins with 4, and multiples of 3 with 9, and so on until 100.

Compiling such a table using Eratosthenes' theorem suggests that when all composite numbers are crossed out, prime numbers will remain that do not exceed n. In the example where n = 50, we have that n = 50. From here we get that the sieve of Eratosthenes sifts out all composite numbers that are not significant in value. greater value root of 50. Searching for numbers is done by crossing out.

Before solving, you need to find out whether the number is prime or composite. Divisibility criteria are often used. Let's look at this in the example below.

Example 1

Prove that the number 898989898989898989 is composite.

Solution

The sum of the digits of a given number is 9 8 + 9 9 = 9 17. This means that the number 9 · 17 is divisible by 9, based on the divisibility test by 9. It follows that it is composite.

Such signs are not able to prove the primeness of a number. If verification is needed, other actions should be taken. The most suitable way is to enumerate numbers. During the process, prime and composite numbers can be found. That is, the numbers should not exceed a in value. That is, the number a must be factorized into prime factors. if this is satisfied, then the number a can be considered prime.

Example 2

Determine the composite or prime number 11723.

Solution

Now you need to find all the divisors for the number 11723. Need to evaluate 11723 .

From here we see that 11723< 200 , то 200 2 = 40 000 , and 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

For a more accurate estimate of the number 11723, you need to write the expression 108 2 = 11 664, and 109 2 = 11 881 , That 108 2 < 11 723 < 109 2 . It follows that 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

When expanding, we find that 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83 , 89 , 97 , 101 , 103 , 107 are all prime numbers. This entire process can be depicted as division by a column. That is, divide 11723 by 19. The number 19 is one of its factors, since we get division without a remainder. Let's represent the division as a column:

It follows that 11723 is a composite number, because in addition to itself and 1 it has a divisor of 19.

Answer: 11723 is a composite number.

If you notice an error in the text, please highlight it and press Ctrl+Enter

Prime number is a natural (positive integer) number that is divisible without a remainder by only two natural numbers: by and by itself. In other words, a prime number has exactly two natural divisors: and the number itself.

By definition, the set of all divisors of a prime number is two-element, i.e. represents a set.

The set of all prime numbers is denoted by the symbol. Thus, due to the definition of the set of prime numbers, we can write: .

The sequence of prime numbers looks like this:

Fundamental Theorem of Arithmetic

Fundamental Theorem of Arithmetic states that every natural number greater than one can be represented as a product of prime numbers, and in a unique way, up to the order of the factors. Thus, prime numbers are the elementary "building blocks" of the set of natural numbers.

Natural number expansion title="Rendered by QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} canonical:

where is a prime number, and . For example, the canonical expansion of a natural number looks like this: .

Representing a natural number as a product of primes is also called factorization of a number.

Properties of Prime Numbers

Sieve of Eratosthenes

One of the most famous algorithms for searching and recognizing prime numbers is sieve of Eratosthenes. So this algorithm was named after the Greek mathematician Eratosthenes of Cyrene, who is considered the author of the algorithm.

To find all prime numbers less than a given number, following Eratosthenes' method, follow these steps:

Step 1. Write down all the natural numbers from two to , i.e. .
Step 2. Assign the variable the value , that is, the value equal to the smallest prime number.
Step 3. Cross out in the list all numbers from to that are multiples of , that is, the numbers: .
Step 4. Find the first uncrossed number in the list greater than , and assign the value of this number to a variable.
Step 5. Repeat steps 3 and 4 until number is reached.

The process of applying the algorithm will look like this:

All remaining uncrossed numbers in the list at the end of the process of applying the algorithm will be the set of prime numbers from to .

Goldbach conjecture

Cover of the book “Uncle Petros and the Goldbach Hypothesis”

Despite the fact that prime numbers have been studied by mathematicians for quite a long time, many related problems remain unsolved today. One of the most famous unsolved problems is Goldbach's hypothesis, which is formulated as follows:

• Is it true that every even number, greater than two, can be represented as the sum of two prime numbers (binary Goldbach hypothesis)?
• Is it true that every odd number greater than 5 can be represented as the sum of three prime numbers (Goldbach's ternary hypothesis)?

It should be said that the ternary Goldbach hypothesis is a special case of the binary Goldbach hypothesis, or as mathematicians say, the ternary Goldbach hypothesis is weaker than the binary Goldbach hypothesis.

Goldbach's conjecture became widely known outside the mathematical community in 2000 thanks to a promotional marketing stunt by the publishing companies Bloomsbury USA (USA) and Faber and Faber (UK). These publishing houses, having released the book “Uncle Petros and Goldbach’s Conjecture,” promised to pay a prize of 1 million US dollars to anyone who proves Goldbach’s hypothesis within 2 years from the date of publication of the book. Sometimes the mentioned prize from publishers is confused with prizes for solving the Millennium Prize Problems. Make no mistake, Goldbach’s hypothesis is not classified by the Clay Institute as a “millennium challenge,” although it is closely related to Riemann hypothesis- one of the “millennium challenges”.

The book “Prime numbers. Long road to infinity"

Cover of the book “The World of Mathematics. Prime numbers. Long road to infinity"

Additionally, I recommend reading a fascinating popular science book, the annotation to which says: “The search for prime numbers is one of the most paradoxical problems in mathematics. Scientists have been trying to solve it for several millennia, but, growing with new versions and hypotheses, this mystery still remains unsolved. The appearance of prime numbers is not subject to any system: they appear spontaneously in the series of natural numbers, ignoring all attempts by mathematicians to identify patterns in their sequence. This book will allow the reader to trace the evolution of scientific concepts from ancient times to the present day and introduce the most interesting theories of searching for prime numbers.”

Additionally, I will quote the beginning of the second chapter of this book: “Prime numbers are one of important topics, which take us back to the very beginnings of mathematics, and then, along a path of increasing complexity, lead us to the forefront modern science. Thus, it would be very useful to trace the fascinating and complex history of prime number theory: exactly how it developed, exactly how the facts and truths that are now generally accepted were collected. In this chapter we will see how generations of mathematicians carefully studied the natural numbers in search of a rule that predicted the appearance of prime numbers - a rule that became increasingly elusive as the search progressed. We will also look in detail at the historical context: under what conditions mathematicians worked and to what extent their work involved mystical and semi-religious practices, which are not at all similar to scientific methods, used nowadays. Nevertheless, slowly and with difficulty, the ground was prepared for new views that inspired Fermat and Euler in the 17th and 18th centuries.”

• Translation

The properties of prime numbers were first studied by mathematicians Ancient Greece. Mathematicians of the Pythagorean school (500 - 300 BC) were primarily interested in the mystical and numerological properties of prime numbers. They were the first to come up with ideas about perfect and friendly numbers.

A perfect number has a sum of its own divisors equal to itself. For example, the proper divisors of the number 6 are 1, 2 and 3. 1 + 2 + 3 = 6. The divisors of the number 28 are 1, 2, 4, 7 and 14. Moreover, 1 + 2 + 4 + 7 + 14 = 28.

Numbers are called friendly if the sum of the proper divisors of one number is equal to another, and vice versa - for example, 220 and 284. We can say that a perfect number is friendly to itself.

By the time of Euclid's Elements in 300 B.C. several have already been proven important facts regarding prime numbers. In Book IX of the Elements, Euclid proved that there are an infinite number of prime numbers. This, by the way, is one of the first examples of using proof by contradiction. He also proves the Fundamental Theorem of Arithmetic - every integer can be represented uniquely as a product of prime numbers.

He also showed that if the number 2n-1 is prime, then the number 2n-1 * (2n-1) will be perfect. Another mathematician, Euler, was able to show in 1747 that all even perfect numbers can be written in this form. To this day it is unknown whether odd perfect numbers exist.

In the year 200 BC. The Greek Eratosthenes came up with an algorithm for finding prime numbers called the Sieve of Eratosthenes.

And then there was a big break in the history of the study of prime numbers, associated with the Middle Ages.

The following discoveries were made already at the beginning of the 17th century by the mathematician Fermat. He proved Albert Girard's conjecture that any prime number of the form 4n+1 can be written uniquely as the sum of two squares, and also formulated the theorem that any number can be written as the sum of four squares.

He developed a new method for factoring large numbers, and demonstrated it on the number 2027651281 = 44021 × 46061. He also proved Fermat's Little Theorem: if p is a prime number, then for any integer a it will be true that a p = a modulo p.

This statement proves half of what was known as the "Chinese conjecture" and dates back 2000 years: an integer n is prime if and only if 2 n -2 is divisible by n. The second part of the hypothesis turned out to be false - for example, 2,341 - 2 is divisible by 341, although the number 341 is composite: 341 = 31 × 11.

Fermat's Little Theorem served as the basis for many other results in number theory and methods for testing whether numbers are primes - many of which are still used today.

Fermat corresponded a lot with his contemporaries, especially with a monk named Maren Mersenne. In one of his letters, he hypothesized that numbers of the form 2 n +1 will always be prime if n is a power of two. He tested this for n = 1, 2, 4, 8 and 16, and was confident that in the case where n was not a power of two, the number was not necessarily prime. These numbers are called Fermat's numbers, and only 100 years later Euler showed that the next number, 2 32 + 1 = 4294967297, is divisible by 641, and therefore is not prime.

Numbers of the form 2 n - 1 have also been the subject of research, since it is easy to show that if n is composite, then the number itself is also composite. These numbers are called Mersenne numbers because he studied them extensively.

But not all numbers of the form 2 n - 1, where n is prime, are prime. For example, 2 11 - 1 = 2047 = 23 * 89. This was first discovered in 1536.

For many years, numbers of this kind provided mathematicians with the largest known prime numbers. That M 19 was proved by Cataldi in 1588, and for 200 years was the largest known prime number, until Euler proved that M 31 was also prime. This record stood for another hundred years, and then Lucas showed that M 127 is prime (and this is already a number of 39 digits), and after that research continued with the advent of computers.

In 1952 the primeness of the numbers M 521, M 607, M 1279, M 2203 and M 2281 was proven.

By 2005, 42 Mersenne primes had been found. The largest of them, M 25964951, consists of 7816230 digits.

Euler's work had a huge impact on the theory of numbers, including prime numbers. He extended Fermat's Little Theorem and introduced the φ-function. Factorized the 5th Fermat number 2 32 +1, found 60 pairs of friendly numbers, and formulated (but could not prove) the quadratic reciprocity law.

He was the first to introduce methods mathematical analysis and developed the analytical theory of numbers. He proved that not only the harmonic series ∑ (1/n), but also a series of the form

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

The result obtained by the sum of the reciprocals of prime numbers also diverges. The sum of n terms of the harmonic series grows approximately as log(n), and the second series diverges more slowly as log[ log(n) ]. This means that, for example, the sum of the reciprocals of all prime numbers found to date will give only 4, although the series still diverges.

At first glance, it seems that prime numbers are distributed quite randomly among integers. For example, among the 100 numbers immediately before 10000000 there are 9 primes, and among the 100 numbers immediately after this value there are only 2. But over large segments the prime numbers are distributed quite evenly. Legendre and Gauss dealt with issues of their distribution. Gauss once told a friend that in any free 15 minutes he always counts the number of primes in the next 1000 numbers. By the end of his life, he had counted all the prime numbers up to 3 million. Legendre and Gauss equally calculated that for large n the prime density is 1/log(n). Legendre estimated the number of prime numbers in the range from 1 to n as

π(n) = n/(log(n) - 1.08366)

And Gauss is like a logarithmic integral

π(n) = ∫ 1/log(t) dt

With an integration interval from 2 to n.

The statement about the density of primes 1/log(n) is known as the Prime Distribution Theorem. They tried to prove it throughout the 19th century, and progress was achieved by Chebyshev and Riemann. They connected it with the Riemann hypothesis, a still unproven hypothesis about the distribution of zeros of the Riemann zeta function. The density of prime numbers was simultaneously proved by Hadamard and Vallée-Poussin in 1896.

There are still many unsolved questions in prime number theory, some of which are hundreds of years old:

• The twin prime hypothesis is about an infinite number of pairs of prime numbers that differ from each other by 2
• Goldbach's conjecture: any even number, starting with 4, can be represented as the sum of two prime numbers
• Is there an infinite number of prime numbers of the form n 2 + 1?
• Is it always possible to find a prime number between n 2 and (n + 1) 2? (the fact that there is always a prime number between n and 2n was proven by Chebyshev)
• Is the number of Fermat primes infinite? Are there any Fermat primes after 4?
• is there an arithmetic progression of consecutive primes for any given length? for example, for length 4: 251, 257, 263, 269. The maximum length found is 26.
• Is there an infinite number of sets of three consecutive prime numbers in an arithmetic progression?
• n 2 - n + 41 is a prime number for 0 ≤ n ≤ 40. Is there an infinite number of such prime numbers? The same question for the formula n 2 - 79 n + 1601. These numbers are prime for 0 ≤ n ≤ 79.
• Is there an infinite number of prime numbers of the form n# + 1? (n# is the result of multiplying all prime numbers less than n)
• Is there an infinite number of prime numbers of the form n# -1 ?
• Is there an infinite number of prime numbers of the form n? + 1?
• Is there an infinite number of prime numbers of the form n? - 1?
• if p is prime, does 2 p -1 always not contain prime squares among its factors?
• does the Fibonacci sequence contain an infinite number of prime numbers?

The largest twin prime numbers are 2003663613 × 2 195000 ± 1. They consist of 58711 digits and were discovered in 2007.

The largest factorial prime number (of the type n! ± 1) is 147855! - 1. It consists of 142891 digits and was found in 2002.

The largest primorial prime number (a number of the form n# ± 1) is 1098133# + 1.

Enumeration of divisors. By definition, number n is prime only if it is not evenly divisible by 2 and other integers except 1 and itself. The above formula removes unnecessary steps and saves time: for example, after checking whether a number is divisible by 3, there is no need to check whether it is divisible by 9.

• The floor(x) function rounds x to the nearest integer that is less than or equal to x.

Learn about modular arithmetic. The operation "x mod y" (mod is an abbreviation of the Latin word "modulo", that is, "module") means "divide x by y and find the remainder." In other words, in modular arithmetic, upon reaching a certain value, which is called module, the numbers “turn” to zero again. For example, a clock keeps time with a modulus of 12: it shows 10, 11 and 12 o'clock and then returns to 1.

• Many calculators have a mod key. The end of this section shows how to manually evaluate this function for large numbers.

Learn about the pitfalls of Fermat's Little Theorem. All numbers for which the test conditions are not met are composite, but the remaining numbers are only probably are classified as simple. If you want to avoid incorrect results, look for n in the list of "Carmichael numbers" (composite numbers that satisfy this test) and "pseudo-prime Fermat numbers" (these numbers meet the test conditions only for some values a).

If convenient, use the Miller-Rabin test. Although this method quite cumbersome when calculating manually, it is often used in computer programs. It provides acceptable speed and produces fewer errors than Fermat's method. A composite number will not be accepted as a prime number if calculations are made for more than ¼ of the values a. If you randomly select different meanings a and for all of them the test will give a positive result, we can assume with a fairly high degree of confidence that n is a prime number.

For large numbers, use modular arithmetic. If you do not have a calculator with a mod function at hand or the calculator is not designed for operations with such large numbers, use properties of powers and modular arithmetic to make calculations easier. Below is an example for 3 50 (\displaystyle 3^(50)) mod 50:

• Rewrite the expression in a more convenient form: mod 50. When doing manual calculations, further simplifications may be necessary.
• (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Here we took into account the property of modular multiplication.
• 3 25 (\displaystyle 3^(25)) mod 50 = 43.
• (3 25 (\displaystyle (3^(25)) mod 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 ∗ 43) (\displaystyle (43*43)) mod 50.
• = 1849 (\displaystyle =1849) mod 50.
• = 49 (\displaystyle =49).