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

    Nice grouping of primes under 105

    The simple algorithm shown in the uploaded file generates a nice grouping of primes under 105.
  2. J

    MHB Can $\mathbb{Z}[\sqrt{-3}]$ Be Proven as a Principal Ideal Domain?

    Hi, Im trying to prove that a prime $p\neq 3$ is of the form $p=x^2 + 3y^2$ if $p \equiv 1 \pmod{3}$. I have think in a prove as follows: As we know that $-3$ is a quadratic residue mod p, we know that the ideal $(p)$ must divide $(x^2 + 3) = (x + \sqrt{-3})(x - \sqrt{-3})$ in the ring...
  3. Colleen G

    Abstract Alg. Proof w/ Mod Congruence and Relative Primes

    Homework Statement If ≡(mod), ≡(mod),and gcd(,)=1,provethat ≡ (mod ). Homework Equations If ≡(mod)→n|ab-cd ≡(mod)→n|b-d gcd(,)=1→ relatively prime. So bx+ny=1 Need to show n|a-c→a-c=nw The Attempt at a Solution If n|ab-cd, then nk=ab-cd If n|b-d, then nl=b-d If n|ab-cd AND n|b-d, then...
  4. anemone

    MHB Solving for Primes and Evens: $x^n+x^{n-1}+\cdots+x+1=y^2+y+1$

    Find all primes $x$ and $y$ and even numbers $n>2$ satisfying the equation $x^n+x^{n-1}+\cdots+x+1=y^2+y+1$.
  5. C

    Are n1 and n2 Prime Factors of n?

    Homework Statement We have n ≥ 2, n not prime, n ∈ ℤ. Take the smallest such n. n is not prime and as such n is not irreducible and can be written as n = n1.n2; n1, n2 not units. We may take n1, n2 ≥ 2. However we have n > n1, n > n2 so n1, n2 have prime factors. I'm not sure how n > n1, n >...
  6. evinda

    MHB For which primes, does the equation have a rational solution?

    Hi! (Smile) I have to find for which primes $p$, the equation $x^2+y^2=3z^2$ has a rational point in $\mathbb{Q}_p$. According to my notes: Obviously, $\forall p \in \mathbb{P}, p \nmid 2 \cdot 3$, there is a rational solution in $\mathbb{Q}_p$. But,why is it obvious that the equation has a...
  7. T

    Our Old Friend, the Twin Primes Conjecture

    I have to be honest--- I am not sure exactly the right tone to strike here. I find that if one comes in cocksure proclaiming "I have a proof of the twin primes conjecture! SOLVED! QED, BAY-BAY!" then one achieves a great deal of annoyance, and rightly so. On the other hand, it also seems...
  8. M

    On partitioning an even number into a pair of (relative) primes

    An example:For m= 176 (132<176<172 one finds r=(3-2)x(5-2)x(7-2)x(11-1)x(13-2)=1650 relative primes (0<v<2x3x5x7x11x13), forming 825 asymmetric pairs, among them four partitions into prime numbers:19+157, 37+139, 67+109, 73+103, 79+97.
  9. R

    Does there always exist primes in between square of two consecutive prime.

    Does there always exist primes in between square of two consecutive prime i.e Pn-1 and Pn where Pn-1 and Pn are consecutive prime. That is, in other words, does all the odd places between Pn-1 and Pn, are not divided, by primes less than Pn or by all primes upto Pn-1.I can only check randomly...
  10. Char. Limit

    A question on palindromic primes

    So just for fun, I decided to look for a list of palindromic primes, that is, primes that when in base 10 representation are the same whether backward or forward. 1003001, just to give an example. I quickly noticed something striking: Other than 11, every palindromic prime out of the first...
  11. W

    A wager of £20 on the nature of primes

    Hello, I am 14.So entirely an amateur.Obviously, I do not want to fall into the, "I am a complete amatuer of your subject but assume my findings will change the world" cliche. Anyway, I recently did some work in correlation to the nature of primes.If you would like to read it, you can...
  12. W

    Is It Proved That All Primes End With 1,3,7,9?

    So it was my observation that all the prime numbers I saw ended with digits 1,3,7,9.Is this true for all primes? Is it proved?
  13. matqkks

    Exploring Perfect Numbers: Applications Beyond Mersenne Primes

    Why are perfect numbers important? What is the best way of introducing these numbers to a first course on number theory? I could not find any application apart from the relation to Mersenne primes. Are there any other applications of perfect numbers?
  14. Bob3141592

    Why Do Different Prime Number Variations Occur in Equal Frequencies?

    As a programming exercise I wrote a program to generate primes. First I generated a billion of them (the one billionth prime is 22,801,763,489). My program also scans through these numbers for Twin primes (adjacent primes that differ by two), cousin primes (adjacent primes that differ by four)...
  15. matqkks

    Germain Primes: Exploring Sophie Germain's Motivation

    Why did Germain come up with her Germain primes? I am intrigued to know why Sophie came across these primes. Do they have any applications?
  16. matqkks

    MHB Why did Sophie Come Up with Germain Primes?

    Why did Germain come up with her Germain primes? I am intrigued to know why Sophie came across these primes. Do they have any applications?
  17. D

    Proof question: the sum of the reciprocals of the primes diverges

    The gist of the approach I took is that∑1/p = log(e^∑1/p) = log(∏e^1/p) and logx→ ∞ as x→∞. Proof outline: let ∑1/p = s(x). (...SO I can write this easily on tablet) and note that e^s(x) diverges since e^1/p > 1 for any p and the infinite product where every term exceeds 1 is divergent. Then...
  18. Z

    Easy way to figure out primes? (Powers of 2, not Mersenne)

    I have figured out a seemingly revolutionary way to calculate primes. It is very simple. Let o be the number of odd digits in p, where p is a power of 2. If o is an odd number, then the sum of digits in p will be a prime number. Please, PLEASE do not hold back with commenting. I really want...
  19. M

    Proof of infinite primes (why is it wrong?)

    So I thought up a "proof" for infinite primes. I'm assuming I did something wrong, but I don't know what, it would be nice if someone could tell me what I did wrong. Suppose there are a finite number of primes of quantity n which are listed from smallest to largest in the list: p1, p2, ... ...
  20. H

    MHB Proving Prime Norms of H: (a,b) in Z

    H is a number system where (a,b) belongs in H where a and b is an element of Z(integer) Addition and multiplication are defined as follows: (a, b) + (c, d) := (a + c , b + d) (a, b) x (c, d) := (ac-5bd , ad+bc) For any number (a,b) in H, we can define its norm by ||(a, b)|| :=...
  21. 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)
  22. G

    Find f'(2) from f'(1)=1 and d/dx[f(2x)]=f'(x)

    Homework Statement d/dx[f(2x)]=f'(x) and f'(1)=1 find f'(2) Homework Equations The Attempt at a Solution so I think this means the derivative of "f(2x)" equals f'(x) if I find the derivative using the chain rule I would get f'(2x)2= f'(x) so f'(2x) = f'(x)/2 Here I am at a loss as to how to...
  23. caters

    MHB Discovering Intersections of Infinite Primes Sets

    We have this set of primes which is infinite. This has lots of different subsets. Here is the list of subsets: Real Eisenstein primes: 3x + 2 Pythagorean primes: 4x + 1 Real Gaussian primes: 4x + 3 Landau primes: x^2 + 1 Central polygonal primes: x^2 - x + 1 Centered triangular primes: 1/2(3x^2...
  24. D

    Distinguish pq Prime Cases: Algorithm for ppt

    Given pq where p < q are prime, but either (p \equiv 1 \mod 4 and q \equiv 3 \mod 4) or (p \equiv 3 \mod 4 and q \equiv 1 \mod 4). Is there a ppt algorithm that will distinguish the two possibilities?
  25. C

    Representation of e in terms of primes

    We can represent π, in terms of primes by using Euler's product form of Riemann Zeta. For example ζ(2)=(π^2)/6= ∏ p^2/(p^2-1). Likewise, is there a representation of e that is obtained by using only prime numbers?
  26. O

    Challenge 11: Sequence of Primes

    Consider the following sequence: a1 = p, where p is a prime number. an+1 = 2an+1 Prove there is no value of p for which every an is a prime number, or make me look dumb and construct a counterexample.
  27. K

    MHB Prove that if p and q are positive distinct primes, then log_p(q) is irrational.

    Prove that if p and q are positive distinct primes,then $\log_p(q)$ is irrational. Attempt: Proof by contradiction: Assume $\log_p(q)$ is rational.Suppose $\log_p(q) = \dfrac{m}{n}$ where $m,n \in \mathbb{Z}$ and $\gcd(m,n) = 1$. Then, $p^{\frac{m}{n}} = q$ which implies $p^m = q^n$.
  28. S

    MHB Proving the Congruence of Primes of the Form x² + 5y² (mod 20)

    If $p$ is an odd prime expressible as $$p=x^2+5y^2$$ where $x,y$ are integers, then prove that $p \equiv 1 \text{ or }9\text{ (mod 20)}$.
  29. C

    Number of Primes between two integers

    Is there a formula to calculate the EXACT number of primes between two integers? There are many very good ways of ESTIMATING the number but I have found very few that give the EXACT number, and those that do essentially require the knowledge of primes before hand (Legendre and Miessel.) While...
  30. G

    For any Pythagorean triple, the number of primes under a + b + c must

    be no more than c? In fact, only for the first triple does equality hold. Upon examining some of the triples, I noticed this must be true. However, I'm having a hard time explaining why. Is there a good explanation for this? Many thanks!
  31. J

    Proving Irreducibility of Primes in Z[√-5]

    Homework Statement Suppose p is a prime number. Prove that p is irreducible in Z[√−5] if and only if there does not exist α ∈ Z[√−5] such that N(α) = p. Using this, find the smallest prime number that is not irreducible in Z[√−5]. Homework Equations α = a+b√−5 ∈ Z[√−5] N(α) = a2 + 5b2...
  32. C

    Euclid's proof of infinitude of primes

    Hi, I'm new into the domain of proofs, and I'm reading How to prove it - A structured approach. I'm having a problem with the last paragraph... If m is a product of primes, and q is one of those primes taken randomly, then we should be able to divide m by q to obtain the rest of the...
  33. mesa

    Need software for calculating primes

    Does anyone have software I can run on my PC that can calculate primes to 8.0 x 1020?
  34. C

    Proving the Existence of Pythagorean Triples for Primes of the Form 4k+1

    Homework Statement Prove that every prime of the form 4k+1 is a hypotenuse of a rectangular triangle with integer sides. The Attempt at a Solution I tried messing around with the Pythagorean theorem but not really sure where to go. x^2+y^2=(4k+1)^2 it seems like there would exist x...
  35. S

    Proof of the twin primes conjecture

    I have just found links to a few articles discussing the proof of the twin prime conjecture by Yitang Zhang, a once obscure mathematician working as a lecturer at the University of New Hampshire, and who according to reports had difficulty finding academic work and worked as an accountant and a...
  36. M

    Why is the Twin Primes Conjecture still relevant to mathematicians today?

    Proof towards Twin Primes Conjecture! http://www.wired.com/wiredscience/2013/05/twin-primes/
  37. C

    Proof about 6k+5 producing an infinite amount of primes

    Homework Statement Prove that 6k+5 produces an infinite amount of primes. k is an integer The Attempt at a Solution We first observe that 6k+1,6k+3,6k+5 produce all the odd integers. Next we see that (6k+1)(6k'+1)=6(6kk'+k+k')+1 so the product of integers of the form (6k+1)(6k'+1)=6k''+1. And...
  38. C

    MHB Minimum number of twin primes

    I’ve encountered a relationship that, if true, could show that there are an infinite number of twin primes. It involves the minimum number of twin primes to be found between 3 and any higher odd number squared. However, I don’t know if this relationship holds true in all cases. We start with...
  39. A

    Mersenne Primes: Identifying & Eliminating Non-Prime Numbers

    Following is a list of 39 Mersenne numbers. Some are prime and some are not. These are generated with x =( 2^n) -1. Many of the largest primes known are Mersenne primes. I would like to point out that a sieve may be used to block out many non prime Mersenne numbers. For...
  40. C

    Proving Infinite Primes of 6m+1 and 6m+5 Form Using Euclid's Method

    Homework Statement Except 2 and 3 , prove that their an infinite amount of primes of the form 6m+1 and 6m+5 for some integer m It says to use Euclid's method but replace the +1 with a -1. The Attempt at a Solution Would I just multiply some of these forms together and subtract 1...
  41. C

    Finding primes fitting a certain algebraic relation.

    Homework Statement Find all the primes p and q such that p^2-p-1=q^3 The Attempt at a Solution Trying out the first prime number 2, it is clear that p>q and that the difference is larger than 1. Then when factorizing it p^2-p=q^3+1 \Rightarrow p(p-1)=(q+1)(q^2-q+1), I get that p must...
  42. H

    Primes, pigeon holes, modular arithmetic

    Homework Statement The Attempt at a Solution Don't have a clue how to even start this one, sorry.
  43. caffeinemachine

    MHB A result involving two primes I think is true.

    Hello MHB. There's a number theory problem I was solving and I can solve it if the following is true: Let $p, q$ be distinct odd primes. Let $pk=q-1$ for some integer $k$. Then $p^k \not\equiv 1 \,(\mbox{mod } q)$. I considered many such primes to find a counter example but failed. Can anyone...
  44. R

    A representation using reciprocal primes

    Is this interesting? I have a way to represent all of the real numbers with a subset of the open interval (0,1). I write as a binary decimal x = .a_{0}a_{1}a_{2}a_{3}... where x = \sum -1^{a_{0}+1}/p_{i} where p_{i} is the i^{}th prime. Since the reciprocals of the primes diverges, in this...
  45. N

    Comp Sci Find primes using sieve of erasthothenes by way of bit arrays in C++

    Hey. I have to create a program in C++ to calculate the number of prime numbers up to a specified number. I also have to print out the first and last 5, but I'll cross that bridge when I come to it. I can do this fine with integers, but we have to do it where each slot in an array represents...
  46. A

    Consecutive integers divisible by a set of Primes

    I am having more than a little fun with this sequence of numbers and am looking for a better algorithm to find the next numbers in the sequence. Let Z be the set of the first n odd primes. Find two integers j and k that are relatively prime to all members of Z where every integer between...
  47. A

    Number theory; primes dividing proof

    Homework Statement Show there exist infinitely many (p, q) pairs, (p ≠ q), s.t. p | 2^{q - 1} - 1 and q | 2^{p - 1} - 1 Homework Equations We are allowed to assume that 2^{β} - 1 is not a prime number or the power of a prime if β is prime. The Attempt at a Solution Using fermat's little...
  48. D

    Sum of Sums over Primes that Divide the Index

    I have seen double sums, but have come across a problem involving sums over primes. However, this sum is inside a second sum, and is taken over all primes that divide the outside index, like this: \sum_{k=1}^{n} \sum_{p | k} \frac 1p for p prime. Is there any way to manipulate this...
  49. caffeinemachine

    MHB Irrationality of sum of roots of primes.

    I observed the following: 1) $\sqrt{2}$ is irrational. 2) $\sqrt{2}+\sqrt{3}$ is irrational(since its square is irrational). 3) $\sqrt{2}+\sqrt{3}+\sqrt{5}$ is irrational(assume its rational and is equal to $r$. Write $r- \sqrt{5}=\sqrt{2} + \sqrt{3}$. Now square both the sides and its...
  50. S

    Trouble understanding proof- infinitely many primes?

    I'm having trouble with this proof: Prove that there are infinitely many prime numbers, using proof by contradiction. My teacher gave it to us the first day of class, but I'm a little lost: Assume there are finitely many prime number, P1, P2, P3,...,Pn. Let q=(P1*P2*P3*...*Pn)+1 Then...
Back
Top