Algebra

Prime numbers

Q: Can a negative number be prime?

No, the prime numbers are always positive.

Q: Is 2 the only even prime number? If yes, then why?

Yes, 2 is the only even prime number, because all other even numbers are a multiple of 2.

Q: How long is the largest known prime number?

The largest known prime number to date has 24,862,048 digits.

Q: What is the one number that is co-prime to all numbers?

1 is the only number that is co-prime to all numbers.

Q: What is a factor?

A factor is a number that completely divides another number with no remainder.

Written by Prerit Jain

Updated on: 15 Aug 2023

Prime numbers

Introduction

Natural numbers known as prime numbers may only be divided by one (1) and by the number itself. In other terms, prime numbers are positive integers larger than one that only include the number itself and the number’s first digit as factors.

In this article we shall see how Euclid’s theorem and its proof, Wilson’s theorem, Euler’s theorem, and Goldbach’s conjecture and its status are related to prime numbers. We will see what composite numbers are and different topics and history of prime numbers.

Looking to Learn Math? Book a Free Trial Lesson and match with top Math Tutors for concepts, homework help, and test prep.

Theorems and Properties of Prime Numbers

● Euclid’s theorem and its proof

This theorem proves that there are infinite primes

Proof:

1.Assume there are $n$ finite primes, with ${p_n}$ being the greatest.

2.Take into account the sum of them, plus one: $N = {p_1}......{p_n} + 1$ .

3. $N$ cannot be divided by any of the p I by design.

4. Therefore, it is a prime itself or is divisible by a prime greater than ${p_n}$ proving that there are infinite primes.

● Wilson’s theorem and its proof

According to the Wilson Theorem, $p$ is considered a prime number if and only if the sum of all positive integers smaller than $p$ is one less than a multiple of number $p$ . This applies to every natural number larger than 1 if $p$ .

Proof:

Given that $p > 1$ and suppose $p$ is prime, $k \in \{ 1,........,p - 1\}$ and there are integers $a$ and $b$ in a way that

$\begin{array}{l}ak + bp = 1\\or\\ak = 1(\bmod p)\end{array}$

Reducing $a(\bmod p)$ we get,

$\begin{array}{l}1.(p - 1)\\ \Rightarrow - 1(\bmod p)\\ \Rightarrow (p - 1)! = 1.2....(p - 2).(p - 1)\\taking(p - 1)! = - 1(\bmod p)\end{array}$

We rewrite the equation as $(p - 1)! + 1 = kp$

Suppose $p = ab$ . We may take $1 \le a,b \le p$ . If $a = p$ then factorization become trivial, suppose $a < p$ then $a|(p - 1)!$ and $a|p$ .

So,

$\begin{array}{l} \Rightarrow (p - 1)! + 1 = kp\\ \Rightarrow a|1\end{array}$

Which means $a$ is 1.

● Euler’s theorem

The Euclid Euler Theorem states that an even perfect number may be expressed by the formula $({2^n} - 1) * \frac{{{2^n}}}{2}$ . where ${2^n} - 1$ is a Mersenne prime number and $n$ is a prime number. It is the result of combining a Mersenne prime number with a power of two. A link between a Mersenne prime and an even perfect number is established by this theorem.

Difference Between Prime Number and Composite Number

Numbers with more than two elements are known as composite numbers. Composite numbers are non-prime numbers that may be divided by more than two other numbers.

Examples of composite numbers:

12, factors are: 1,2,3,4,6.

14, factors are: 1,2,7,14

Prime Numbers and Co-prime Numbers

The HCF (Highest Common Factor) of co-prime numbers, also known as substantially prime numbers, is 1. In other terms, two numbers are co-prime if they only share the number one as a common element.

A number that has just itself and the number one is said to be a prime number. Co-primes, on the other hand, are thought of in pairs, and two numbers are co-prime if they only have one common element.

Determine the factors of the number first, then the co-prime of that number. Next, pick any number and determine the variables that make up that number. The given number’s co-prime numbers are all those that have just the number one as a common element.

What Does “Relatively Prime” Mean?

When two numbers have just one in common, or if there is no other value with the same value as one, you cannot divide them both and obtain zero as the remainder, two numbers are said to be relatively prime.

