What is Primes: Definition and 297 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. E

    Primes as Energy levels (eigenvalues of a certain operator)

    "primes" as Energy levels...(eigenvalues of a certain operator) I have heard about the Riemann Zeta function to be some kind of physical partition function..my question is..could we consider primes as "Energy levels" (eigenvalues) of a certain partition function or operator?..in the form that...
  2. M

    Proving the Uniqueness of the Sum of 3 Primes

    if u have 3 primes: x,y,z then prove its sum m=x+y+z is unique ? Thank you
  3. R

    Twin Primes of the form (8n+5,8n+7)

    Conjecture If 8n+5 and 8n+7 are twin primes then their product divides S_{4n+3} where S_{n} = 6S_{n-1} - S_{n-2} \mid S_{0} = 0 Prove or disprove
  4. D

    Find a List of Primes up to 10^9 - No Generator Needed

    I need a list of primes up to at least 10^9 if possible. I don't want a program that will generate it as it will take too long. Does anyone know where on the net I can find a list that's already compiled? The largest I can find so far is 10^7. The list doesn't have to be fancy, just the primes...
  5. D

    Sequence of Primes: Concluding Divergence for All e>0

    From the fact that \sum_{\mathbb{P}}\frac{1}{p} diverges, how do I conclude that the sequence \frac{n^{1+e}}{p_n} diverges for all e>0? (p=prime, P_n=nth prime)
  6. R

    Relate Mersenne Primes To Sq Triangular Nos.

    Conjecture, For p>2, the 2^(p-1) th square triangular number is divisible by M_{p} if and only if M_{p} is prime. I checked this for 2<p<27. For instance the first four square triangular numbers are 0,1,36 and 1225 and the fourth is divisible by . PS In fact it appears that if is prime then...
  7. E

    Primes as roots of same function

    It,s proven that there can not be any Polynomial that gives all the primes..but could exist a function to its roots are precisely the primes 8or related to them) if we write: f(x)=\prod_{p}(1-xp^{-s})=\sum_{n=0}^{\infty}\frac{\mu(n)}{n^{s}}x^{n} wher for x=1 you get the classical...
  8. N

    Primes vs. Integers: Are There More?

    I was having this discussion in my math class today, and my teacher said that it was not something that he couldn't explain in a manner that we would understand. So the question is, are there more positive integers than primes, or no?
  9. -Job-

    Exploring Alternative Prime Sequences

    Other "primes" If, instead a defining a prime as an integer divisable only by 1 or itself, we define it as an integer not divisable by a number other than 1, 2, half of itself, or itself, (numbers not being divisable by 2 still "able" to be primes) then we generate a new "prime" sequence: 1...
  10. S

    Primes, Complex-Contours, and Reimann

    I'm working on understanding the following relation which was referenced in the Number Theory Forum some time ago: x-\text{ln}(2\pi)-\sum_{\rho} \frac{x^{\rho}}{\rho}-\frac{1}{2}\text{ln}(1-\frac{1}{x^2})= -\frac{1}{2\pi...
  11. D

    Algorithmic complexity of primes

    Every number can be considered a bit string. For a bit string one can define some algorithmic complexity (the shortest algorithm/program that reproduces the desired bit string). Can something be said, in general, about difference in complexity for primes as compared to composites?
  12. C

    Sine Waves and Primes: Exploring the Connection Through Music

    Hi folks. I'm back to make a fool of myself again. It seems that I have a proof that the 'music' of the primes is caused by the interaction of a collection of sine waves. However, I have no idea whether this is old hat, trivial or interesting. Can somebody here tell me? PS. I don't know why...
  13. J

    Infinite primes using Quadratic Residues

    I've been able to prove that the set {8n+7} has infinite primes by manipulating Fermat's Theorem, but I'm trying to reprove it using quadratic residue and Legendre Polynomials. I've been able to show that for p=8n+7, (2/p)=1 and (-1,p)=-1 So it follows that (-2/p)=-1. And that (-2/p)=1 iff...
  14. A

    Euler's Method of proving primes r infinite

    I somewhere read that Euler proved that primes are infinite by proving that the series 1/2 +1/3 + 1/5 +... diverges. Can anybody tell the proof? Aditya
  15. J

    Exploring Twin Primes Conjecture

    Bear with me. I'm new to forum and don't yet know all protocol. My question concerns twin primes. The previous thread on this topic seems to be closed. My question is this: When considering the Twin Primes Conjecture, has anyone researched the idea that (heuristically speaking) there is...
  16. S

    Proving Twin Primes with n and n+2 mod n(n+2)

    1.) Show that (n+1)! = 2(n-1)! mod n+2 I finished this one. Actually very easy. 2.) Let n > 2 be odd. Prove that if 4[(n-1)! + 1] + n = 0 mod n(n+2) holds, then n, n+2 are twin primes. Hint says to use the previous problem. I don't even know what to do for this problem. 3.) Prove the...
  17. E

    Pairs of primes separated by a single number are called prime pairs

    here's one more: pairs of primes separated by a single number are called prime pairs. Example: 17 and 19 are a pair. Prove that the number between prime pair is always divisible by 6 (assuming both numbers are greater than 6).
  18. V

    Modulo, congruences and primes - the love story

    Can somebody please give me a hint as to how to do the following proof please? I have no idea what to use or where to start :( Suppose that p is a prime and a is an integer which is not divisible by p. Prove that there exists an integer b such that ba is congruent to 1 mod p^2. Thank you. T
  19. C

    Sieving for Primes - A Program to Find Primes in Any Range

    Sieving for Primes For a while now I've been messing about in a spreadsheet trying to make sense of the pattern of the primes. I've at last managed to construct a simple programme that will sieve a range of numbers leaving only the primes. But I'm wondering just what it is I've done, whether it...
  20. N

    Why are there infinitely many primes of the form 4n+1?

    I have heard a lot of talk about primes in the form of 4n+3 being infinite, but no one can seem to prove that 4n+1 is infinte. Why is this? Also, if someone disproved it, wouldn't that mean that all primes after a certain number had to be in the form of 4n+3
  21. P

    What is the connection between the Riemann hypothesis and prime numbers?

    Hi, When I hear about the Riemann hypothesis, it seems like the first thing I hear about it is its importance to the distribution of prime numbers. However, looking online this seems to be a very difficult thing to explain. I understand that the Riemann Hypothesis asserts that the zeroes of...
  22. M

    What is the relationship between primes and the distribution of factors?

    "A way of conceptualizing the nature of primes..." We know Eratosthenes observed that the primes occur at 6n+-1. We also know that Ulam's spiral is considered interesting because it visually displays a 'striking non-random appearance' in the distribution of primes. What strikes me...
  23. T

    Are Primes of the Form 4n+1 Infinite?

    I have proved the primes of the order 4n+3 are infiinite but can not prove that primes of the form 4n+1 are infinite.please help prove that primes of the form 4n+1 are infinite.
  24. T

    Prove that primes of the form 4n+1 are infinite

    prove that primes of the form 4n+1 are infinite . send the proof at tamalkuila@gmail.com
  25. M

    Expressing Natural Numbers as Sum of Primes

    Is it possible to express all natural numbers greater than 2 as the sum of N unique prime numbers? For example, 6 = 2 + 3 and 18 = 13 + 5.
  26. A

    Proving infinately many primes 12k-1

    This is a particularly fun problem! Its on a homework that I already turned in. I used the proof by contradiction method. I just need a clarification point. I started by assuming finite number of primes of form 12k-1. suppose N = (6*P1*P2...*Pn)^2 - 3 and set the congruence...
  27. S

    Is There a Proven Method for Finding Prime Numbers?

    It was really close, perhaps the ways you can wright n on is >= the n-1:th prime. But how could i ever prove it?
  28. B

    Infinetely many primes of the form 3n+1

    prove that there are infinetely many primes of the form 3n+1 we used : Assume there is a finitely # of primes of the form 3n+1 let P = product of those primes.. which is also of the form 3A+1 for some A. Let N = (2p)^2 + 3. Now we need to show that N has a prime divisor of the form...
  29. N

    How many primes are there in a certain range of numbers?

    Hi, what would be the best estimate in the # of primes between 10^{100} and 10^{101} thanks
  30. C

    Merseinne Primes: Question from a Maths Dunce

    Question from a mathematics dunce. I recently read that Merseinne primes are searched for using 2^x -1 where x is a number. Is this correct? If so why not use 6n+/-1 instead?
  31. T

    Primes in ring of Gauss integers - help

    Primes in ring of Gauss integers - help! I'm having a very difficult time solving this question, please help! So I'm dealing with the ring R=\field{Z}[\zeta] where \zeta=\frac{1}{2}(-1+\sqrt{-3}) is a cube root of 1. Then the question is: Show the polynomial x^2+x+1 has a root in F_p if...
  32. R

    Generalized Pell Equation and Primes

    I have a conjecture that the equation X^2 - 2Y^2 = P has solutions in odd integers if P is a prime of the form 8*N+1. I know of a paper that requires one to find Q such that Q^2 = 2 mod P inorder to solve these equations using continued fractions. To get to first base in proving my conjecture...
  33. Z

    Large Twin Primes: Find & Submit 100 Digit Primes

    Hi hi, I've been messing about with primes for the last couple of weeks now to try and generate very strong primes for my RSA project. I've made an algorithm which generates a 100 digit prime within about 3 seconds. For my own amusement I thought I'd add a little check to see if any prime I...
  34. Z

    RSA Encryption: Finding Primes to Make Decryption Difficult

    I'm working on encrypting a small message using RSA. Are there any types of primes or primes of particular property that would make RSA decryption particularly difficult? Furthermore are there any better ways that just randomly trying to factorise to break RSA encryption or is there some...
  35. P

    Can Prime Numbers x Satisfy x^2 = v^3 + 1?

    Hey everyone, I need help on this problem: Find all prime numbers x such that x^2 = v^3 + 1 for some integer v. Thanks a lot for your help, i appreciated.
  36. Z

    Why Must m Be a Power of 2 for 2^m + 1 to Be Prime?

    I've been asked to research primes of the form 2^m + 1, I've found all the known primes but now I've been asked to find out why m must be of the form 2^x for some natrual number x for 2^m + 1 to be prime. I've found quite a lot on this but nothing that clearly proves it, can anyone give me a...
  37. G

    Finding primes given a condition

    Hi, I need help solving this problem. The question asks me to find all prime numbers p such that p^2 = n^3 + 1 for some integer n.
  38. C

    Primes and the Geometric Distribution

    Given the probability of flipping a heads with a fair coin is \frac{1}{2}, what is the probability that the first heads occurs on a prime number?
  39. Gokul43201

    Cicada Life Cycles: Why Evolution Chose Prime Numbers

    Know why the cicada have 13 and 17 year life cycles ? Is there a reason why evolution picked prime numbers for their life-cycles ? Check out this neat article in the Post : http://www.washingtonpost.com/wp-dyn/articles/A61426-2004May2.html
  40. maverick280857

    Is the number of twin primes really infinite?

    Hi I've been wondering...the conjecture which states that the number of twin primes is infinite has neither been proved nor disproved so far. We know that the number of primes is infinite and I have come across two methods of proving this. My question is: why can't we actually prove that...
  41. C

    Prove that the sum of two odd primes will never result in a prime?

    How can I prove that the sum of two odd primes will never result in a prime? Would this be proof?: Proof by contradiction: The sum of two odd primes will sometimes result in a prime. This is true because 2 + 3 = 5, which is a prime. So since this is true, does this proof the...
  42. Loren Booda

    Partitioning with Primes: Comparing P(n) and P'(n)

    If a partition P(n) gives the number of ways of writing the integer n as a sum of positive integers, comparatively how many ways does the partition P'(n) give for writing n as a sum of primes?
  43. suyver

    Sum of 1/primes for all primes

    Maybe most of you have seen this before, but I find it cool and that's why I thought I share it with you. :smile: Lets look at the sum \sum_{p\leq N}\frac{1}{p} where p represents only prime numbers. If I calculate the value for this sum when taking into account all prime numbers < 105...
  44. Loren Booda

    Real primes as complex composites

    There are many occurrences where real primes are composites when including complex factors with integral magnitude components, e. g. 2=(1+i)(1-i); 1 X 2 5=(2+i)(2-i); 1 x 5 . . . Using complex numbers gives no insight, though, into a formula for prime distribution. Both sets of...
  45. anil

    Exploring Mersenne Primes: How Big Are They?

    A prime number is a positive ineger greater than 2 whose only integer divisors are itself and 1. A Mersenne prime in of the form 2^(n) - 1 where p is a prime. For example 2^(5) - 1 = 31 is a Mersenne prime. One of the larger Mersenne prime is 2^(216091) - 1. Estimate the number of decimal digits...
  46. H

    Proving Prime Numbers: Understanding the Non-Divisibility Theorem in Mathematics

    Hello everyone, My first post on these forums and I was wondering if I could have some assistance/direction with a problem: Prove that if p is a prime number and a and b are any positive integers strictly less than p then a x b is not divisible by p. The first thing I thought to myself...
  47. A

    Uncovering the Rule of 'Cyclic' Primes

    1/7 = .142857... (repeated) 2/7 = .285714... 3/7 = .428571... 4/7 = .571428... 5/7 = .714285... 6/7 = .857142... So, you get all n/7 from the same 'cycle' of 6 digits. Let's call 7 a 'cyclic' integer. The next cyclic integers are 17, 19, 23,... They are all prime. But 11, 13, or 37 are...
Back
Top