Prime Definition and 777 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. bremenfallturm

    Finding large prime factors (number theory)

    Hello! I'm asked to factor 314000 by hand. The answer key says that is is ##2^4\cdot 5^3\cdot 157##, but I honestly have no idea how to factor it by hand. I know that I can check all prime numbers up to ##\sqrt{314000}## but that would not be doable by hand obviously. I did try to use the...
  2. 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:
  3. M

    A How should I write an account of prime numbers?

    How should I write an account of prime numbers in arithmetic progressions? Assuming this account should be in the form of an essay of at least ## 500 ## words. Should I apply the formula ## a_{n}=3+4n ## for ## 0\leq n\leq 2 ##? Can anyone please provide any idea(s)?
  4. T

    I Frequency of prime number gaps according to (p-1)/(p-2)

    Caution I'm not a mathematician. In short, long time ago I calculated prime number gaps just for fun expecting an almost uniform distribution of the frequency of the gaps 2, 4, 6, ... . Instead the frequency showed a series of maxima and minima and I was confused. Later Professor emeritus Oskar...
  5. M

    Determine (with proof) the set of all prime numbers

    Proof: Let ## p ## be the prime divisor of two successive integers ## n^{2}+3 ## and ## (n+1)^{2}+3 ##. Then ## p\mid [(n+1)^{2}+3-(n^{2}+3)]\implies p\mid (2n+1) ##. Observe that ## p\mid (n^{2}+3) ## and ## p\mid (2n+1) ##. Now we see that ## p\mid [(n^{2}+3)-3(2n+1)]\implies p\mid...
  6. 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.)
  7. MevsEinstein

    I Defining the Prime Gap function

    Hi PF! I created a function ##R(x)## that gives the gap between the largest two primes less than or equal to ##x##. To define it, I used this property: $$\pi(x+R(x))=\pi(x)+1$$ Which is true since the ##x## distance between ##\pi(x)## and ##\pi(x)+1## is ##R(x)##. If we solve for ##R(x)## we...
  8. M

    Prove that there exists a prime with at least ## n ## of its digits.

    Proof: By Dirichlet's theorem, we have that if ## a ## and ## d ## are two positive coprime numbers, then there are infinitely many primes of the form ## a+nd ## for some ## n\in\mathbb{N} ##. Let ## n\geq 1 ## be a natural number. Now we consider the arithmetic progression ## 10^{n+1}k+1 ##...
  9. hotAdaptness

    A I think I discovered a pattern for prime numbers

    I wrote a program that implements the pattern and finds the primes automatically. It worked up to 70 million then it crashed because program holds data in RAM so it can be fixed. It found all the primes up to 70 million and found no exception. I won't explain the pattern because its so...
  10. e2m2a

    A Prime Number Powers of Integers and Fermat's Last Theorem

    From my research I have found that since Fermat proved his last theorem for the n=4 case, one only needs to prove his theorem for the case where n=odd prime where c^n = a^n + b^n. But I am not clear on some points relating to this. For example, what if we have the term (c^x)^p, where c is an...
  11. M

    Show that 13 is the largest prime that can divide....

    Proof: Let ## p ## be the prime divisor of two successive integers ## n^2+3 ## and ## (n+1)^2+3 ##. Then ## p\mid [(n+1)^2+3-(n^2+3)]\implies p\mid 2n+1 ##. Since ## p\mid n^2+3 ## and ## p\mid 2n+1 ##, it follows that ## p\mid a(n^2+3)+b(2n+1) ## for some ## a,b\in\mathbb{Z} ##. Suppose ## a=4...
  12. M

    If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that....

    Proof: Suppose ## p ## and ## p^{2}+8 ## are both prime numbers. Since ## p^{2}+8 ## is prime, it follows that ## p ## is odd, so ## p\neq 2 ##. Let ## p>3 ##. Then ## p^{2}\equiv 1 \mod 3 ##, so ## p^{2}+8\equiv 0 \mod 3 ##. Note that ## p^{2}+8 ## can only be prime for ## p=3 ##. Thus ##...
  13. M

    For n>3, show that the integers n, n+2, n+4 cannot all be prime

    Proof: Let ## n>3 ## be an integer. Applying the Division Algorithm produces: ## n=3q+r ## for ## 0\leq r< 3 ##, where there exist unique integers ## q ## and ## r ##. Suppose ## n ## is prime. Then ## n=3q+1 ## or ## n=3q+2 ##, because ## n\neq 3q ##. Now we consider two cases. Case #1...
  14. M

    For ## n>1 ##, show that every prime divisor of ## n+1 ## is an odd integer

    Proof: Suppose for the sake of contradiction that there exists a prime divisor of ## n!+1 ##, which is an odd integer that is not greater than ## n ##. Let ## n>1 ## be an integer. Since ## n! ## is even, it follows that ## n!+1 ## is odd. Thus ## 2\nmid (n!+1) ##. This means every prime factor...
  15. M

    Prove that if ## n>2 ##, then there exists a prime ## p ## satisfying....

    Proof: Assume to the contrary that ## n!-1 ## is not prime. That is, ## n!-1 ## is composite. Let ## p ## be a prime factor of ## n!-1 ## such that ## n<p ## for some ## n\in\mathbb{N} ## where ## n>2 ##. Since ## p\mid (n!-1) ##, it follows that ## p\nmid n! ##. This means ## p\nleq n ##...
  16. M

    Show that any composite three-digit number must have a prime factor

    Proof: Suppose for the sake of contradiction that any composite three-digit number must have a prime factor not less than or equal to ## 31 ##. Let ## n ## be any composite three-digit number such that ## n=ab ## for some ## a,b\in\mathbb{Z} ## where ## a,b>1 ##. Note that the smallest prime...
  17. D

    I Probability of Sum of 2 Random Ints Being Prime

    if I select two integers at random between 1 and 1,000, what is the probability that their sum will be prime?
  18. M

    Prove that ## \sqrt{p} ## is irrational for any prime ## p ##?

    Proof: Suppose for the sake of contradiction that ## \sqrt{p} ## is not irrational for any prime ## p ##, that is, ## \sqrt{p} ## is rational. Then we have ## \sqrt{p}=\frac{a}{b} ## for some ## a,b\in\mathbb{Z} ## such that ## gcd(a, b)=1 ## where ## b\neq 0 ##. Thus ## p=\frac{a^2}{b^2} ##...
  19. M

    Determine whether the integer 701 is prime by testing?

    Proof: Consider all primes ## p\leq\sqrt{701}\leq 27 ##. Note that ## 701=2(350)+1 ## ## =3(233)+2 ## ## =5(140)+1 ## ## =7(100)+1 ## ## =11(63)+8 ## ## =13(53)+12 ##...
  20. bland

    I Is Riemann's Zeta at 2 Related to Pi through Prime Numbers?

    I just saw that one of the ways of calculating Pi uses the set of prime numbers. This must sound crazy even to people who understand it, is it possible that this can be explained in terms that I, a mere mortal can understand or it is out of reach for non mathematicians?
  21. M

    Find the prime factorization of the integers 1234, 10140, and 36000?

    ## 1234=2\cdot 617 ## ## 10140=2\cdot 2\cdot 3\cdot 5\cdot 13\cdot 13 ## ## 36000=2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 5\cdot 5\cdot 5\cdot ## Are the answers above correct? Or do I need to put them in canonical form as below? ## 1234=2\cdot 617 ## ## 10140=2^{2}\cdot 3\cdot 5\cdot...
  22. M

    If ## p\neq5 ## is an odd prime, prove that either ## p^{2}-1 ## or....

    Proof: Suppose ## p\neq5 ## is an odd prime. Applying the Division Algorithm produces: ## p=10q+r ## where ## 0\leq r\leq 10 ##, where there exist unique integers ## q ## and ## r ##. Note that ## p\equiv 1, 3, 7 ## or ## 9 ## mod ## 10 ##. This means ## p^{2}\equiv 1, -1, -1 ## or ## 1 ## mod...
  23. M

    Find all prime numbers that divide 50

    Proof: Note that all primes less than 50 will divide 50!, because each prime is a term of 50!. Applying the Fundamental Theorem of Arithmetic produces: Each term k of 50! that is non-prime has a unique prime factorization. Since 48, 49 and 50 are not primes, it follows that all primes...
  24. M

    Given that p is a prime? (Review/verify this proof)?

    Proof: Suppose that p is a prime and ##p \mid a^n ##. Note that a prime number is a number that has only two factors, 1 and the number itself. Then we have (p*1)##\mid##a*## a^{(n-1)} ##. Thus p##\mid##a, which implies that pk=a for some k##\in\mathbb{Z}##. Now we have ## a^n ##=## (pk)^n ##...
  25. M

    If p##\geq##5 is a prime number, show that p^{2}+2 is composite?

    Proof: Suppose p##\geq##5 is a prime number. Applying the Division Algorithm produces: p=6k, p=6k+1, p=6k+2, p=6k+3, p=6k+4 or p=6k+5 for some k##\in\mathbb{Z}##. Since p##\geq##5 is a prime number, it follows that p cannot...
  26. M

    The only prime p for which 3p+1 is a perfect square is p=5?

    Proof: Suppose that p is a prime and 3p+1=n^2 for some n##\in\mathbb{Z}##. Then we have 3p+1=n^2 3p=n^2-1 3p=(n+1)(n-1). Since n+1>3 for ##\forall...
  27. M

    The only prime of the form n^2-4 is 5?

    Proof: Suppose p is a prime such that p=n^2-4. Then we have p=n^2-4=(n+2)(n-2). Note that prime number is a number that has only two factors, 1 and the number itself. Since n+2>1 for ##\forall n \in...
  28. M

    The only prime of the form n^3-1 is 7?

    Proof: Suppose p is a prime such that p=n^3-1. Then we have p=n^3-1=(n-1)(n^2+n+1). Note that prime number is a number that has only two factors, 1 and the number itself. Since n^2+n+1>1 for ##\forall...
  29. karush

    MHB -c5.LCM and Prime Factorization of A,B,C

    Build the least common multiple of A, B, and C Then write the prime factorization of the least common multiple of A, B, and C. $A = 2 \cdot 3^2 \cdot 7 \cdot 13 \cdot 23^8$ $B = 2 3^5 \cdot 5^9 \cdot 13$ $C = 2 \cdot 5 \cdot 11^8 \cdot 13^3$ $\boxed{?}$ ok this only has a single answer...
  30. karush

    MHB -c03 write prime factorization of the LCM of A and B

    Build the least common multiple of A and B a. write the prime factorization of the least common multiple of A and B. $A=2\cdot 3^2\cdot 5\cdot 7^3\cdot 11^3\cdot 13^2$ $B= 3^2 \cdot 5 \cdot 7^2 \cdot 11^2$ $\dfrac{2\cdot \cancel{3^2}\cdot \cancel{5\cdot 7^2} 7\cdot \cancel{11^2} 11\cdot...
  31. F

    Calculate time to defrost Prime Rib roast from freezer to refrigerator

    I don't know where. to even begin inserting numbers here. I know the Temperature would be -5 for the first T and 36 for T sub zero but I do not know how to solve this. I never had Calculus.
  32. D

    I Irreducible polynomials and prime elements

    let p∈Z a prime how can I show that p is a prime element of Z[√3] if and only if the polynomial x^2−3 is irreducible in Fp[x]? ideas or everything is well accepted :)
  33. PhysicoRaj

    Stargazing Level of details in prime focus vs eyepiece images

    I hope this is the right place to ask this. I was clicking the Sun a few days ago with my beginner scope and a DSLR. The scope is a 60mm aperture f/12 refractor and the DSLR is a Canon SL3 (APS-C 6000x4000). First I used a 20mm eyepiece (35x) to view the sun, saw it in all its glory, the...
  34. e2m2a

    A Prime Factorization Theorem and Number Systems

    If you go to "The Abel Prize Interview 2016 with Andrew Wiles" on YouTube, there is a statement made by Andrew Wiles beginning at about 4:10 and ending about 4:54 where he mentions there are some new number systems possible where the fundamental theorem of arithmetic does not hold. I don't...
  35. chwala

    Proving an integer problem about the sum of a square number and a prime number

    i do not seem to understand part ##ii## of this problem...mathematical induction proofs is one area in maths that has always boggled me :oldlaugh: let ##n=3, p=7, ⇒m=4## therefore, ##7=(4-3)(4+3)## ##7=1⋅7## ##1, 7## are integers...##p## is prime. i am attempting part ##iii## in a moment...
  36. karush

    MHB Apc.1.1.13 what is the prime factorization of 30,030

    $\tiny{apc.1.1.13}$ The number 1,001 is the product of the primes 7, 11, and 13 Knowing this, What is the prime factorization of 30,030? a, ${3 \cdot 7\cdot 10\cdot 13}$ b. ${30\cdot 7\cdot 11\cdot 13}$ c. ${2 \cdot 5\cdot 7\cdot 11\cdot 13}$ d. ${3\cdot 7\cdot 10\cdot 11\cdot 13}$ e...
  37. F

    Can prime editing fix every harmful mutation in all our cells?

    https://www.biorxiv.org/content/10.1101/2021.01.08.425835v1.full Can prime editing fix every mutation in every type of cell in the body?. From what I read in the article the editing efficiency of prime editing using adeno-associated virus is 1.82%, so what prevent us from repeating the same...
  38. Greg Bernhardt

    I Math Myth: A prime is only divisible by 1 and itself

    From @fresh_42's Insight https://www.physicsforums.com/insights/10-math-things-we-all-learnt-wrong-at-school/
  39. K

    What is the fastest algorithm for finding large prime numbers?

    Dear PF Forum, Can someone help me with the algorithm for finding a very large prime number? In RSA Encryption (1024 bit? 2048?, I forget, should look it up at wiki for that), Private Keys is a - two prime number packet. Now, what I wonder is, what algorithm that the computer use to find those...
  40. anemone

    MHB Finding the Minimum $x$ for a Prime Product

    Find the minimum value for $x$ where $x\in \mathbb{N} $ and $x^2-x+11$ can be written as a product of 4 primes, which are not necessarily distinct.
  41. diegzumillo

    I Average of prime factors growth

    Hi there, bored physicist here. I wondered about factorization so I made some plots and a model fit to satiate my curiosity, but it only made me more curious. Now I just want the answers! I didn't know which prefix to use. "Hobbyist" seemed more appropriate but we don't have that so I went with...
  42. N

    Set Notation: A x B Product of Powers of Prime Factors

    I get 2^5 x 3^80 Am I correct?
  43. T

    MHB Proving Zp is a Vector Space for Prime p

    How can I prove that Zp is a vector space if and only if p is prime
  44. D

    Cryptography problem involving prime numbers

    Here is my attempt When we raise both sides to the power (p-1)/2, we get x^(p-1)= -1^[(p-1)/2](modp) Looking at p=3(mod4), the possible values of p are {3, 7, 11, 19, 23, 31...}. Putting these values of p into (p-1)/2 we get odd integers. {1, 3, 5, 9, 11, 15...}. So we have x^(p-1) =...
  45. e2m2a

    Consecutive integers and relatively prime numbers

    Summary:: Interested in the history of the proof. Consecutive integer numbers are always relatively prime to each other. Does anyone know when this was proved? Was this known since Euclid's time or was this proved in modern times?
  46. karush

    MHB 412.00.1.12 are relatively prime for all n.

    $\tiny{412.00.1.12}$ Show that $5n+3$ and $7n+4$ are relatively prime for all n. $$ax + by = 1$$ $\begin{array}{ll} \textit{let} &a=5n+3 \textit{ and } b=7n+4\\ \textit{then} &(5n+3)x + (7n+4)y = 1\\ \textit{compute}&(7n+4)=(5n+3)+(2n+1)\\ &(5n+3)=2\cdot(2n+1)+(n+1)\\...
  47. T

    I Significance of discovering a function which computes the n-th prime?

    Let's say the function is of a form F(x), where F(n) gives us the value of the n-th prime number, for all values of n. And it computes and discovers subsequent prime numbers directly without using any form of brute-force computation.If such a function is discovered, how ground-breaking would it...
  48. Z

    Prime Number Detection: Running Time of Algorithm

    Hi, I want to know if the algorithm to find prime number has running time O(sqrt(N)) or O(log^2N). log^2N is better than sqrt(N). Also for large values can it become a pseudo polynomial algorithm? Zulfi.
  49. e2m2a

    I Prime factorization and real exponents

    I know that the prime factorization theorem predicts that a prime number raised to an integer power will never be equal to another prime number raised to a different power. But does this apply to real number powers? For example, suppose there is a prime number raised to some real value, could...
  50. bagasme

    B Aren't There Any Formulas for Prime Numbers?

    Hello all, We know that following formulas failed to produced all prime numbers for any given whole number ##n##: ##f(n) = n^2 - n - 41##, failed for ##n = 41~(f = 1681)## ##g(n) = 2^(2^n) + 1##, failed for ##n = 5~(g = 4,294,967,297)## ##m(n) = 2^n - 1##, failed for ##n = 67~(m =...
Back
Top