A and B are relatively prime numbers if the only component they have in common is 1. The pair (a, b) in this instance is considered to be relatively prime. These figures don’t necessarily have to be prime numbers. Additionally, two composite numbers, such as 9 and 10, can be substantially primes. Coprime or mutually prime numbers are other names for relatively prime numbers.

Finding the HCF of the numbers allows us to determine whether or not two numbers are relatively prime. The two integers are referred to as relatively primes if the HCF is 1. List all the contributing elements, then choose the one with the highest common factor between the two integers to determine their HCF.

Prime Number Distribution and Density

The asymptotic distribution of prime numbers is described by the prime number theorem. It provides a broad overview of how primes are distributed among positive integers and notes that as positive integers get larger, the prevalence of primes declines. According to the informal theorem, there is a roughly equal chance that any randomly chosen positive integer between zero and a big number $N$ and the probability that a selected number is prime is $\frac{1}{{\ln N}}$ .

The Gauss’s observation is: $\mathop {\lim }\limits_{x \to \infty } \frac{{\pi (x)}}{{\frac{x}{{\ln x}}}} = 1$

This is also called the prime number theorem.

The Sieve of Eratosthenes

The Sieve of Eratosthenes is a technique for identifying prime and composite numbers in a collection of numbers. Greek mathematician Eratosthenes developed this technique in the third century B.C.

Steps to find prime numbers from 1to 100:

Step 1: List all natural numbers from 1 to 100 in a row and a column, as illustrated in the image below.

Step 2: Put a cross over 1 in step 2 since it is neither a prime nor a composite.

Step 3: Next, cross all the multiples of 2, such as 4, 6, 8, 10, 12, and so on, and encircle the number 2, which is a prime number. due to the composite nature of all multiples of 2.

Step 4: Next, draw a circle over the number 3 and a cross over each of its multiples, including 6, 9, 15, 21, and so on. Since all of its multiples other than 3 are composite.

Step 5: Once more, circle the number 5 (which only has two components) and cross off all of its multiples.

Step 6: At this point, surround 7 and cut all of its multiples.

Step 7: Circle 11 and cross every multiple of 11

Step 8: Keep going until all of the numbers are crossed or surrounded.

History of Prime Numbers

The study of prime numbers dates back thousands of years. Several findings on prime numbers were proven in Euclid’s “Elements,” which was published around 300 B.C. Euclid asserts that the number of prime integers is unlimited. The Fundamental Theorem of Arithmetic, which states that every integer can be expressed as a unique product of primes, is also shown by Euclid. In “Elements,” Euclid uses Mersenne primes to provide a solution to the conundrum of how to construct a perfect number, which is a positive integer equal to the sum of its positive divisors. A Mersenne prime is a prime that can be figured out using the formula $2n - 1$ .

No more study on prime numbers was done in the Dark Ages, when knowledge and science were banned. Mathematicians like Fermat, Euler, and Gauss started investigating the patterns seen in prime numbers in the 17th century. Math was transformed by the hypotheses and ideas advanced at the time, some of which remain unproven now.

Prime Numbers Chart

The primes numbers charts for

1. between 1 to 100

2. between 1 to 200

3. between 1 to 1000,

Are as follows:

How to Find Prime Numbers

● Prime factorization:

Step 1: Determine the provided number’s factors first.

Step 2: Determine how many components that number has.

Step 3: It is not a prime number if there are more than two elements.

● How to find if a large number is prime?

Step 1: Verify the number’s units’ placement. It is not a prime number if it ends in 0, 2, 4, 6, or 8.

The second step is to calculate the number’s digit sum. A number is not a prime number if the total is divisible by three.

Step 3: Once steps 1 and 2 have been proven to be false, locate the square root of the supplied integer.

Step 4: Subtract the provided integer from its square root by each prime number below it.

Step 5: A number is not a prime number if it can be divided by any prime number less than its square root; otherwise, it is a prime number.

Is 1 a Prime Number?

In accordance with the definition of a prime number, a number must have precisely two components in order to qualify as a prime number. However, the sole component in number one is the number one itself. As a result, 1 is not regarded as a prime number.

Is 1 a composite number since its not a prime number?

The definition of composite numbers contains the solution to this question as well. A composite number is a natural number that has more than two positive elements, under the definition. However, 1 only has 1 component, which is 1 itself. Thus, one is not a composite number.

Applications of Prime Numbers

● When it comes to cyber-age security, we frequently employ and rely on prime numbers.

