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

    B Probability that 2 distinct integers are divisible by the same number

    The probability that a randomly chosen integer is divisible by a given integer p is 1/p, regardless of whether p is prime. The probability that 2 distinct randomly chosen integers are divisible by the same prime p is 1/p2. I am not sure however whether the probability that 2 distinct randomly...
  2. C

    I How to Generate Cubes without Cubing: A Proof Method

    I have tested the above proposition thru the integer 90, and have found that the proposition holds true. I'm not sure of the method to prove that this would always be true. Any help, criticism, or proof is welcome.
  3. M

    Prove that there are infinitely many primes of the form ## 6k+1 ##?

    Proof: Suppose that the only prime numbers of the form ## 6k+1 ## are ## p_{1}, p_{2}, ..., p_{n} ##, and let ## N=4p_{1}^{2}p_{2}^{2}\dotsb p_{n}^{2}+3 ##. Since ## N ## is odd, ## N ## is divisible by some prime ## p ##, so ## 4p_{1}^{2}\dotsb p_{n}^{2}\equiv -3\pmod {p} ##. That is, ##...
  4. Jiketz

    A Determining rationality of real numbers represented by prime digit sequence

    I would like to know if my answer is correct and if no ,could you correct.But it should be right I hope:
  5. M

    Prove that there are infinitely many primes of the form ## 8k-1 ##

    Proof: Suppose for the sake of contradiction that the only primes of the form ## 8k-1 ## are ## p_{1}, p_{2}, ..., p_{n} ## where ## N=16p_{1}^2p_{2}^2\dotsb p_{n}^2-2 ##. Then ## N=(4p_{1}p_{2}\dotsb p_{n})^2-2 ##. Note that there exists at least one odd prime divisor ## p ## of ## N ## such...
  6. M

    Determine the set of odd primes ## p ##?

    Let ## p ## be an odd prime. Then ## 23 ## is a quadratic residue modulo ## p ## if ## (23|p)=1 ##. Applying the Quadratic Reciprocity Law produces: ## (23|p)=(p|23) ## if ## p\equiv 1\pmod {4} ## ## (23|p)=-(p|23) ## if ## p\equiv 3\pmod {4} ##. Now we consider two cases. Case #1: Suppose ##...
  7. D

    I Primes -- Probability that the sum of two random integers is Prime

    im thinking i should just integrate (binominal distribution 1-2000 * prime probability function) and divide by integral of bin. distr. 1-2000. note that I am looking for a novel proof, not just some brute force calculation. (this isn't homework, I am just curious.)
  8. M

    I Polynomials can be used to generate a finite string of primes....

    F(n)=##n^2 −n+41## generates primes for all n<41. Questions: (1) Are there polynomials that have longer lists? (2) Is such a list of polynomials finite (yes, no, unknown)? (3) Same questions for quadratic polynomials?
  9. M

    Factor the repunit ## R_{6}=111111 ## into a product of primes

    Consider the repunit ## R_{6}=111111 ##. Then ## R_{6}=111111=1\cdot 10^{5}+1\cdot 10^{4}+1\cdot 10^{3}+1\cdot 10^{2}+1\cdot 10^{1}+1\cdot 10^{0} ##. Note that a positive integer ## N=a_{m}10^{m}+\dotsb +a_{2}10^{2}+a_{1}10+a_{0} ## where ## 0\leq a_{k}\leq 9 ## is divisible by ## 7, 11 ##, and...
  10. M

    Every integer greater than 5 is the sum of three primes?

    Proof: Let ## a>5 ## be an integer. Now we consider two cases. Case #1: Suppose ## a ## is even. Then ## a=2n ## for ## n\geq 3 ##. Note that ## a-2=2n-2=2(n-1) ##, so ## a-2 ## is even. Applying Goldbach's conjecture produces: ## 2n-2=p_{1}+p_{2} ## as a sum of two primes ## p_{1} ## and ##...
  11. M

    Find all pairs of primes ## p ## and ## q ## satisfying ## p-q=3 ##.

    Proof: Let ## p ## and ## q ## be primes such that ## p-q=3 ##. Now we consider two cases. Case #1: Suppose ## p ## is an even prime. Then ## p=2 ##, because ## 2 ## is the only even prime. Thus ## 2-q=3 ##, so ## q=-1 ##, which contradicts the fact that ## q ## is prime. Case #2: Suppose ## p...
  12. M

    Show that the sum of twin primes ## p ## and ## p+2 ## is divisible?

    Proof: Suppose ## p ## and ## p+2 ## are twin primes such that ## p>3 ##. Let ## p=2k+1 ## for some ## k\in\mathbb{N} ##. Then we have ## p+(p+2)=2k+1+(2k+1+2)=4k+4=4(k+1)=4m ##, where ## m ## is an integer. Thus, the sum of twin primes ## p ## and ## p+2 ## is divisible by ## 4 ##. Since ##...
  13. M

    Proof: Twin Primes Always Result in Perfect Squares

    Proof: Suppose ## p ## and ## p+2 ## are twin primes. Then we have ## p(p+2)+1=p^2+2p+1=(p+1)^2 ##. Thus, ## (p+1)^2 ## is a perfect square. Therefore, if ## 1 ## is added to a product of twin primes, then a perfect square is always obtained.
  14. M

    Verify that the integers 1949 and 1951 are twin primes

    Proof: Consider all primes ## p\leq \sqrt{1949} \leq 43 ## and ## q\leq \sqrt{1951} \leq 43 ##. Then we have ## p\nmid 1949 ## and ## q\nmid 1951 ## for all ## p\leq 43 ##. Thus, ## 1949 ## and ## 1951 ## are both primes. By definition, twin primes are two prime numbers whose difference is ## 2...
  15. M

    Given that ## p\nmid n ## for all primes ## p\leq \sqrt[3]{n} ##

    Proof: Suppose for the sake of contradiction that ## n ## contains at least three prime factors. Let ## n=p_{1} p_{2}\dotsb p_{X} ## for ## x\geq 3 ##. Note that ## n=p_{1} p_{2} p_{3} ##. Then we have ## p_{1}\nleq \sqrt[3]{n} ##, ## p_{2}\nleq \sqrt[3]{n} ## and ## p_{3}\nleq \sqrt[3]{n} ##...
  16. M

    If ## p\geq q\geq 5 ## and ## p ## and ## q ## are both primes ....

    Proof: Suppose ## p\geq q\geq 5 ## and ## p ## and ## q ## are both primes. Note that ## p ## and ## q ## are not divisible by ## 3 ##, so we have ## p^{2}-1\equiv 0 (mod 3) ## and ## q^{2}-1\equiv 0 (mod 3) ##. This means ## 3\mid((p^{2}-1)-(q^{2}-1)) ##, and so ## 3\mid p^{2}-q^{2} ##. Since...
  17. M

    How to Find an Answer to 2^n + 1 Prime Question

    Proof: ## 17=2^4+1 ## Now I'm stuck. How should I find the correct answers to this problem?
  18. M

    Can anyone please verify/review this proof about primes?

    Proof: Suppose that there are infinitely many primes of the form n^2-2. Then we have n^2-2=2^2-2=2, n^2-2=3^2-2=7, n^2-2=5^2-2=23, n^2-2=7^2-2=47...
  19. The Riemann Hypothesis, Explained

    The Riemann Hypothesis, Explained

    The Riemann Hypothesis, Explained
    • fresh_42
    • Media item
    • Primes Riemann hypothesis
    • Comments: 0
    • Category: Analysis
  20. D

    I What are the unique prime factors of -30?

    If I select two integers at random, what is the probability that their sum will be prime?
  21. P

    B Natural Numbers contain all the Primes

    w = {0,0 | 1,1 | 2,2...} Let x = number of primes up to w+1 Let y = number of primes up to w-1 Now there's an empty prime box in the 0,0 slot not connected to anything. So I let x = p-1 and y = p+1 p = [p0, p1, p2...] Now p0 becomes 1,0/1 It can be either on or off. For the sake of...
  22. F

    Indirect Proof (open) Divergent series of inverse primes

    Show by contradiction that $$ \sum_{p\in \mathbb{P}}\dfrac{1}{p} =\sum_{p\;\text{prime}}\dfrac{1}{p} $$ diverges. Which famous result is an immediate corollary?
  23. nomadreid

    I Connection of zeta to primes: less Euler than error or L-functions?

    Often I read that the Riemann Hypothesis (RH) is related to prime numbers because of the equivalence on Re(s)>1 of the zeta function and Eurler's product formula , but is it more accurate that the relevance of the RH to primes (or vice-versa) is either that the RH implies formulas for the...
  24. DaTario

    A Does Mihailescu's theorem use the infinitude of primes?

    Hi all, I would like to know if in proving the Catalan's conjecture Preda Mihailescu used the infinitude of primes. Best wishes, DaTario
  25. DaTario

    I Compilations of proofs of Euclid's Theorem on primes

    Hi All. Does anybody have a reference, (book, internet site) - besides those books of Paulo Ribenboim - where one can find a compilation of demonstrations of the Euclid's theorem on the infinitude of primes? As a suggestion, if the known proofs are neither too many not too long, it would be nice...
  26. GlassBones

    Prime factors of odd composites

    Homework Statement Let ##n## be odd and a composite number, prove that all of its prime is at most ##\frac{n}{3} ## Homework Equations Some theorems might help? Any ##n>1## must have a prime factor if n is composite then there is a prime ##p<√n## such that ##p|n## The Attempt at a Solution...
  27. matqkks

    I Number of Primes: How Computers Evaluate

    How do computers evaluate the number of primes below a given integer?
  28. DuckAmuck

    A The Last Occurrence of any Greatest Prime Factor

    If you have 2 integers n and n+1, it is easy to show that they have no shared prime factors. For example: the prime factors of 9 are (3,3), and the prime factors of 10 are (2,5). Now if we consider 9 and 10 as a pair, we can collect all their prime factors (2,3,3,5) and find the maximum, which...
  29. Arman777

    When Does the Prime Ratio of Spiral Diagonals Drop Below 10%?

    Homework Statement https://projecteuler.net/problem=58 Homework EquationsThe Attempt at a Solution def prime(N): if N == 1: return False y = int(N**0.5) for i in range(2,y+1): if N%i == 0: return False return True def finder(N): L = len(N)...
  30. qspeechc

    Sacks' Autistic Twins and Prime Testing

    Hello everyone. [Firstly, I didn't know if this belongs here or in General; please move if appropriate]. <Moderator's note: moved to GD> I was reading this paper on the AKS primality test (undergraduates can understand it, highly recommended!), and on page 7 the author brings up the story of...
  31. F

    Congruence and Primes: Proving the Order of an Integer Modulo a Prime

    Homework Statement 1.31 Let ##p## be a prime and let ##q## be a prime that divides ##p - 1##. a) Let ##a \epsilon F^*_p## and let ##b = a^{(p - 1)/q}##. Prove that either ##b = 1## or else ##b## has order ##q##. (Recall that order of ##b## is the smallest ##k \ge 1## such that ##b^k = 1## in...
  32. J

    I Primes and Polynomials

    Does there exist a polynomial P(x) with rational coefficients such that for every composite number x, P(x) takes an integer value and for every prime number x, P(x) does not take on an integer value? Can someone please guide me in the right direction? I've tried to consider the roots of the...
  33. 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
  34. A

    I Bijective function from naturals to primes

    What's the problem with this trivial solution: n --> n'th prime.
  35. FallenApple

    A Relation between Sparse Primes and Curse of Dimensionality?

    Is there a relation between these concepts? We know that as we move down the number line, the primes become less common. This makes sense: as we get more and more numbers, they could be constituted using all the primes that came before early on and less likely to be constituted by all the recent...
  36. S

    I Arbirtary Extraction of Primes - From Ideal Fractal(s)?

    At a sufficient resolution, such as mapping every knowing prime gap... Could a fractal equation created to perfectly describe this (at max possible res.): http://techn.ology.net/the-density-plot-of-the-prime-gaps-is-a-fractal/ Likewise clear a path to a nth-dimensional fractal for prime gaps...
  37. I

    MHB Sum of 2 Primes: 45 - (2 Digit Integer)?

    I think that we have to get all 2 digit odd numbers that can be expressed as the sum of 2 primes and subtract that from 45, so I think that the answer would be 45-(number of 2 digit integers n that are prime and have n-2 be prime as well)?
  38. Math Amateur

    MHB Irreducibles and Primes in Integral Domains ....

    I am reading "Introductory Algebraic Number Theory"by Saban Alaca and Kenneth S. Williams ... and am currently focused on Chapter 1: Integral Domains ... I need some help with understanding Example 1.4.1 ... Example 1.4.1 reads as follows: In the above text by Alaca and Williams we read the...
  39. Math Amateur

    I Irreducibles and Primes in Integral Domains ....

    I am reading "Introductory Algebraic Number Theory"by Saban Alaca and Kenneth S. Williams ... and am currently focused on Chapter 1: Integral Domains ... I need some help with understanding Example 1.4.1 ... Example 1.4.1 reads as follows: In the above text by Alaca and Williams we read the...
  40. Math Amateur

    MHB Quadratic Polynomials and Irreducibles and Primes

    I am reading "Introductory Algebraic Number Theory"by Saban Alaca and Kenneth S. Williams ... and am currently focused on Chapter 1: Integral Domains ... I need some help with the proof of Theorem 1.2.2 ... Theorem 1.2.2 reads as follows: https://www.physicsforums.com/attachments/6515 In the...
  41. Math Amateur

    I Quadratic Polynomials and Irreducibles and Primes ....

    I am reading "Introductory Algebraic Number Theory"by Saban Alaca and Kenneth S. Williams ... and am currently focused on Chapter 1: Integral Domains ... I need some help with the proof of Theorem 1.2.2 ... Theorem 1.2.2 reads as follows: In the above text from Alaca and Williams, we read the...
  42. K

    Prove there are infinitely many primes using Mersenne Primes

    Homework Statement Prove that there are infinitely many primes using Mersenne Primes, or show that it cannot be proven with Mersenne Primes. Homework Equations A Mersenne prime has the form: M = 2k - 1 The Attempt at a Solution Lemma: If k is a prime, then M = 2k - 1 is a prime. Proof of...
  43. kaliprasad

    MHB Showcase of 2016 Consecutive Numbers w/ 100 Primes

    Show that there exists 2016 consecutive numbers that contains exactly 100 primes.
  44. Albert1

    MHB Palindromic Primes: Find A from 1000-2000

    given : A=B$\times $C with the following characters (1) A,B,C $\in N$ (2)A is a palindrome (3)B and C are all palindromic primes (4) 1000<A<2000 (5) B is a 2-digit number (6) C is a 3-digit number find A
  45. e2theipi2026

    A Does this imply infinite twin primes?

    I can prove the twin prime counting function has this form: \pi_2(n)=f(n)+\pi(n)+\pi(n+2)-n-1, where \pi_2(n) is the twin prime counting function, f(n) is the number of twin composites less than or equal to n and \pi(n) is the prime counting function. At n=p_n, this becomes \pi_2(p_n) =...
  46. B

    Testing primes using factorials

    As far as I can tell for the equation n!/n^2=x or n-1!/n=x, if x is a natural number then it seems n is composite. If x is a non-natural number then it is prime (excluding 4). I am aware that this is not very practical since I am using factorials and the numbers get very large. But it still...
  47. Borek

    I Basel problem, primes and π²/6

    Bear with me, I know nothing. Eons ego @micromass told me about this beautiful formula: \frac {\pi^2} 6 = \prod\limits_{P}\left( 1-\frac 1 {p^2}\right) ^{-1} where p are primes. Just a few minutes ago I have learned about the Basel problem and its solution: \sum \limits_{n=1}^{\infty} \frac...
  48. 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...
  49. DaMeekie

    I Can This Formula Identify All Prime Numbers?

    To start let's use this trick to find a sequence of primes 11+13-7=17 This trick starts with prime 11 and the next in sequence 13. After you add them together to get 24 you subtract 7 which is the prime in sequence before 11, and you will get the answer 17. Now this will find every single prime...
  50. PcumP_Ravenclaw

    Aren't there infinitely many primes?

    Homework Statement sn= 1/n if n is a prime number; sn = 0 if n is not prime. Homework EquationsThe Attempt at a Solution We know that there are infinitely many prime numbers as n tends to infinity so why is ## \frac{1}{(prime number)} ## not equal to zero when n is a prime number?
Back
Top