# What is Prime: Definition and 776 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
1. ### 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:
2. ### 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)?
3. ### 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...
4. ### 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...
5. ### 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.)
6. ### 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...
7. ### 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 ##...
8. ### 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...
9. ### 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...
10. ### 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...
11. ### 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 ##...
12. ### 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...
13. ### 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...
14. ### 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 ##...
15. ### 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...
16. ### 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?
17. ### 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} ##...
18. ### 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 ##...
19. ### 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?
20. ### 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...
21. ### 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...
22. ### 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...
23. ### 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 ##...
24. ### 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...
25. ### 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...
26. ### 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...
27. ### 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...
28. ### 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...

46. ### 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...
47. ### 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.
48. ### 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...
49. ### 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 =...
50. ### MHB Solved for Prime using Grade 4 Math Prove me wrong

I Need someone to publish Grade 4 Prime Sequence Series Table, just add my name to it and were partners oh and teach this to your students, this took 40 years to develope https://www.youtube.com/watch?v=eDKK8pP1jiw