What is Prime: Definition and 776 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



n


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



n


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





n




{\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
Recent contents Top users
  1. 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
  2. D

    Number theory - show divergence of ∑1/p for prime p

    1. show that the sum of. The reciprocals of the primes is divergent. I am reposying this here under homework and deleting the inital improperly placed post 2. Theorem i use but don't prove because its assumed thw student has already lim a^1/n = 1. The gist of the approach I took is that∑1/p =...
  3. 2

    Prime Obsession or Millennium problems?

    Hello, people. So I am considering getting a book on mathematics (of the "popular book"-ish realm). However, I do not want it to be too much aimed towards the general public (something like Kaku or Hawking would write in Physics). I want to buy one of these two and I am asking for guidance which...
  4. M

    Exploring the Prime Number Theorem: A Comprehensive Guide

    Can I get the link to the prime number theorem?
  5. S

    Every positive integer except 1 is a multiple of at least one prime.

    Homework Statement The problem (and its solution) are attached in TheProblemAndSolution.jpg. Specifically, I am referring to problem (c). Homework Equations Set theory. Union. Integers. Prime numbers. The Attempt at a Solution I see how we have all multiples of all prime numbers in...
  6. anemone

    MHB Prime Pairs: Finding $b-a$ Values

    The numbers $a$ and $b$ are prime and satisfy $\dfrac{a}{a+1}+\dfrac{b+1}{b}=\dfrac{2k}{k+2}$ for some positive integer $k$. Find all possible values of $b-a$.
  7. T

    MHB Please help figure this out: prime numbers largest, smallest, twin primes.

    Guys, please help me figure this out: 1) how to calculate the largest prime less than 300 2) why 35 and 37 are not twin primes? 3) the smallest number divisible by five different primes Any input would be greatly appreciated)
  8. C

    Proof about relatively prime integers.

    Homework Statement Prove that if you have n+1 integers less than or equal to 2n then at least 2 are relatively prime. The Attempt at a Solution the book say integers but I am pretty sure this will only work in the natural numbers. there are n even numbers between 0 and 2n okay and none of...
  9. P

    Why is Two Prime? Exploring Factors

    just a quick question. why is two prime if its has factors, (1+i) and (1-i)?
  10. X

    Is my equation for counting primes unique or similar to existing equations?

    Dear fellow learners, Through an extracurricular project I have found a really cool equation to count primes. The equation can evaluate Pi(x)+Pi(√x)/2+Pi(cubedroot(x))/3+...Pi(nthroot(x))/n I have directly proved my equation so I now it will be accurate 100% of the time. Although the...
  11. Nono713

    MHB Showing the nth prime is primitive recursive

    I've been asked in an exercise to show that the function $f(n)$ which returns the $n$th prime is a primitive recursive function. We've covered the basics of primitive recursion, the primitive recursive schematic notation, addition, multiplication, limited subtraction, bounded products, sums...
  12. Sudharaka

    MHB Prime Artinian Rings are Simple

    Hi everyone, :) Here's a question that I am struggling find the answer. Any nudge in the correct direction would be greatly appreciated. Question: Prove that a prime Artinian ring is simple.
  13. anemone

    MHB Show the result of the sum of a series isn't a prime number

    Show that for an odd integer $m\ge 5$, $\displaystyle {m\choose 0} 5^{m-1}-{m\choose 1} 5^{m-2}+{m\choose 2} 5^{m-3}-\cdots+{m\choose m-1} $ is not a prime number.
  14. F

    Prime Number with Prime Digits

    Is there a name for a prime number whose digits are all prime? The first several that I can think of are 2,3,5,7 and 23, 23 being the first double digit prime whose digits are all prime.
  15. S

    C/C++ C++ programming on prime numbers

    this is the program which i wrote: #include<iostream.h> #include<conio.h> #include<stdlib.h> void prime(int p) { if(p==0||p==1) { cout<<"neither prime nor composite"<<endl; getch(); exit(1); } for(int i=2;i<p/2;i++) { if(p%i==0) { cout<<"composite"<<endl; break; } else...
  16. S

    Solving Relatively Prime Homework Without Fractions

    Homework Statement For integers a,b, and c, if a and c are relatively prime and c|ab, then c|b. Knowing that: For any integers p and q, there are integers s and t such that gcd(p,q) = sp + tq. The hint I'm given is that I should form an equation from the fact that they are "relatively...
  17. Math Amateur

    MHB Primary ideals and localization of prime ideals

    I am reading Dummit and Foote Section 15.4 Localization. Exercise 11 on page 727 reads as follows: ------------------------------------------------------------------------------- Let R_P be the localization of R at the prime P. Prove that if Q is a P-primary idea of R then Q = ^c(^e Q)...
  18. Math Amateur

    MHB Simple problem concerning R[x], R and a prime ideal I

    I am reading Dummit and Foote Section 15.4: Localization. On page 710, D&F make the following statement: ------------------------------------------------------------------------------- "In general, suppose R is a commutative ring. If P is a prime ideal in R[x] then P \cap R is a prime ideal...
  19. Math Amateur

    MHB Localization - Bijections between prime ideals of R and D^-1R

    I am reading Dummit and Foote, Section 15.4: Localization and am currently working on Proposition 38, part 3 (contraction bijection) - see attachments. I am hoping that someone can demonstrate a proof of the following propostion (without - as D&F do - referring to or relying on translating the...
  20. evinda

    MHB {a^k,k is a prime is not contextfree}

    Hi! :) I have to show that the language $L=\{a^{k},\text{ k is a prime }\}$ is not context-free..I thought that I could show this,using the pumping lemma.I took the word $s^{p}$,and said that if we add $i|vy|$ at the length of $s$,it must still belong in $L$..To show that it is not possible,I...
  21. N

    Zeta Function -1 1/2 and prime numbers

    I talked with an old friend of mine. We discussed prime numbers and Ulams Spiral, and the mathematical patterns that surround us all. He brought up something called the Zeta-Function and something about -1 1/2 and how this all related to prime numbers. I did a google search and found some...
  22. mente oscura

    MHB Prime numbers vs consecutive natural numbers.

    An easy question. All "odd" number can be expressed as a sum of consecutive natural numbers. Example: 35=17+18 35=5+6+7+8+9 35=2+3+4+5+6+7+8Question: Demonstrate that prime numbers (except for the "2"), can only be expressed as the sum of two consecutive natural numbers.
  23. Math Amateur

    MHB Radicals and Prime Ideals

    I am reading R.Y. Sharp: Steps in Commutative Algebra, Chapter 3: Prime Ideals and Maximal Ideals. Exerise 3.47 on page 52 reads as follows: ===================================================== Let P be a prime ideal of the commutative ring R. Show that \sqrt (P^n) = P...
  24. G

    Eta prime meson as SU(3) singlet

    I understand that when the quark theory was being developed that SU(3) was used to explain the mesons that were ultimately found to be composed of the up, down, and strange quarks. I also get that the SU(3) is grouped as an octet and a singlet, with the eta prime meson being the singlet. But I'm...
  25. L

    Efficient Prime Factoring Method for Numbers Below the Square Root"

    trust me this is trivial... As a kid I had a teacher fond of asking if numbers were prime. Of course at the time I had no calculator and did not have many primes remembered. I did not even know the less than square root. I came up with a method that made a simple chart of smaller than the...
  26. mathbalarka

    MHB Twin Prime Conjecture : A Brief History of the Present

    I don't know if such thread has been created, all I can find out is one mentioning Zhang's initial bound of $7 \times 10^7$. This has been greatly improved by now so I thought it is worthwhile to post it here as well as the resources which I somehow collected from here and there. History; a...
  27. 1

    2 is the oddest prime of all.

    2 is the "oddest prime of all." Regarding the old humorous "math joke" that 2 is the only even prime, thus it is the "oddest" prime of all. I have a bone to pick with this. I don't think the idea of "even" numbers is any more special than numbers that are divisible by 3 or 5, or anything...
  28. Math Amateur

    MHB Prime Ideals in K[X] - Commutative Algebra Exercise 3.22 (ii)

    I am reading R.Y.Sharp's book: "Steps in Commutative Algebra. In Chapter 3: Prime Ideals and Maximal Ideals, Exercise 3.22 (ii) reads as follows: ------------------------------------------------------------------------- Determine all the prime ideals of the ring K[X], where K is a field...
  29. E

    Finding Prime numbers using Euler's formula

    Homework Statement use Eular's formula to find the greatest prime number under : If I wasn't forced to use this method I would set up a program to loop through checking for primes Homework Equations F(n) = n^2 + n + 41(0 to 39) or depending on your PoV f(n) = n^2 - n + 41(1 to...
  30. Math Amateur

    Why is (x) a prime ideal in k[x,y]?

    Example (2) on page 682 of Dummit and Foote reads as follows: ------------------------------------------------------------------------ (2) For any field k, the ideal (x) in k[x,y] is primary since it is a prime ideal. ... ... etc...
  31. Math Amateur

    MHB Prime ideal (x) in k[x,y]

    Example (2) on page 682 of Dummit and Foote reads as follows: ------------------------------------------------------------------------ (2) For any field k, the ideal (x) in k[x,y] is primary since it is a prime ideal. ... ... etc...
  32. Superposed_Cat

    What is the Fastest Method for Finding Prime Numbers and Combinations?

    Hi, I was wondering what A)the fastest way to find primes is, the fastest I've found so far is the sieve of Eratosthenes. B) The fastest way to find all possible combinations of a set are. e.g. cat-> act,cta,tca,atc,tac,cat any help appreciated. thanks in advance.
  33. Math Amateur

    Primary Ideals, prime ideals and maximal ideals - D&F Section 15.2

    I am studying Dummit and Foote Section 15.2. I am trying to understand the proof of Proposition 19 Part (5) on page 682 (see attachment) Proposition 19 Part (5) reads as follows...
  34. Math Amateur

    MHB Primary Ideals, prime ideals and maximal ideals - D&F Section 15.2

    I am studying Dummit and Foote Section 15.2. I am trying to understand the proof of Proposition 19 Part (5) on page 682 (see attachment) Proposition 19 Part (5) reads as follows...
  35. Math Amateur

    Primary Ideals, prime ideals and maximal ideals.

    I have a problem in understanding the proof to Dummit and Foote Section 15.2, Proposition 19 regarding primary ideals. I hope someone can help. My problem is with Proposition 19 part 4 - but note that part 4 relies on part 2 - see attachment. The relevant sections of Proposition 19 read as...
  36. Math Amateur

    MHB Primary Ideals, prime ideals and maximal ideals.

    I have a problem in understanding the proof to Dummit and Foote Section 15.2, Proposition 19 regarding primary ideals. I hope someone can help. My problem is with Proposition 19 part 4 - but note that part 4 relies on part 2 - see attachment. The relevant sections of Proposition 19 read as...
  37. G

    Is it really true that, for any n > 0 , there is a prime between 2 ^ n

    and 2 ^ n + 2 * n? I have checked it for n from 1 to 39. At n = 40, 2 ^ n is over a trillion, and I no longer have the resources to continue checking. I believe this statement is true. As n gets to 40 or more, would this statement become more probable or less probable by the Prime Number...
  38. G

    Why is Goldbach conjecture that every even = a prime + a prime becomes

    more and more likely to be true the bigger the even? Primes become more rare, so it seems to me this notion is counter intuitive. :confused: A few recent papers all point to that Goldbach becomes more and more likely the higher up you go. A very large even can be the sum of two large odds or...
  39. G

    Is it true that any rule regarding prime numbers eventually fails?

    Other than the fact that prime numbers are infinite?
  40. A

    Proving Prime p≥3 Satisfies pr ≡ 1, 5, 7 or 11 (mod 12)

    Homework Statement If p is a prime and p>3, show that pr\equiv1,5,7 or 11 (mod12) Homework Equations The Attempt at a Solution Do I go about this by knowing that any prime p greater than 3 is of the form 6n+1 or 6n+5? Any direction on how to go about this will be helpful. Thanks.
  41. K

    If p is prime, then its square root is irrational

    Homework Statement Im trying to prove that if p is prime, then its square root is irrational. The Attempt at a Solution Is a proof by contradiction a good way to do this? All i can think of is suppose p is prime and √p is a/b, p= (a^2)/ (b^2) Is there any property i can...
  42. srfriggen

    Prove or disprove: Is 10^1,000 - 9 Prime?

    Homework Statement Prove or disprove: Is 10^1,000 - 9 Prime? Homework Equations The Attempt at a Solution 10^1,000 = 999...91. Is there a way to logically argue to drop the first nine hundred ninety eight 9's and just look at 91 as being a prime?
  43. Math Amateur

    MHB Splitting Fields - Dummit and Foote - Example - page 541 - x^p - 2, p prime

    I am reading Dummit and Foote Section 13.4 Splitting Fields and Algebraic Closures In particular, I am trying to understand D&F's example on page 541 - namely "Splitting Field of x^p - 2, p a prime - see attached. I follow the example down to the following statement: " ... ... ... so...
  44. Z

    Proving the Validity of 5y^2 + 5y + 1 in Prime Numbers

    prove if the statement is true, else form it's negation and prove that is true: ## \forall y \in (x | x \in \mathbb Z , x \geq 1), 5y^2 + 5y + 1 ## I think it's true, but I can't really even get started to prove it I really suck at these and need help please, thank you!
  45. C

    Prime Factorization (Arithmetic)

    Homework Statement Assume n = p_1*p_2*p_3*...*p_r = q_1*q_2*q_3*...*q_s, where the p's and q's are primes. We can assume that none of the p's are equal to any of the q's. Why? Homework Equations The Attempt at a Solution I am completely stuck on this. My understanding of the...
  46. G

    Question about density of prime numbers?

    It is known that prime numbers become sparser and sparser, with the average distance between one prime number and the next increasing as n approaches infinity. Dividing an even number by 2 results in a bottom half from 1 to n / 2 and a top half from n / 2 to n. For a particular sufficiently...
  47. N

    Solvable group: decomposable in prime order groups?

    Hey! From MathWorld on solvable group: But why is that a special case? The way I understand it: the normal series can always be made such that all composition factors are simple, but then the composition factors are both simple and Abelian, and hence (isomorphic to) \mathbb Z_p, i.e. the...
  48. M

    Discover the Largest Known Prime: 2^57,885,161-1

    This news is a little dated, but I still found it interesting and wanted to see what everyone else thought about this years discovery of a new "largest" prime: ##2^{(57,885,161)}-1## its 17,425,170 digits long and would span all 7 harry potter books twice. Written out in plain text it would take...
  49. G

    MHB Fractals in relatively prime integers

    Greetings, humans! (Tongueout) I'm from Ukraine. My English is very bad. So I will use a Google Translate. In 2002, I came up with an interesting piece. I was only 14 years old. I was thinking about fractals and chaos theory, and did not want to learn. Did not want to learn, and were forced to...
  50. matqkks

    MHB Resources for 18yo Students: Prime Number Theorem

    I am looking for resources which explain the prime number theorem to 18 year old students. I am not seeking a proof of the result but something which will have an impact and motivate a student to study mathematics in the future. Can anyone provide or direct me to these resources?
Back
Top