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
Recent contents Top users
  1. FallenApple

    I Real reason why 1 isn't prime?

    It's very interesting that primes are considered the atoms of numbers, but yet, 1 isn't prime. It makes sense because one isn't an "atom" for numbers in the multiplication sense. That is, 6=2*3 =1*2*3 =1*1*2*3 =1*... So clearly 1 cannot be prime. But in the addition sense, all numbers are made...
  2. G

    Checking a proof of a basic property of prime numbers

    Homework Statement Prove: If p is prime and m, n are positive integers such that p divides mn, then either p divides n or p divides m. Is anyone willing to look through this proof and give me comments on the following: a) my reasoning within the strategy I chose (validity, any constraints or...
  3. Kevin McHugh

    I Symmetry involving prime multiplication modulo 8

    I was reading Armstrong's Groups and Symmetry the other day and saw this table. It has beautiful symmetry. It is the the prime numbers multiplied modulo 8. It creates one of the most elegant things I've ever seen. What is so special about modulo 8 that creates such a symmetric matrix of primes?
  4. CaptainJonathanNorth

    B Is Infinity a Prime Number: The Confusing Concept of Infinity Explained

    Infinity is both a number and a concept. I asked my 10 year old niece what kind of number infinity might be and she said, "It's a composite number." But I want to think about weather infinity is a prime number? Clearly if you divide infinity by any number, you get infinity. Also if you divide...
  5. S

    I Normalizer of a subgroup of prime index

    Hello! Can anyone help me with this problem? If H is a subgroup of prime index in a finite group G, show that either N(H)=G or N(H) = H. Thank you!
  6. lfdahl

    MHB Prove, that the decimal representation: pk = 11111....1 exists for every prime, p > 5.

    Let $p$ be a prime number exceeding $5$. Prove that there exists a natural number $k$ such that each digit in the decimal representation of $pk$ is $1$ : $pk = 1111...1$
  7. J

    MHB Odd/Even and Prime: Check 819877966 Numbers

    Hi everyone, been a busy week and I've got midterm cal 2 on monday so i need to get this done as fast as possible so i can focus on my math. I've got two assignments each requiring me to input 819877966 as a user number and its two parts 1.) is to break the usernumber into individual numbers...
  8. D

    Proving 5 integers to be pairwise relatively prime

    Homework Statement Let n be an integer. Prove that the integers 6n-1, 6n+1, 6n+2, 6n+3, and 6n+5 are pairwise relatively prime. Homework EquationsThe Attempt at a Solution I tried to prove that the first two integers in the list are relatively prime. (6n-1)-(6n+1)=1 (trying to eliminate...
  9. Math Amateur

    MHB Prime and Maximal Ideals in PIDs .... Rotman, AMA Theorem 5.12

    I am reading Joseph J. Rotman's book: Advanced Modern Algebra (AMA) and I am currently focused on Section 5.1 Prime Ideals and Maximal Ideals ... I need some help with understanding the proof of Theorem 5.12 ... ...Theorem 5.12 reads as follows: In the above text Rotman writes the following:"...
  10. Math Amateur

    I Prime and Maximal Ideals in PIDs ... Rotman, AMA Theorem 5.12

    I am reading Joseph J. Rotman's book: Advanced Modern Algebra (AMA) and I am currently focused on Section 5.1 Prime Ideals and Maximal Ideals ... I need some help with understanding the proof of Theorem 5.12 ... ...Theorem 5.12 reads as follows: In the above text Rotman writes the following:"...
  11. H

    B Connections with Prime numbers and Quantum Physics?

    Hello I'm hard at work trying to find a pattern for the prime numbers and this keeps cropping up. To be honest though, to me it comes across like pseudo science. I mean I never really hear people talk about it. This seems an obvious thing to look into but I don't know anyone who does. Prime...
  12. F

    What properties do prime numbers exhibit?

    Mod note: moved from a homework section What properties do prime numbers exhibit which can be used in proofs to define them? Like rational numbers have a unique property that they can be expressed as a quotient of a/b. Even numbers have a unique property of divisibility by 2 and thus they can be...
  13. R

    MHB Prove prime test conjecture.

    I was examining the AKS and discovered this conjecture. Please prove the following true or false. Let n be an odd integer >2 then n is prime IFF $\left( \begin{array}{c} n-1 \\ \frac{n-1}{2} \\ \end{array} \right) \text{ $\equiv $ } \pm 1$ mod n
  14. Mr Davis 97

    Why is the common difference of an arithmetic sequence relatively prime to 3?

    I'm solving a problem, and the solution makes the following statement: "The common difference of the arithmetic sequence 106, 116, 126, ..., 996 is relatively prime to 3. Therefore, given any three consecutive terms, exactly one of them is divisible by 3." Why is this statement true? Where does...
  15. evinda

    MHB Prime Subfield of Field F: Isomorphic to $\mathbb{Q}$

    Hello! (Wave) Could you explain to me why the prime subfield of any field $F$ could be isomorphic to $\mathbb{Q}$ ? How do we find the prime subfield?
  16. micromass

    Unlock the Prime Number Riddle

    First a definition: given a natural number ##a_na_{n-1}...a_0##, a subnumber is any number of the form ##a_k a_{k-1}...a_{l+1}a_l## for some ##0\leq l \leq k \leq n##. I think an example will be the easiest way to illustrate this definition: the subnumbers of ##1234## are...
  17. DuckAmuck

    I Question about the gaps between prime numbers

    Is there any prime number pn, such that it has a relationship with the next prime number pn+1 p_{n+1} > p_{n}^2 If not, is there any proof saying a prime like this does not exist? I have the exact same question about this relation: p_{n+1} > 2p_{n}
  18. Math Amateur

    I Why do some people only define prime elements in integral domains?

    On page 284 Dummit and Foote in their book Abstract Algebra define a prime element in an integral domain ... as follows: My question is as follows: What is the definition of a prime element in a ring that is not an integral domain ... does D&F's definition imply that prime elements cannot exist...
  19. Math Amateur

    MHB Prime Element in a Ring .... ?

    On page 284 Dummit and Foote in their book Abstract Algebra define a prime element in an integral domain ... as follows:My question is as follows: What is the definition of a prime element in a ring that is not an integral domain ... does D&F's definition imply that prime elements cannot exist...
  20. DaTario

    I Prime Number Theorem: the meaning of the limit

    Hi All. I have a doubt concerning the limit: $$ \lim_{n \to \infty} \frac{\pi (n)}{Li(n)} = 1 $$. This mathematical statement does not imply that both functions converge to the same value. The main reason is that both tend to infinity as n tend to infinity. I would like to ask you if it is...
  21. A

    Which prime mover do you think will win?

    I already know the answer to this easy question. Just curious what people know on the internet. A 36 volt DC electric motor, model P66SR274 is rated for 1865 watts (2.5 HP) at 2000 RPM, and its output shaft is to be direct coupled to a shaft that is 25mm in diameter. The power supply is 3X, 12...
  22. mathworker

    MHB How Can You Find Numbers Whose Sum of Divisors is a Perfect Square?

    Hello I am reading "The Theory of Numbers, by Robert D. Carmichael" and stuck in an exercise problem, Find numbers x such that the sum of the divisors of x is a perfect square. I know sum of divisors of a x = p_1^{{\alpha}_1}.p_2^{{\alpha}_1}...p_n^{{\alpha}_1} is Sum of divisors...
  23. Albert1

    MHB Max 3-Digit Prime Divisor of 2000!/(1000!1000!)

    giving : (1) $p$ is a divisor of $\dfrac{2000!}{1000!1000!}$ (2) $p$ is a prime (3) $p$ is a 3-digit number find $max(p)$
  24. M

    MHB (x) and (x,y) are prime ideals of Q[x,y]

    Hey! :o I want to show that the ideals $(x)$ and $(x,y)$ are prime ideals of $\mathbb{Q}[x,y]$ but only the second one is a maximal ideal. We have to show that $\mathbb{Q}[x,y]/(x)$ and $\mathbb{Q}[x,y]/(x,y)$ are integral domains, right? (Wondering) How could we show it? Could you give me...
  25. M

    MHB Exploring Prime and Maximal Ideals in $\mathbb{Z}_{12}$ Ring

    Hey! :o I want to find the prime and maximal ideals of the ring $\mathbb{Z}_{12}$. Could you give me some hints what we could do to find them? (Wondering)
  26. D

    A Equation with three consecutive prime numbers

    Solve the equation np_n+(n+1)p_{n+1}+(n+2)p_{n+2}=p^2_{n+2} where n\in \mathbb N^* and p_n , p_{n+1} , p_{n+2} are three consecutive prime numbers. ------------------------------------- A solution is n=2,p_2=3,p_3=5,p_4=7. May be other solutions?
  27. R

    B Consecutive integers, each relatively prime to some k

    Hello, Say I have some integer n in some interval such that, gcd(n, k) = gcd(n + 1, k) = 1, for some composite odd integer k >= 9 I want to know if such n exists in that interval. To know that one exists suffices. I have tried to think in terms of modular arithmetic where for all primes in k...
  28. Ackbach

    MHB Fascinating Discovery about Prime Numbers

    I found this article fascinating. Imagine overlooking something so simple for so long!
  29. G

    Print Highly Prime Numbers in an Input Interval | C Program

    Homework Statement Write a program that will print all highly prime numbers from the input interval <a,b>. Prime number is highly prime if deletion of every digit from right is a prime. Example: 239 is highly prime because 239,23,2 are primes. 2. The attempt at a solution Could someone point...
  30. anemone

    MHB Is 2017^4+4^{2017} a Prime Number?

    Is $2017^4+4^{2017}$ a prime?
  31. anemone

    MHB Exploring the Primality of 3^(2520)+4^(4038)

    Is $3^{2520}+4^{4038}$ a prime?
  32. K

    What is the Theorem regarding the number of polynomial zeros modulo p and H?

    Hello I am currently learning some of the basics of number theory, and struggling to understand this Theorem. Could someone please explain it with maby a simple example? :) THRM:(Number of polynomial zero mod p and H) Let p be a prime number and let H be a polynomial that is irruducible modulo...
  33. RJLiberator

    [Abstract Algebra] GCD and Relatively Prime Proof

    Homework Statement If gcd(f(x),g(x)) = 1 and m,n ∈ ℕ, show that gcd(f(x)^m, g(x)^n) = 1. Homework EquationsThe Attempt at a Solution So I had previously proved this for non-polynomials: gcd(a,b)=1 then gcd(a^n,b^n)=1 Proof: a = p1*p2*...*pn b = p1*p2*...*pm then a^n = p1^n*p2^n*...*pn^n...
  34. E

    Looking for a prime number benchmark

    I am trying to find a benchmark program that will find all of the numbers between 1 and 1000 and give a time that it takes
  35. RJLiberator

    Abstract algebra Polynomials and Prime

    Homework Statement Let g(x) ∈ ℤ[x] have degree at least 2, and let p be a prime number such that: (i) the leading coefficient of g(x) is not divisible by p. (ii) every other coefficient of g(x) is divisible by p. (iii) the constant term of g(x) is not divisible by p^2. a) Show that if a ∈ ℤ...
  36. kaliprasad

    MHB What is the highest 3 digit prime factor of ${2000 \choose 1000}$?

    find the highest 3 digit prime factor of ${2000 \choose 1000}$
  37. RJLiberator

    Relatively prime proof involving a^n and b^n

    Homework Statement Show that if a, b, n, m are Natural Numbers such that a and b are relatively prime, then a^n and b^n are relatively prime. Homework Equations Relatively prime means 1 = am + bn where a and b are relatively prime. gcd(a,b) = 1 We have a couple corollaries that may be...
  38. kaliprasad

    MHB What is the significance of the recent discovery of the largest prime number?

    for details refer http://www.nytimes.com/2016/01/22/science/new-biggest-prime-number-mersenne-primes.html?_r=0
  39. DrClaude

    New largest known prime found

    Source: http://www.mersenne.org/ See also the press release.
  40. RJLiberator

    Proof: There Exists a prime p such that p=< sqrt(n)

    Homework Statement Question: Let n> 1 be an integer which is not prime. Prove that there exists a prime p such that p|n and p≤ sqrt(n). Homework Equations Fundamental theorem of arithmetic: Every integer n >1 can be written uniquely (up to order) as a product of primes. The Attempt at a...
  41. S

    Is a^2+c Always a Prime Number Under Certain Conditions?

    dear sir, i wish to know if i am correct. a^2+c can be a prime number provided if a is even then c is odd or vice versa, also a and c are not multiple of same number. and c is not a negative square of any number. finally prime number is unique combination of 1,2,and other powers of 2. each power...
  42. T

    MHB Beginner Exercises on Prime numbers and Equality / Inequality proofs

    Does anyone know a good resource for exercises on these topics?
  43. T

    MHB Prime numbers proof by contradiction

    For prime numbers, $a$, $b$, $c$, $a^2 + b^2 \ne c^2$. Prove this by contradiction. So, I get that $a^2 = c^2 - b^2 = (c - b)(c +b)$ And I get that prime numbers are the product of 2 numbers that are either greater than one, or less than the prime numbers. But I'm unsure how to go from here.
  44. R

    Comp Sci C++ Sum of prime numbers in matrix

    Homework Statement My Program is not showing the sum value or not returning it. A blank space is coming.Why that is so? Homework Equations Showing the attempt below in form of code. The Attempt at a Solution #include<iostream.h> #include<conio.h> Prime_Sum(int arr[30][30],int m, int n); void...
  45. N

    Is This Simple Algorithm the Key to Finding the Next Largest Prime Number?

    I have a simple algorithm that appears to generate many primes (or semi-primes with relatively large factors). By 'relatively large', I mean large in relation to inputs. I have tested this algorithm for small values, and of the forty (six-digit) numbers produced, 22 are prime, 16 are...
  46. N

    Prime Numbers Between Two Quadratics: A Useful Result?

    Would it be a useful result to know there is at least one prime between 16x^2+4x-1 and 16x^2+8x-5 for any odd natural number x?
  47. a1call

    A Is there a formula for generating prime numbers and proving their primality?

    I have figured out a formula that generates prime numbers along with the proof that all such generated numbers are primes. The way it works is that you have to input consecutive prime numbers staring from 2 and ending at some Pn. And no it's not primorial minus or plus 1. Is this of any value...
  48. alexmahone

    MHB Group Theory: Finite Group Has Prime Order Element

    Show that if G is a finite group, then it contains at least one element g with |g| a prime number. (|g| is the order of g.) Hints only as this is an assignment problem.
  49. Isaacsname

    Is there any indication the Egyptians understood coprimes ?

    My apologies for such an unorthodox question, move if necessary I've not been able to find much on this, aside from that there is some conjecture { who, I have no idea } that they have understood and cataloged prime numbers. If they cataloged prime numbers they certainly understood coprime...
  50. F

    MHB Next set of prime birthdays for three brothers

    Hello! I have the following problem: Three brothers are aged 6, 10 and 14 years old. Will they ever, in the future, have a prime number birthday the same year? Looking at all of the prime numbers between 1 and 100, it seems that they won't. So I guess this is the same thing as saying: are...
Back
Top