Primes Definition and 298 Threads

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. C

    Prove sum of two primes is even

    Homework Statement Prove: If a and b are prime numbers larger than 2, then a + b is even. The Attempt at a Solution Can i just say that prime numbers larger than 2 are odd and then prove that the sum of 2 odd numbers is even. And can i say that prime numbers larger than 2 are odd because...
  2. S

    Integer factorization given enough primes

    I realize that this might seems to be a strange question, but after doing some coding i realized the following. to brute force the factorization of all numbers less than one million takes around 665 million tests (i.e. does this number divide the original). to do it "smarter" (least i...
  3. M

    Primes whose digits sum to a prime

    Is there a name for prime numbers whose digits sum to a prime number? For example, the prime 83 gives 8+3=11, a prime. Is there anything known about these primes, e.g. are there infinitely many of them? Thanks, M
  4. C

    Uncovering the Mystery of Euclid's Proof of Infinite Primes

    I am trying to understand Euclid's proof of infinite primes. So let's say we have a finite list of primes n1, n2 ... N where N is the largest prime . Then we take the product of all of these prime numbers, and we will call it Q . Then we add 1 to it . so this number is either prime or...
  5. Y

    Totient function and distinct primes.

    It is true that phi(pq)=(p-1)(q-1) when p and q are distinct primes, but is it true that given phi(pq) = (p-1)(q-1) then p and q have to be distinct primes? It seems intuitive, but I'm having some difficulty proving it. Also, if this was true, is it possible to generalize this into more than 2...
  6. Y

    Euler's proof of infinite primes and his product formula.

    From what I had read, Euler had originally proved the infinitude of primes through proving his product formula and equating the primorial to the divergent harmonic series. \sum^{\infty}_{n=1}\frac{1}{n^{s}} = \prod^{\infty}_{p}\frac{1}{1-p^{-s}} where p ranges through the primes. However, the...
  7. J

    What is the approximate number of primes between 1 and a given limit?

    Primes between 1 and a limit! I just discovered something cool! I found out a method to find a close approximate to the number of primes between 1 a certain limit. If n is the limit, then number of primes is approximately equal to n/(natural log of n). For example, number of primes between 1...
  8. T

    Facinating experiment with primes and resulting theory

    I had an idea a while back and did an experiment concerning primes. It began with the idea that the distribution of prime numbers must be somehow determinable. So I used photoshop and created a white line several pixels wide and several million pixels long, each pixel along the length...
  9. JeremyEbert

    Music of the Primes: Maths Through Musical Patterns

    great article http://plus.maths.org/content/music-primes
  10. R

    Prove infinitude of primes that satisfy these properties

    Homework Statement Hi. I need to prove (or at least make a conjecture) about the infinitude of primes in these cases. 1) N^2+2 2) N^2-2 3) N^2+2N+2 4) N^2+3N+2 Homework Equations none? The Attempt at a Solution Already solved for number 4. This is always even, therefore there is not an...
  11. P

    Solving x^2=1 (mod pq) with Odd Primes

    Homework Statement The idea of this problem is to investigate the solutions to x^2=1 (mod pq), where p,q are distinct odd primes. (a) Show that if p is an odd prime, then there are exactly two solutions (mod p) to x^2=1 (mod p). (Hint: difference of two squares) (b) Find all pairs...
  12. R

    [number theory] product of co primes congruent to 1 (mod m)

    Homework Statement Let b1 through b_phi(m) be integers between 1 and m that are coprime to m. Let B be the product of these integers. Show that B must be congruent to 1 or -1 (mod m) Homework Equations None. The Attempt at a Solution Well, I know that the quantity B appears during the...
  13. D

    What is the significance of k being a multiple of 2 or 3?

    Let p,q be two different primes from 5 onwards (not 2 or 3). Let p be the biggest of the two. The difference of squares p^2 - q^2, since p,q are both odd, is always a multiple of 8 (easy to prove). So take the integer k = (p^2 - q^2) / 8. It turns out that k seems to be (says friend computer)...
  14. C

    Proof using primes, divisibility, and sum of squares

    Homework Statement I have to prove or disprove the following: Part a) If p is prime and p | (a2 + b2) and p | (c2 + d2), then p | (a2 - c2) Part b) f p is prime and p | (a2 + b2) and p | (c2 + d2), then p | (a2 + c2) Homework Equations The Attempt at a Solution Part a)...
  15. I

    Significance of calculating non primes in sequence.

    Instead of using a sieve to remove non-primes from the sequence. 6x-1 x =0 to x=n 6x+1 x=0 to x= n What if you calculate and remove the non-primes. I have determined how to calculate the non-primes in this set. By subtracting them from the entire set you are left with all primes. I find this...
  16. S

    Proving Sum of Two Primes is Never Twice a Prime

    Prove that sum of two primes can never be twice a prime p.s: find the actual edited q in 4th post belowsorry for the mistake
  17. A

    How do I prove that the Dirichlet density of primes of the form n^2 +1 is 0?

    How do I prove that the Dirichlet density of primes of the form n^2 +1 is 0? I can't find an way to approach the question - all my attempts so far have hit dead ends - just need a starting direction and I should be able to solve it (I hope!) One approach I have tried is: n^2+1 prime...
  18. H

    Relation between Primes: Proving (2m-1, 2mn-1/2m-1) = 1

    Prove, that if (m,n) = 1 // m and n are two different primes then (2m -1, 2mn -1/2m -1) = 1
  19. K

    Homomorphisms, finite groups, and primes

    Homework Statement 1. Let G and H be finite groups and let a: G → H be a group homomorphism. Show that if |G| is a prime, then a is either one-to-one or the trivial homomorphism. 2. Let G and H be finite groups and let a : G → H be a group homomorphism. Show that if |H| is a prime, then a...
  20. A

    How Can a Number Be Written as a Sum of Squares or Primes?

    Hi All, So I was just wondering if there is a formula for the number of ways a number can be written as a sum of squares?(Without including negatives, zero or repeats). For example 5=2^2+1^2. (There is only one way for 5). Second question along this line is: In how many ways can a number...
  21. B

    Infinitely many primes in Q[Sqrt(d)]

    Hello PhysicsForums people! Could someone show me how there are inifintely many primes in Q[Sqrt(d)]? I figure this will be very similar to the proof of there being infinitely many primes in Z. I cited the above from Wikipedia -Prime Number - The Number of Prime Numbers
  22. S

    C/C++ Finding Primes Using the Sieve of Eratosthenes

    I have been trying to write a program whose function is to find all of the prime numbers between 0 and n using the "Sieve of Eratosthenes" method. (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) using bit manipulation and bit arrays and the print out the number of primes found, the first...
  23. J

    Find and Test Primes using the Chinese Remainder Theorem and Binary Search

    The Chinese remainder theorem tells us that the system of equations: \begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align} Uniquely determines all numbers in the range: X<N=n_1n_2\ldots n_k and that all solutions are...
  24. ╔(σ_σ)╝

    Proof of the irrationality of the square root of primes ?

    Homework Statement If p is prime \sqrt{p} is prime. Are there flaws in my proof ? Homework Equations The Attempt at a Solution Assume \sqrt{p}=\frac{m}{n} and gcd(m,n)=1 p = \frac{m^{2}}{n^{2}} Since p is an integer n^{2}|m^{2} but gcd(m,n)=1 Therefore...
  25. J

    Can Linear Combinations of Primes Model Unique Solutions in Modular Arithmetic?

    Was thinking a bit about linear combination of primes and my conclusions are bellow. I presume their is some theorem to capture this but I don't know it's name. If p1 p2 are primes and n1 or n2 are positive integers, then there should be unique a minimum n1 n2 pair such that: x=p_1n_1+p_2n_2...
  26. Z

    Sum over primes asymtotics

    is the following asymptotic approximation valid whenever dealing sums over primes ?? \sum_{p\le x}f(p) \sim \int_{2}^{x}\frac{f(x)dx}{log(x)}
  27. M

    Twin Primes: Occur in Pairs, 90k+11/13/17/19 Proven?

    Twin primes may occur in pairs - i.e. 11, 13, 17, 19. A cursory check seems to indicate that they have to be of the form 90k + 11, 13, 17, 19. Has this ever been proven? If so has it ever been proven that the set of k's is infinite or is it finite?
  28. R

    Are there any primes of the form 10^k + 1 above 101?

    "11 and 101 are primes, whereas 1001 is not (7*11*13). Find the next smallest prime of the form 100...01, and show that it is the next" I'm fairly sure that there no primes of the form 10^k + 1 above 101, but I can't seem to find a complete proof. Consider the general case of factorising...
  29. R

    Subsets of the set of primes - uncountable or countable?

    Subsets of the set of primes -- uncountable or countable?? Cantor proved that the sub-sets of the natural numbers are uncountable. assuming that the the set of primes can be put in a 1-to-1 matching with the natural numbers (which I believe they can...) then it would follow that the sub...
  30. T

    Importance of the first 3 primes

    hey guys, I am a student engineer and have found that the laws we use are primarily based off of stats. this has led me to an interest in number theory and groupings. I was hoping someone could help me with somehing, i would like to know the relevance of the first 3 primes(2,3,5) to math in...
  31. J

    Proving Congruences of Primes: Show 2^((p-1)/2) = +1 (mod p)

    I came across this: Show that if p denotes an odd prime, then 2^((p-1)/2) = +1 (mod p). So basically, this is asking me to show that p|2^((p-1)/2)-1 AND p|2^((p-1)/2)+1 But I'm stuck from there. What am I missing? Could someone help me with the proof?
  32. S

    Finite non-abelian group of the order pq, pq primes

    Howdy, all. I am not sure if this is the right forum for this question. It isn't exactly an homework question, but it does stem very closely from a homework assignment in a first year graduate course in Abstract Algebra. The assignment has come and gone with limited success on my part, but...
  33. C

    Can the Product of All Primes Before p Be Greater Than p^2?

    Homework Statement I am proving something different and need this to be true. choose prime p > 11. then p^2 is less than the product of all primes that came before it. Homework Equations U(n)= {1, a_1, ... a_k} this is the ring of numbers co prime to n. ex: let p=13. 13^2 =...
  34. C

    Proving the Upper Bound for Primes Using Induction

    I am aiming to prove the following: Let 2 = p1 < p2 < p3... be the sequence of primes in increasing order. Prove that pn ≤ 22n-1.(Hint: Show that the method used to prove Euclid’s Theorem also proves that pn ≤ p1p2...pn−1 + 1.) So I started doing the proof via induction, letting n=2 be my...
  35. A

    Is There an Equation for Finding All Prime Numbers?

    This isn't a homework problem, but something I was kicking around. Thus far it has worked for the first 20 primes I could calculate in my head. Does anyone know why this shouldn't work, or an example of it not working for the a specific prime number? The idea is that all prime numbers can be...
  36. M

    Primes in set of rational numbers

    There was a part c and d from a question I couldn't answer. Let R = \{ a/b : a, b \in \mathbb{Z}, b \equiv 1 (\mod 2) \}. a) was find the units, b) was show that R\setminus U(R) is a maximal ideal. Both I was successful. But c) is find all primes, which I believe i only found one...the...
  37. K

    Euclid's Proof: Infinity of Primes

    Euclid's proof: 1) Assume there is a finite number of primes. 2) Let Pn be the largest prime. 3) Let X be the P1 * P2 ... * Pn + 1 At this point the statement is that "X cannot be divided by P1 through Pn", but why is that? This is not self-obvious to me. How can I know this? k
  38. J

    Pythagorean Primes and Gaussian Primes, divisibility question

    Here is an interesting problem that I've been thinking about for a while: Let p be a prime s.t. p = 4m+1 for some integer m. Show that p divides n^2 + 1, where n = (2m)! It comes from a section on principal ideal domains and unique factorization domains. It is well-known that p is the...
  39. A

    Prove primes based on associates

    Homework Statement Suppose that a and b are associates. Prove that if a is a prime number then b is a prime number. Homework Equations Associates are two numbers that are exactly equal when the abs(a) = abs(b). Or, re-write as a=ub where u is a unit. The Attempt at a Solution...
  40. Ƒ

    Comp Sci Solving Twin Primes with a Sieve Algorithm in Fortran

    Homework Statement I have been trying to come up with a program to calculate twin primes using a sieve algorithm in Fortran. So far I have been successful in creating one that finds primes, but I am having difficulty finding one that finds prime twins. If I knew how to do this I could find...
  41. P

    Exploring the Significance of Large Mersenne Primes in Mathematics

    http://mathworld.wolfram.com/news/2009-06-07/mersenne-47/ When a new large number such as this is discovered, does anything interesting usually follow from it or does everyone say "Yes... there it is, now let's find the next one."?
  42. icystrike

    Odd Primes Divisible by Sum of n^p-1 from n=1 to 103

    Find all odd primes p, if any, so that p divides \sum_{n=1}^{103} n^{p-1}
  43. D

    Which primes p satisfy p^2|5^p^2+1?

    Homework Statement First of all, hi everyone! I'm quite new in number theory, and need help on this one badly... Determine all prime numbers p so p2 divides 5p2+1. Homework Equations Euler's theorem: If a and m are coprimes then...
  44. T

    Divisibility of powers of primes

    Hi all, so I was looking at Legendre symbols, and I saw that \left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}. How does one show that \frac{p^2-1}{8} is always an integer? That is, how can we show that 8 | p^2-1? Can a similar method be applied to show that 24 | p^3-p? Thanks :-)...
  45. C

    The only 3 consecutive odd numbers that are primes are 3,5,7

    Homework Statement Show that the only three consecutive numbers that are primes are 3,5,7. Homework Equations The Attempt at a Solution let p, p+2, p+4 be three consecutive odd numbers If p=0(mod3), p is divisible by 3 If p=1(mod 3), p+2 is divisible by 3 If p=2(mod3), p+4 is...
  46. S

    No of primes less than a given number

    After reading 1 of the posts in this forum , I had a look at the millenium problems . There I saw the problem of proving if N=NP . I really did not understand what is NP and what is P ( I checked the Wikipedia link but this got me even more confused ... It talked of a non deterministic...
  47. C

    Proving the Finiteness of Fermat Primes

    for all fermat no.s, fi-1=[fi-1-1]2 all fermat no.s are of form 6Ni+5 Ni+1=6Ni2+8Ni+2 a no. of form 6N+5 is composite only when N is of form 6n1n2+5n1+n2 if we could assume that all fermat no.s after f4 are not prime, that means all Nis are of form 6n1n2+5n1+n2, i>4 that means that either...
  48. Z

    Spectral interpretation of Primes

    the idea is is there a Linear operator L so L | \phi _n > =p_n |\phi_n > with p_n being the nth prime and L a linear operator , is it possible to have an spectral interpretation for prime numbers ?
  49. Loren Booda

    A conjecture about sums of uniquely valued primes

    "Of the numbers N>1, only 4 and 6 cannot be expressed as a sum of prime numbers with unique values."
  50. P

    Euclid Proof of Infinite Primes

    Near the end of Euclid's proof he says that if you multiply all our known primes from 2 to Pn and then add 1 to it, the number isn't divisible by any of our primes up to Pn, because it leaves the remainder 1. Why is that? How does he know that it will always leave the remainder 1? Couldn't...
Back
Top