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

    MHB Need a Cosigner on a New Prime Sieve for a Math Paper

    I am a Savant I count using Primes and Developed this Table Here ... Because I am a Math Savant I never had to go to University so I don't have any papers, I need a Student or Professor willing to Sign off on this Methodology of spotting Primes...Here is the Table with the Formulas all you...
  2. Z

    MHB Help proving prime and permutation

    https://imgur.com/a/9tDdMqt Hey So I am trying to prove this. I tried using linear combinations and not sure how that would help. I am just not familiar with combinatorics and wondering if anyone would enlighten me.
  3. M

    MHB Prime implicants and disjunctive minimal form

    Hey! :o I am looking the follwong exercise: Using the method of Quine-McCluskey, determine the prime implicants for the following switching function and find a disjunctive minimal form. If available, also specify all other disjoint minimal forms. The switching function is...
  4. M

    MHB Quine-McCluskey method: Prime implicants - disjunctive minimal forms

    Hey! :o I am looking at the following: Use the Quine-McCluskey method to determine the respective prime implicants for the following boolean functions and find a disjunctive minimal form. If available, also give all others disjunctive minimal forms. \begin{equation*}f(x_1, x_2, x_3...
  5. Raschedian

    B Do Prime Numbers Follow a Pattern?

    Hello everyone! I was going through a simple high school level mathematics book and got to the following question: n2 - n + 41 is a prime for all positive integers n. You're supposed to find a counter-example and prove the statement false. You could of course sit and enter different...
  6. Ventrella

    A All complex integers of the same norm = associates?

    Are all complex integers that have the same norm associates of each other? I have seen definitions saying that an associate of a complex number is a multiple of that number with a unit. And I understand that the conjugate of a complex number is also an associate. But I am looking for a...
  7. Philip Robotic

    Prime numbers and divisibility by 12

    Homework Statement Prove that if ##p## is a prime number and if ##p>5## then ##p^2-37## is divisible by ##12## Homework EquationsThe Attempt at a Solution So I think that the number ##p^2-37## should be expressed in a way that we can clearly see that it is divisible by 3 and by 2 twice...
  8. M

    Prime factors of a unique form in the each term a sequence?

    This is no homework. I have come across a conjecture in a book called The art of the infinite:the pleasures of mathematics. I want to understand how to prove it. Homework Statement Consider a 3-rhythm starting with 2: ## 2, 5, 8, 11, 14, 17...## The each number in this sequenc has the form...
  9. 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...
  10. YoungPhysicist

    B A new Mersenne prime being found

    A couple days ago, a new Mersenne prime, $$2^{82589933}-1$$ has being found by GIMPS. It’s the number 51st Mersenne prime being found by men. Link to GIMPS’s website: https://www.mersenne.org/primes/?press=M82589933 Edit: According to my calculations using common logarithm, this number should...
  11. Ventrella

    I Mutually disjoint sets of all integer powers?

    I identified what appears to be a partitioning of all integers > 1 into mutually disjoint sets. Each set consists of an infinite series of integers that are all the powers of what I am calling a "root" r (r is an integer that has no integer roots of its own, meaning: there is no number x^n that...
  12. M

    Prime Factors Bounds in a Recurrence

    Let $$g(n)$$ be the numerators of the elements of the recursion $$i(n)=i(n-1)+\frac{1}{i(n-1)}$$ when they are expressed in simplest form, with $$i(0)=1$$. Let $$p$$ be the smallest prime factor of $$g(m)$$. Show that $$p>4m-4$$.Homework Equations Euler's Theorem? The Attempt at a Solution OEIS...
  13. C

    A Is it possible to locate prime numbers through addition only

    I was reading an old thread about multiplying successive prime numbers adding 1 to obtain another prime number. I have worked with prime numbers for several years now and have developed what I best call a bi-linear advancement. It is an open-ended sieve of Eratosthenes. After many, many hours...
  14. evinda

    MHB System of congruences, not relatively prime moduli

    Hello! (Wave) I want to solve the following system of congruences: $$x \equiv 13 \pmod{40} \\ x\equiv 5 \pmod{44} \\ x \equiv 38 \pmod{275}.$$I have thought the following: $$x \equiv 13 \pmod{40} \Leftrightarrow x \equiv 13 \pmod{2^3 \cdot 5}$$ $$x \equiv 5 \pmod{44} \Leftrightarrow x \equiv...
  15. S

    Prove that if p > 3 is a prime number, then p^2 = [....]

    Homework Statement Prove that if p is a prime number larger than 3, then ##p^2## = 6k + 1 for some k ∈ ℤ. Homework Equations * Modulo * Factoring * Distribution or ##(ax + b)^2 = a^2 x^2 + 2abx + b^2## formula The Attempt at a Solution The reason why p mod d = r_i, where r_i is the remainder...
  16. Math Amateur

    MHB Prime and Irreducible Elements in Principal Ideal Domains .... Bland - AA - Theorem 7.2.14 .... ....

    I am reading The Basics of Abstract Algebra by Paul E. Bland ... I am focused on Section 7.2 Euclidean, Principal Ideal, Unique Factorization Domains ... ... I need help with the proof of Theorem 7.2.14 ... ... Theorem 7.2.14 and its proof reads as follows: In the above proof by Bland we...
  17. 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...
  18. Math Amateur

    MHB Principal Ideals and Prime and Maximal Ideals .... Blamnd, AA, Theorem 3.2.19 .... ....

    I am reading The Basics of Abstract Algebra by Paul E. Bland ... I am focused on Section 3.2 Subrings, Ideals and Factor Rings ... ... I need help with the proof of Theorem 3.2.19 ... ... Theorem 3.2.19 and its proof reads as follows: In the above proof by Bland we read the following:"... ...
  19. Math Amateur

    MHB Prime and Maximal Ideals .... Bland -AA - Theorem 3.2.16 .... ....

    I am reading The Basics of Abstract Algebra by Paul E. Bland ... I am focused on Section 3.2 Subrings, Ideals and Factor Rings ... ... I need help with the proof of Theorem 3.2.16 ... ... Theorem 3.2.16 and its proof reads as follows: In the above proof of (3) \Longrightarrow (1) by Bland...
  20. 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...
  21. K

    MHB Large Prime number unable to compute

    Using Wolfram I was able to make certain that the following number was a Prime: 123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901 However finding its position in Wolfram...
  22. Arman777

    Largest Prime Factor of 600851475143

    Homework Statement The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? Homework EquationsThe Attempt at a Solution Here part of the my code #!/usr/bin/python import math N=99 for n in range (2,N): if N%n == 0...
  23. Arman777

    Making an Algorithm to Check Whether a Number is a Prime Number

    1. The problem statement, all variables, and given/known data Create algorithm steps that for a given number (N) is prime or not Homework Equations 3. The Attempt at a Solution I am trying to create an algorithm but I am stuck at some place. Here is my trying. 1-Input a...
  24. B

    Proving x ∉ (x,y)^n for any n ∈ N in F[x,y] Field

    Homework Statement Consider ##F[x,y]##, where ##F## is some field. I've been working on a problem all day and I'm having trouble with this last step. I am trying to show that ##x \notin(x,y)^n## for any ##n \in \Bbb{N}##. Homework EquationsThe Attempt at a Solution Note that ##(x,y)^n =...
  25. lfdahl

    MHB N is a good number, if in any subset of M of size n there are two elements a and b such that a+b is a prime number

    $M$ is the set of squares of the fi rst $20$ natural numbers:\[M = \left\{1^2,2^2,3^2,...,19^2,20^2\right\}\]We say that $n$ is a good number, if in any subset of $M$ of size $n$ there are two elements $a$ and $b$ such that $a + b$ is a prime number. Find the smallest good number.
  26. Ventrella

    A Examples of fractal structure in prime partition numbers?

    Regarding the recent discovery by Ken Ono and colleagues of the fractal structure of partition numbers for primes: a great lever of intuition would be to see a diagram, or any presentation of the numbers that reveals this fractal structure. Perhaps the fractal structure is somehow hidden in a...
  27. 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...
  28. evinda

    MHB Test whether the integer is a prime

    Hello! (Wave) We want to find an efficient algorithm that checks whether an odd number is a prime or not. In order to obtain such an algorithm, one tests the congruence $(X+a)^n \equiv X^n+a$ not "absolutely" in $\mathbb{Z}_n[X]$, but modulo a polynomial $X^r-1$, where $r$ have to be chosen in...
  29. J

    MHB Prime Or Composite - Proof required?

    n^2 - 14n + 40, is this quadratic composite or prime - when n ≤ 0. Determine, all integer values of 'n' - for which n^2 - 14n + 40 is prime? Proof Required. ps. I can do the workings, but the 'proof' is the problem. Many Thanks John.
  30. B

    Union of Prime Ideals Contains an Ideal

    Homework Statement Let ##R## be a commutative ring with identity and suppose that ##A## is an ideal in ##R## contained in the finite union of prime ideals ##P_1 \cup \cdots \cup P_n##. Show that ##A \subseteq P_i## for some ##i##. Homework EquationsThe Attempt at a Solution The base case...
  31. 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
  32. B

    Repeated Roots and Being Relatively Prime w/Derivative

    Homework Statement Let ##f(x) = (x-a_1)...(x-a_n) \in k[x]##, where ##k## is a field. Show that ##f(x)## has no repeated roots (i.e., all the ai are distinct elements in ##k##) if and only if ##gcd(f,f')=1##, where ##f'(x)## is the derivative of ##f## Homework Equations ##(x-a)^2 |f(x)##...
  33. lfdahl

    MHB Determine all prime numbers p such that the total number of positive divisors of A=p^2+1007 (including 1 and A) is less than 7 .

    Determine all prime numbers $p$ such that the total number of positive divisors of $A = p^2 + 1007$ (including $1$ and $A$) is less than $7$.
  34. evinda

    MHB Product of integers that are relatively prime to m

    Hello! (Wave)Let $b_1< b_2< \dots< b_{\phi(m)}$ be the integers between $1$ and $m$ that are relatively prime to $m$ (including 1), and let $B=b_1 b_2 b_3 \cdots b_{\phi(m)}$ be their product. I want to show that either $B \equiv 1 \pmod{m}$ or $B \equiv -1 \pmod{m}$ . Also I want to find a...
  35. lfdahl

    MHB Set of 2015 Consecutive Positive Ints with 15 Primes

    Is there a set of $2015$ consecutive positive integers containing exactly $15$ prime numbers?
  36. F

    Prime factorization proof

    Homework Statement The book wants me to use direct proof. if p is a prime and k is an integer for which 0 < k < p, then p divides ##\left( \frac p k \right)## Homework Equations ##\left( \frac p k \right) = \frac {p!} {k!(p-k)!}## The Attempt at a Solution the fraction line in ##\left( \frac...
  37. M

    How many ways one can put prime numbers to form 3 digit NIP?

    Homework Statement as listed above the question is how many and which three digit NIP can be formed whit the use of prime numbers[/B]Homework Equations nothing currently trying to understand[/B]The Attempt at a Solution well i have found at least 168 primer numbers below 1000 i mean in the...
  38. M

    MHB Is 2 the Only Even Prime Number?

    I know that 2 is an even number. I equate prime numbers with odd numbers. Why is 2 a prime number when it is listed in a group of odd numbers? Is 2 the only, even prime number? Why?
  39. M

    MHB What are the differences between odd, composite, and prime numbers?

    What is the basic difference between an odd, composite and prime number? Give an example for each.
  40. itsabdulbasit

    B Prime Factorization of 5-Digit Numbers

    Hi, Can anyone please tell me any easy way of prime factorizing 5-digit composite numbers from 10,000 to 99,999 with little writing or mentally? Thanks.
  41. awholenumber

    B Factoring a number and prime numbers?

    A number can be factored into a product of its component factors A number can be factored into a product of its prime . But, What exactly is a prime number ? Prime numbers are numbers greater than 1 that are evenly divisible only by themselves and 1 Is it a number that can only be evenly...
  42. Janosh89

    B Are Prime Pairs Ending in 9 or 1 Derived from 20x2-1 Centred 10-Gonal Primes?

    45x2+15x +/-1. ... 59;61 ,209;211 ,449;451 ,779;781 ... 45x2- 15x +/-1 ... 29;31 ,149;151 ,359;361 ,659;661 ... Derived from 20x2-1 can only have factors ending in the digit _1, or _9 .
  43. kupid

    MHB Defining Prime Factors, Greatest Common Factor, Least Common Multiple

    I am a commerce student But i decided to refresh my maths from some basics , i downloaded this book called algebra one for dummies . I have few doubts . What is the difference between Prime factors Greatest common factor (GCF) Least common multiple (LCM) Can i move to algebra factorization...
  44. Math Amateur

    MHB Prime Subfiellds - Lovett, Proposition 7.1.3 ....

    I am reading Abstract Algebra: Structures and Applications" by Stephen Lovett ... I am currently focused on Chapter 7: Field Extensions ... ... I need help with the proof of, or at least some remarks concerning, Proposition 7.1.3 ...Proposition 7.1.3 plus some introductory remarks (proof?)...
  45. Math Amateur

    I Prime Subfiellds - Lovett, Proposition 7.1.3 ....

    I am reading Abstract Algebra: Structures and Applications" by Stephen Lovett ... I am currently focused on Chapter 7: Field Extensions ... ... I need help with the proof of, or at least some remarks concerning, Proposition 7.1.3 ...Proposition 7.1.3 plus some introductory remarks (proof?)...
  46. I

    MHB Useful facts Indeed Finding A Mersenne Prime

    Is there a better way than guess and check?
  47. S

    How to Identify Prime Numbers Using Eratosthenes in C#?

    Mod note: added code tags using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { List<int> number = new List<int>(1000); // int list for 1000 numbers...
  48. PsychonautQQ

    I What is the inequality for prime numbers in the Prime Number Theorem proof?

    I believe this is probably a high level undergraduate question, but i could easily be underestimating it and it's actually quite a bit higher than that. I'm reading the Prime number theorem wikipedia page and I'm in part 4 under Proof sketch where sometime down they give in inequality: x is a...
  49. Jehannum

    I Prime factors of an expression

    I'm reading a book that mentions writing an algebraic expression in terms of its prime factors, for example: x2 - 2 x - 3 = (x + 1) (x - 3) I know what 'prime factors' means for a number but not for an expression. Aren't these just 'factors'?
  50. Eclair_de_XII

    Prove that if three numbers have no prime factor in common...

    Homework Statement "If no prime number ##p## divides a hypothetical solution ##(x,y,z)∈ℕ×ℕ×ℕ## to the equation ##x^3+y^3=z^3##, prove that exactly one of x, y and z is even." Homework Equations Given: ~##∃p:(\frac{x}{p},\frac{y}{p},\frac{z}{p})∈ℕ×ℕ×ℕ## such that ##x^3+y^3=z^3##. In other...
Back
Top