What is Prime numbers: Definition and 155 Discussions

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself.
However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.
The property of being prime is called primality. A simple but slow method of checking the primality of a given number


{\displaystyle n}
, called trial division, tests whether


{\displaystyle n}
is a multiple of any integer between 2 and


{\displaystyle {\sqrt {n}}}
. Faster algorithms include the Miller–Rabin primality test, which is fast but has a small chance of error, and the AKS primality test, which always produces the correct answer in polynomial time but is too slow to be practical. Particularly fast methods are available for numbers of special forms, such as Mersenne numbers. As of December 2018 the largest known prime number is a Mersenne prime with 24,862,048 decimal digits.There are infinitely many primes, as demonstrated by Euclid around 300 BC. No known simple formula separates prime numbers from composite numbers. However, the distribution of primes within the natural numbers in the large can be statistically modelled. The first result in that direction is the prime number theorem, proven at the end of the 19th century, which says that the probability of a randomly chosen number being prime is inversely proportional to its number of digits, that is, to its logarithm.
Several historical questions regarding prime numbers are still unsolved. These include Goldbach's conjecture, that every even integer greater than 2 can be expressed as the sum of two primes, and the twin prime conjecture, that there are infinitely many pairs of primes having just one even number between them. Such questions spurred the development of various branches of number theory, focusing on analytic or algebraic aspects of numbers. Primes are used in several routines in information technology, such as public-key cryptography, which relies on the difficulty of factoring large numbers into their prime factors. In abstract algebra, objects that behave in a generalized way like prime numbers include prime elements and prime ideals.