● Utilizing the peculiar mathematical feature of primes for encryption and decryption

● To create error-correcting codes for use in communications, they are utilized. They make sure that automated message correction is delivered and received.

● The foundation for developing public-key cryptography techniques is primes.

● They’re employed in hash tables.

● They can also be employed to produce pseudorandom numbers.

● The design of rotor machines also makes use of primes. A number on one rotor is either coprime or prime to the number on another rotor. By doing so, the entire cycle may be generated before trying any different rotor locations.

● The RSA encryption system computes with primes.

Famous Prime Numbers

● Mersenne primes

A prime number that may be expressed in the form ${2^n} - 1$ is known as a Mersenne prime. For instance, the Mersenne prime number 31 can be represented as ${2^5} - 1$ . The first five Mersenne primes are 3, 7, 31, 127, 8191.

● Sophie Germain primes

If both $p$ and $2p + 1$ are primes, then a prime p is said to be a Sophie Germain prime.

Some examples are: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, …

● Fermat primes

Fermat prime, a prime number of the form ${2^{2n}} + 1$ for $n$ , where $n$ is a positive integer. For example, Fermat prime is ${2^{2.2}} + 1 = {2^4} + 1 = 16 + 1 = 17$ which is prime.

Some Facts about Prime Numbers

● The lowest prime number is 2.

● The only even prime number is 2, which is unique.

● The only consecutive prime numbers are 2 and 3.

● A whole number, excluding 0 and 1, is either a prime number or a composite number.

● Not every odd number is a prime number. Examples include 9, 15, etc.

● Beyond 5, no prime number ends in a 5.

● As the number increases, prime numbers become more uncommon.

Conclusion

In our everyday lives as well as routine mathematical sums and difficulties, prime numbers are actually highly important. The world of factors and multiples has been given a magnificent gift by their inception. And it is due of their existence that we now know a great deal of unique information about other numbers, such as the rules for different numbers’ divisibility. Additionally, it has made it incredibly simple and pleasant to calculate complex sums. Most significantly, the prime numbers today serve as a cornerstone of the Number System, one of the branches and the core subject of mathematics, without which occasional pointless attempts at simple computations would have continued.

Sample Examples

Example 1: Find the prime numbers in the following list: 5,28,4,9,39,44,121,47.

Solution 1:

The prime numbers are as follows:5,47

Since,28 has factors 1,2,14,7,4,28.

4 has 1,2,4.

9 has 1,3,9.

39 has 1,3,13,39.

44 has 1,2,22,4,11,44.

121 has 1,121,11

Example 2: What are the prime numbers between 10 and 20?

Solution 2:

The prime numbers are 11,13,17,19.

Example 3: What is the lowest prime number between 70 and 80?

Solution 3:

The lowest prime is 71.

Example 4: Find out if 101 is a prime number.

Solution 4:

Yes, since the only factors of the number are 1 and itself it is a prime number.

Example 5: Using the Fermat prime formula find the prime number when $n$ is 13.

Solution 5:

The formula is ${2^{2n}} + 1$ since $n$ is 13, plugging in the value we get ${2^{2.13}} + 1 = {2^{26}} + 1 = 67108865$

Looking to Learn Math? Book a Free Trial Lesson and match with top Math Tutors for concepts, homework help, and test prep.

FAQs

1. Can a negative number be prime?

Ans: No, the prime numbers are always positive.

2. Is 2 the only even prime number? If yes, then why?

Ans: Yes, 2 is the only even prime number, because all other even numbers are a multiple of 2.

3. How long is the largest known prime number?

Ans: The largest known prime number to date has 24,862,048 digits.

4. What is the one number that is co-prime to all numbers?

Ans: 1 is the only number that is co-prime to all numbers.

5. What is a factor?

Ans: A factor is a number that completely divides another number with no remainder.

References

Wells, D. G. (2005). Prime numbers. Hoboken: Wiley.

Ingham, A. E., & Ingham, A. E. (1990). The distribution of prime numbers (No. 30). Cambridge University Press.

Adleman, L. M. (1980, October). On distinguishing prime numbers from composite numbers. In 21st Annual Symposium on Foundations of Computer Science (sfcs 1980) (pp. 387-406). IEEE.

Written by

Prerit Jain

See our editorial process Meet our Review board

Share article on