View More On Wikipedia.org
  1. TartElm

    A Is it required to use the Reimann function to solve the problem?

    The Reimann hypothesis, from what I gather, would answer questions to the distribution of prime numbers. So then, would a thorough breakdown of the distribution of prime numbers and how predictable they are distributed, solve the problem? This predictability makes it possible to determined...
  2. Charles Kusniec

    Discussion on Astronomical Prime Numbers and Re-evaluating the Primali

    Subject: Discussion on Astronomical Prime Numbers and Re-evaluating the Primality of the Number 1 Dear Members of the Physics Forum, I hope this message finds you well. I've been avidly exploring various discussions on prime numbers and came across an intriguing thread on your forum titled "Is...
  3. Kekkuli

    Python Who can find the largest prime number with the own programmed code?

    I announce a playful competition :smile: Who can find the largest prime number with the programmed code? I found the number 2249999999999999981 with the Python code. I first tabulated the truth value of the prime numerosity of numbers smaller than 1.5 billion using Erasthonene's sieve, and then...
  4. M

    A How should I write an account of prime numbers?

    How should I write an account of prime numbers in arithmetic progressions? Assuming this account should be in the form of an essay of at least ## 500 ## words. Should I apply the formula ## a_{n}=3+4n ## for ## 0\leq n\leq 2 ##? Can anyone please provide any idea(s)?
  5. S

    I Union of Prime Numbers & Non-Powers of Integers: Usage & Contexts

    Is there a name for the union of {prime numbers} and {integers that are not powers of integers}? For example, we would include 2, 3, 5, 7, 11... And also 6, 10, 12... But we exclude 2^n, 3^n, ... and 6^n , 10^n , etc. What are some interesting contexts where this set crops up?
  6. M

    Determine (with proof) the set of all prime numbers

    Proof: Let ## p ## be the prime divisor of two successive integers ## n^{2}+3 ## and ## (n+1)^{2}+3 ##. Then ## p\mid [(n+1)^{2}+3-(n^{2}+3)]\implies p\mid (2n+1) ##. Observe that ## p\mid (n^{2}+3) ## and ## p\mid (2n+1) ##. Now we see that ## p\mid [(n^{2}+3)-3(2n+1)]\implies p\mid...
  7. hotAdaptness

    A I think I discovered a pattern for prime numbers

    I wrote a program that implements the pattern and finds the primes automatically. It worked up to 70 million then it crashed because program holds data in RAM so it can be fixed. It found all the primes up to 70 million and found no exception. I won't explain the pattern because its so...
  8. M

    If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that....

    Proof: Suppose ## p ## and ## p^{2}+8 ## are both prime numbers. Since ## p^{2}+8 ## is prime, it follows that ## p ## is odd, so ## p\neq 2 ##. Let ## p>3 ##. Then ## p^{2}\equiv 1 \mod 3 ##, so ## p^{2}+8\equiv 0 \mod 3 ##. Note that ## p^{2}+8 ## can only be prime for ## p=3 ##. Thus ##...
  9. bland

    I Is Riemann's Zeta at 2 Related to Pi through Prime Numbers?

    I just saw that one of the ways of calculating Pi uses the set of prime numbers. This must sound crazy even to people who understand it, is it possible that this can be explained in terms that I, a mere mortal can understand or it is out of reach for non mathematicians?
  10. M

    Find all prime numbers that divide 50

    Proof: Note that all primes less than 50 will divide 50!, because each prime is a term of 50!. Applying the Fundamental Theorem of Arithmetic produces: Each term k of 50! that is non-prime has a unique prime factorization. Since 48, 49 and 50 are not primes, it follows that all primes...
  11. K

    What is the fastest algorithm for finding large prime numbers?

    Dear PF Forum, Can someone help me with the algorithm for finding a very large prime number? In RSA Encryption (1024 bit? 2048?, I forget, should look it up at wiki for that), Private Keys is a - two prime number packet. Now, what I wonder is, what algorithm that the computer use to find those...
  12. docnet

    Cryptography problem involving prime numbers

    Here is my attempt When we raise both sides to the power (p-1)/2, we get x^(p-1)= -1^[(p-1)/2](modp) Looking at p=3(mod4), the possible values of p are {3, 7, 11, 19, 23, 31...}. Putting these values of p into (p-1)/2 we get odd integers. {1, 3, 5, 9, 11, 15...}. So we have x^(p-1) =...
  13. e2m2a

    Consecutive integers and relatively prime numbers

    Summary:: Interested in the history of the proof. Consecutive integer numbers are always relatively prime to each other. Does anyone know when this was proved? Was this known since Euclid's time or was this proved in modern times?
  14. bagasme

    B Aren't There Any Formulas for Prime Numbers?

    Hello all, We know that following formulas failed to produced all prime numbers for any given whole number ##n##: ##f(n) = n^2 - n - 41##, failed for ##n = 41~(f = 1681)## ##g(n) = 2^(2^n) + 1##, failed for ##n = 5~(g = 4,294,967,297)## ##m(n) = 2^n - 1##, failed for ##n = 67~(m =...
  15. Raschedian

    B Do Prime Numbers Follow a Pattern?

    Hello everyone! I was going through a simple high school level mathematics book and got to the following question: n2 - n + 41 is a prime for all positive integers n. You're supposed to find a counter-example and prove the statement false. You could of course sit and enter different...
  16. Philip Robotic

    Prime numbers and divisibility by 12

    Homework Statement Prove that if ##p## is a prime number and if ##p>5## then ##p^2-37## is divisible by ##12## Homework EquationsThe Attempt at a Solution So I think that the number ##p^2-37## should be expressed in a way that we can clearly see that it is divisible by 3 and by 2 twice...
  17. nomadreid

    I |Li(x) - pi(x)| goes to 0 under RH?

    Extremely quick question: According to http://mathworld.wolfram.com/PrimeNumberTheorem.html, the Riemann Hypothesis is equivalent to |Li(x)-π(x)|≤ c(√x)*ln(x) for some constant c. Am I correct that then c goes to 0 as x goes to infinity? Does any expression exist (yet) for c? Thanks.
  18. C

    A Is it possible to locate prime numbers through addition only

    I was reading an old thread about multiplying successive prime numbers adding 1 to obtain another prime number. I have worked with prime numbers for several years now and have developed what I best call a bi-linear advancement. It is an open-ended sieve of Eratosthenes. After many, many hours...
  19. Janosh89

    B Simple Question About Term(s) re: Fermat

    Since Fermat, the French magistrate & noted mathematician, expounded : all odd integers ,(2n+1) where n≥0, are representable by the difference of TWO squares...
  20. Clara Chung

    Analysis question -- Aren't all prime numbers not a product of primes?

    Homework Statement I don't understand the lemma. Homework EquationsThe Attempt at a Solution Isn't all prime number not a product of primes? The lemma doesn't make sense to me... Moreover, if m=2, m-1 is smaller than 2, the inequality also doesn't make sense. Please help me
  21. lfdahl

    MHB Determine all prime numbers p such that the total number of positive divisors of A=p^2+1007 (including 1 and A) is less than 7 .

    Determine all prime numbers $p$ such that the total number of positive divisors of $A = p^2 + 1007$ (including $1$ and $A$) is less than $7$.
  22. lfdahl

    MHB Set of 2015 Consecutive Positive Ints with 15 Primes

    Is there a set of $2015$ consecutive positive integers containing exactly $15$ prime numbers?
  23. M

    How many ways one can put prime numbers to form 3 digit NIP?

    Homework Statement as listed above the question is how many and which three digit NIP can be formed whit the use of prime numbers[/B]Homework Equations nothing currently trying to understand[/B]The Attempt at a Solution well i have found at least 168 primer numbers below 1000 i mean in the...
  24. awholenumber

    B Factoring a number and prime numbers?

    A number can be factored into a product of its component factors A number can be factored into a product of its prime . But, What exactly is a prime number ? Prime numbers are numbers greater than 1 that are evenly divisible only by themselves and 1 Is it a number that can only be evenly...
  25. Janosh89

    B Are Prime Pairs Ending in 9 or 1 Derived from 20x2-1 Centred 10-Gonal Primes?

    45x2+15x +/-1. ... 59;61 ,209;211 ,449;451 ,779;781 ... 45x2- 15x +/-1 ... 29;31 ,149;151 ,359;361 ,659;661 ... Derived from 20x2-1 can only have factors ending in the digit _1, or _9 .
  26. S

    How to Identify Prime Numbers Using Eratosthenes in C#?

    Mod note: added code tags using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { List<int> number = new List<int>(1000); // int list for 1000 numbers...
  27. G

    Checking a proof of a basic property of prime numbers

    Homework Statement Prove: If p is prime and m, n are positive integers such that p divides mn, then either p divides n or p divides m. Is anyone willing to look through this proof and give me comments on the following: a) my reasoning within the strategy I chose (validity, any constraints or...
  28. H

    B Connections with Prime numbers and Quantum Physics?

    Hello I'm hard at work trying to find a pattern for the prime numbers and this keeps cropping up. To be honest though, to me it comes across like pseudo science. I mean I never really hear people talk about it. This seems an obvious thing to look into but I don't know anyone who does. Prime...
  29. F

    What properties do prime numbers exhibit?

    Mod note: moved from a homework section What properties do prime numbers exhibit which can be used in proofs to define them? Like rational numbers have a unique property that they can be expressed as a quotient of a/b. Even numbers have a unique property of divisibility by 2 and thus they can be...
  30. DuckAmuck

    I Question about the gaps between prime numbers

    Is there any prime number pn, such that it has a relationship with the next prime number pn+1 p_{n+1} > p_{n}^2 If not, is there any proof saying a prime like this does not exist? I have the exact same question about this relation: p_{n+1} > 2p_{n}
  31. D

    A Equation with three consecutive prime numbers

    Solve the equation np_n+(n+1)p_{n+1}+(n+2)p_{n+2}=p^2_{n+2} where n\in \mathbb N^* and p_n , p_{n+1} , p_{n+2} are three consecutive prime numbers. ------------------------------------- A solution is n=2,p_2=3,p_3=5,p_4=7. May be other solutions?
  32. J

    A Is this product always greater than these sums?

    I've been working on a problem for a couple of days now and I wanted to see if anyone here had an idea whether this was already proven or where I could find some guidance. I feel this problem is connected to the multinomial theorem but the multinomial theorem is not really what I need . Perhaps...
  33. Ackbach

    MHB Fascinating Discovery about Prime Numbers

    I found this article fascinating. Imagine overlooking something so simple for so long!
  34. G

    Print Highly Prime Numbers in an Input Interval | C Program

    Homework Statement Write a program that will print all highly prime numbers from the input interval <a,b>. Prime number is highly prime if deletion of every digit from right is a prime. Example: 239 is highly prime because 239,23,2 are primes. 2. The attempt at a solution Could someone point...
  35. T

    MHB Prime numbers proof by contradiction

    For prime numbers, $a$, $b$, $c$, $a^2 + b^2 \ne c^2$. Prove this by contradiction. So, I get that $a^2 = c^2 - b^2 = (c - b)(c +b)$ And I get that prime numbers are the product of 2 numbers that are either greater than one, or less than the prime numbers. But I'm unsure how to go from here.
  36. R

    Comp Sci C++ Sum of prime numbers in matrix

    Homework Statement My Program is not showing the sum value or not returning it. A blank space is coming.Why that is so? Homework Equations Showing the attempt below in form of code. The Attempt at a Solution #include<iostream.h> #include<conio.h> Prime_Sum(int arr[30][30],int m, int n); void...
  37. N

    Is This Simple Algorithm the Key to Finding the Next Largest Prime Number?

    I have a simple algorithm that appears to generate many primes (or semi-primes with relatively large factors). By 'relatively large', I mean large in relation to inputs. I have tested this algorithm for small values, and of the forty (six-digit) numbers produced, 22 are prime, 16 are...
  38. N

    Prime Numbers Between Two Quadratics: A Useful Result?

    Would it be a useful result to know there is at least one prime between 16x^2+4x-1 and 16x^2+8x-5 for any odd natural number x?
  39. a1call

    A Is there a formula for generating prime numbers and proving their primality?

    I have figured out a formula that generates prime numbers along with the proof that all such generated numbers are primes. The way it works is that you have to input consecutive prime numbers staring from 2 and ending at some Pn. And no it's not primorial minus or plus 1. Is this of any value...
  40. B

    Convergence of a sum over primes

    I am trying to understand a condition for a nonincreasing sequence to converge when summed over its prime indices. The claim is that, given a_n a nonincreasing sequence of positive numbers, then \sum_{p}a_p converges if and only if \sum_{n=2}^{\infty}\frac{a_n}{\log(n)} converges. I have tried...
  41. K

    Are there prime numbers n for which S=/0?

    We have the set:S={1<a<n:gcd(a,n)=1,a^(n-1)=/1(modn)} Are there prime numbers n for which S=/0?After this, are there any composite numbers n for which S=0? (with =/ i mean the 'not equal' and '0' is the empty set) for the first one i know that there are no n prime numbers suh that S to be not...
  42. K

    MHB Proving Prime Numbers in Quadratic Imaginary Fields

    Hi, I need your help with the next two problems: 1) If p is a prime number such that p\equiv{3}\;mod\;4, prove that \sqrt{-p} is prime in \mathbb{Z}[\sqrt[ ]{-p}] and in \mathbb{Z}[\displaystyle\frac{1+\sqrt[ ]{-p}}{2}] too. 2) 2) We have d > 1 a square-free integer. Consider the quadratic...
  43. G

    Are There Infinitely Many Prime Numbers Written as ak+b?

    Homework Statement Prove that there are infinitely many prime numbers written ##ak+b##, with ##a,b,k## integers greater than 1 Homework EquationsThe Attempt at a Solution Please could you tell me if you agree with that proof ? By contradiction: Assume that there is an integer ##k## such that...
  44. K

    Prime Numbers as Ortho-normal basis for all numbers

    Hi, Can we treat prime numbers as an Ortho-normal basis of "Infinite" dimensions to represent every possible number. Treating numbers as vectors. Thanks.
  45. qpwimblik

    R-Simplex's the number 5 and prime numbers.

    So if you do a search for R-Simplexs you should find that. RSimplex(n,d)=Pochhammer(n,d)/d! Well so to does RSimplex(n,d)=If(n<d, Pochhammer(d+1,n-1)/n!, Pochhammer(n,d)/d!) Or something like that my maths package is down so I'm not sure quite how it works. Anyway the relationship between...
  46. G

    Do Two Primes Divide All Binomial Coefficients for Any n?

    Homework Statement Is it true that for each ##n\geq 2## there are two primes ##p, q \neq 1## that divide every ##\binom{n}{k}## for ##1\leq k\leq n-1##?Examples: For ##n=6: \binom{6}{1}=6; \binom{6}{2}=15; \binom{6}{3}=20; \binom{6}{4}=15; \binom{6}{5}=6.## So we can have ##p=2## and...
  47. P

    The Even Primes: Exploring the Fascinating World of Prime Numbers

    Just want to know if there are applications in the derivation of prime numbers. My instructor and the textbook that we are using seems to be obsessed with it, there is at least one problem about deriving prime numbers in each chapter. And also different versions like palindromic prime, emirp...
  48. PsychonautQQ

    What Is the Product of Primes for the Integer 23?

    Homework Statement My textbook says any integer greater than 1 is a product of primes. Wouldn't that mean that there are no prime numbers? What is the product of primes that create the integer 23? Homework Equations The Attempt at a Solution