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

    Evolving Prime Number Algorithms: Can Computers Duplicate Human Programming?

    there are many prime number algorithm the simplest being dividing all the number less than the prime number. then comes division of number less than or equal half of the number to prime number with the prime number finally the division by all the smaller prime number than the given number...
  2. T

    Modulo and Prime Numbers: Exploring the Multiplicative Function f(x)

    f(x) will give us the smallest integer m such that y^m \equiv 1 \bmod{x} given that x and y are coprime how would one go about showing that this function is multiplicative? I'm trying to do some Number Theory self study, and the problems I'm encountering are quite difficult to figure out from...
  3. K

    Finding f inverse prime at a point c

    Homework Statement Assume the function f defined by f(x)=5x+sin(πx) is strictly increasing on ℝ. Find (f^{-1})'(10) Homework Equations Let I and J be be intervals and let f:I->J be a continuous, strictly monotone function. If f is differentiable at c and if f'(c)≠0, then (f^{-1}) is...
  4. D

    Groups of prime order structurally distinct?

    I have a question. If I have a group G of order p where p is prime, I know from the *fundamental theorem of finite abelian groups* that G is isomorphic to Zp (since p is the unique prime factorization of p, and I know this because G is finite order) also I know G is isomorphic to Cp (the pth...
  5. JeremyEbert

    Proof of ∏(√n) Increment for Centered Polygonal Numbers w/ Prime Index

    Is there a proof that ∏(√n) increments only when n is a centered polygonal number with a prime index? ∏(n) is the prime counting function n=p^2-p+1 for a prime p 3, 7, 21, 43, 111, 157, 273, 343, 507, 813, 931, 1333... http://oeis.org/A119959
  6. A

    Proof that exists prime btw n<p<n

    I'm trying to prove that for n>2, member of Z, exists some prime p s.t. n<p<n!. I have successfully proved it by saying there's no prime btw n and (n-1)!, but I want to prove it with my original thought: first prove for 3, then for n>3: p=1+∏pi (where pi is the ith prime less ≤n) is a prime...
  7. W

    Consecutive integers such that the prime divisors of each is less or equal to 3

    For each integer n > 1, let p(n) denote the largest prime factor of n. Determine all triples (x; y; z) of distinct positive integers satisfying  x; y; z are in arithmetic progression,  p(xyz) <= 3. So far I have come up with 22k + 1, 22k + 1 + 22k, and 22k + 2 other than the solutions...
  8. M

    Prove: Rational Number Squared Has Prime Factors w/ Even Exponent

    I have a theory that i need to prove but I am not quite sure how to mathematically prove that it is true. Theory: When you square a rational number, each of the prime factors has an even exponent. For example, 10 --> If i square 10, which is a rational number, =10^2 =(5^2 x 2^2)...
  9. A

    MHB 6 Successive numbers no one is prime

    is it possible to find a 6 Successive numbers like x , x+1 , x+2 , x+3 ,x+4 ,x+5 such that one one is prime ? Thanks
  10. Fantini

    MHB Solving Congruences with Polynomials: A Prime Challenge

    I'm having trouble with the following question: Construct a polynomial $q(x) \neq 0$ with integer coefficients which has no rational roots but is such that for any prime $p$ we can solve the congruence $q(x) \equiv 0 \mod p$ in the integers. Any hints on how to even start the problem will be...
  11. O

    Prove that sqrt of a prime is irrational

    Homework Statement If a is a prime number, prove that √a is not a rational number. (You may assume the uniqueness of prime factorization.) Homework Equations Per the text: A positive integer a is said to be prime if a > 1 and whenever a is written as the product of two positive...
  12. I

    Question about Euclid and Prime numbers.

    Homework Statement This is a question i just got in the coursera material. Euclid's proof that there are infinitely many primes uses the fact that if p1…,pn are the first n primes, then the number N=(p1...pn)+1 is prime. True or False. The answer was False I answered true and i THINK i...
  13. B

    Is 11 a Prime in the Non-UFD Ring Z[sqrt{-5}]?

    I am trying to prove that 11 is a prime in \mathbb{Z}[\sqrt{-5}]. I noticed that \mathbb{Z}[\sqrt{-5}] is not a UFD so I cannot show that it is irreducible then conclude it is prime. I know that that an ideal is prime if and only if the quotient ring is a domain. I was wondering if it is...
  14. H

    Abstract Algebra: repeating decimals and prime factors

    Homework Statement Prove if m/n has a repeating decimal expansion of period k, and n has no repeated prime factors, then some prime factor of n divides 10k-1 and no number of the form 10j-1 for 1 ≤ j < k Homework Equations The Attempt at a Solution I know that if a decimal...
  15. H

    Prove is p is prime and p = 1 (mod 4), then x^2 = -1 (mod p) has a solution

    Homework Statement Prove that if p is prime and p \equiv 1 (mod 4), then x^{2} \equiv -1 (mod p) has a solution (x). Homework Equations We already have proved (p-1)! \equiv -1 (mod p) Hint: Use the properties of Z_{p} - a field that partitions the integers into p equivalence classes...
  16. FeDeX_LaTeX

    Prime Number Arithmetic Progression

    "Determine the least possible value of the largest term in an arithmetic progression of seven distinct primes." I really have no clue what to do here. Is there a general tactic that you can use to do this, other than trial and error? Some experimenting gives you these of arithmetic...
  17. M

    What are some applications of prime numbers other than cryptography

    I was just wondering what are some applications of prime numbers other than cryptography? Also i heard that there is no certain *equation or prediction of Prime numbers? For example, there is no way to explain prime numbers with an equation. What happens if one was able to find one...
  18. D

    If w is an even integer, then w^2 - 1 is not a prime number.

    hello, I am trying to solve this problem: If w is an even integer, then w^2 - 1 is not a prime number. my current working. prove by contradiction If w is a even integer then w^2 -1 is a prime number. if w = 2x then w^{2} -1 = 4x^{2} -1 I am not sure where to go from here, maybe congruence...
  19. P

    Relative Prime Gaps: Fast Algorithm for Calc.

    Given the first N prime numbers what is the largest gap between consecutive numbers that are relatively prime to all of them? Anyone know of a fast algorithm for calculating this?
  20. S

    Prime numbers and cryptography

    Hello, this is rather vague but I had a lecture around a year ago about prime numbers and how a mathematician (Hardy or Euler?) found a proof to do with prime numbers and then this lead on to cryptography and internet security... That's all I can particularly remember but I'm wondering on...
  21. A

    Prove by Contradiction: For all Prime Numbers a, b, and c

    Homework Statement Prove by Contradiction: For all Prime Numbers a, b, and c, a^2 + b^2 =/= c^2 Homework Equations Prime number is a number whose only factors are one and itself. Proof by contradiction means that you take a statement's negation as a starting point, and find a...
  22. A

    Is There a Recognizable Pattern in the Distribution of Prime Numbers?

    Hello everybody , I'm Adrian , new stupid among apes :biggrin: This might sound silly or obvious according to a viewer's point of view and knowledge on the matter but,is there any visible undeniable linear order or logical distinguishable pattern in the distribution of primes of which humanity...
  23. M

    Pells equation for D prime and =n*n-3

    I, retired physicist (working with high level radioactive waste regulation) and now amateur mathematician, have been looking at solutions for the Pell equation x*x-D*y*y=1, and I have in particular looked at the case D=n*n-3 which contains solutions with high values for x and y, such as for...
  24. C

    Proof about m/nth root of a prime.

    Lets take a prime number and raise it to m/n where m and n are coprime. x,y are coprime and I want to show that this is irrational. Proof: let's assume for the sake of contradiction that P^{\frac{m}{n}}=\frac{x}{y} P is prime and m,n,x,y are integers. no we take both sides to the...
  25. D

    Every prime greater than 7 can be written as the sum of two primes

    "Every prime greater than 7, P, can be written as the sum of two primes, A and B, and the subtraction of a third prime, C, in the form (A+B)-C, where A is not identical to B or C, B is not identical to C, and A, B, and C are less than P." True?
  26. D

    Every prime greater than 7 can be written as the sum of two primes

    "Every prime greater than 7, P, can be written as the sum of two primes, A and B, and the subtraction of a third prime, C, in the form (A+B)-C, where A is not identical to B or C, B is not identical to C, and A, B, and C are less than P." True?
  27. S

    Prove that this number is not a prime number

    Hello all. I came across this question which is "prove that (5^125-1)/(5^25-1) is composite". I am not even getting a clue as to how I can attack this problem. Any help would be greatly appreciated. Please note that we need to prove (5^125-1)/(5^25-1)=1+5^25+5^50+5^75+5^100 as composite and not...
  28. Karlx

    Discovering Prime Numbers & Riemann's Zeta Function

    Hi everybody. I would like to find a book about the Distribution of Prime Numbers and the Riemann's Zeta Function. I know about the "classical" books: 1) Titchmarsh's "The Theory of the Riemann Zeta-Function" 2) Ingham's "The Distribution of Prime Numbers" 3) Ivic's "The Riemann...
  29. F

    A Question About Prime Numbers and Goldbach's Conjecture

    I know that one of Goldbach's conjectures is that every even number is the sum of 2 primes. So, I was wondering if there was a definite, largest prime number ever possible. I know that as a number gets larger, there are more numbers that can be tried to divide it (At least I think so), and I...
  30. T

    G is cyclic and |G| = p^n, p is prime <=> H,K Subgroups, H⊆K or K⊆H

    Homework Statement Show that the following conditions are equivalent for a finite group G: 1.G is cyclic and |G| = p^n where p is prime and n\geq 0 2.If H and K are subgroups of G, either H⊆K or K⊆H. The Attempt at a Solution 1 => 2. Let H,K be subgroups of G = <g> where o(g)...
  31. T

    Show that m and n relatively prime if and only if no prime divides both

    Homework Statement Show that m and n are relatively prime if and only if no prime divides both. The Attempt at a Solution Now, if m and n are relatively prime, we have gcd(m,n) = 1. All the common divisors of m and n must divide gcd(m,n), but the only divisors of 1 are 1 and -1. Thus...
  32. C

    MHB Prove/disprove inequality involving sums of consecutive twin prime pairs - - (My own problem)

    . . Let \ \ p_n \ \ = \ \ the \ \ nth \ \ prime \ \ number.Examples:p_1 \ = \ 2 p_2 \ = \ 3 p_3 \ = \ 5 p_4 \ = \ 7- - - - - - - - - - - - - - - - - - - - - - - - - - - - Let \ \ n \ \ belong \ \ to \ \ the \ \ set \ \ of \ \ positive \ \ integers. Prove (or disprove) the following:p_n \ +...
  33. J

    Hydrualic prime mover - the accumulator

    I am working on a hydraulic system for a vehicle of nominal weight. Of course, the hp required to keep it at reasonable highway speeds is reasonably in the 30-40 hp range. My issue is energy storage for acceleration (s). This of course is substantial (like 150hp, over 8-10 seconds). My...
  34. J

    Automotive Could a 100% hydraulic system as a vehicle prime mover work?

    Given: I understand that there would have to be the equivalent energy source to drive the pump. That I will look to later (my gut says the real issue), but for the purposes of this discussion, assume endless power from a source of electricity or hydraulic pressure/flow, and you have to build a...
  35. I

    Can prime fields act two ways on the same abelian group?

    A problem asks to find an abelian group V and a field F such that there exist two different actions, call them \cdot and \odot, of F on V such that V is an F-module. A usual way to solve this is to take any vector space over a field with a non-trivial automorphism group, and define r\odot \mu...
  36. N

    [number theory] x²-a = 0 no solution => n not prime

    Homework Statement Define n = 3^{100}+2. Suppose x^2-53 \equiv 0 \mod n has no solution. Prove that n is not prime. Homework Equations / The Attempt at a Solution Well, I suppose that I'll have to prove that some identity which should be true for n prime is not satisfied in the above case...
  37. D

    Theorem on Division by a Prime

    Homework Statement I am working my way through the Theorem on Division by a Prime. "Let p be a prime number.Then for all integers x and y, if p divides xy, then p divides x or p divides y. The proof is being done by complete induction. Proof. Let x be a whole number p a prime numberk and y be...
  38. N

    Prime Ideals: Abstract Algebra Example

    This is a basic abstract algebra question. Q1. Is this (x1, x2) a prime ideal in C[x1, x2, x3, x4] ? Q2. What about this: (x1 x4-x2 x3, x1 x3-x22)? Q3. Is this a prime ideal (this is the twisted cubic in projective 3-space): (x1 x4-x2 x3, x1 x3-x22, x2 x4-x32)? Thanks everyone.
  39. A

    Prime Number Theorem and Its Expansion: A Puzzling Equation

    Hi there, working on Prime Number Theorem and the book gives an equality that I probably should know... \frac{1}{log(2x)}= \frac{1}{logx}- \frac{log2}{log^{2}x} + O(\frac{1}{log^{3}x}) and \frac{1}{log^{2}2x} = \frac{1}{log^{2}x} + O(\frac{1}{log^{3}x}) Not sure what kind of...
  40. C

    Uhh help with this proof then x is prime .

    uhh! help with this proof """" then x is prime""". Homework Statement For a positive integer x≥2. "if x is not divisible by any positive integer n satisfying 2≤n≤√x then x is a prime number" a) show that the above statement is true . b) Is the statement still true if the condition...
  41. B

    Maximal subgroups of solvable groups have prime power index

    I would like to ask if somebody can verify the solution I wrote up to an exercise in my book. It's kind of long, but I have no one else to check it for me :) Homework Statement If H is a maximal proper subgroup of a finite solvable group G, then [G:H] is a prime power.Homework Equations Lemma...
  42. Whovian

    C/C++ C++ Prime Testing: Find & Fix Errors

    Alright. I know how incredibly inefficient this algorithm is, but I felt like giving this a whirl. #include <iostream> #include <cmath> using namespace std; bool prime(int x) { bool j = true; for (double i = 2;i == x;i++) { if (x/i == floor(x/i)) { j = false; } } return j; }...
  43. C

    Proof about a prime between k and 2k.

    If K is a prime is there a prime between k and 2k. Obviously this is a weaker version of a prime between n and 2n that was proved by Erdos and Chebyshev. Let's assume that their isn't a prime between k and 2k. This would imply that all the numbers between k and 2k would have to be...
  44. T

    Number Theory least divisor of integer is prime number if integer is not prime

    Homework Statement The question is not really a question from a book but rather a statement that it makes : it says " Obviously the least divisor[excluding 1] of an integer a is prime if a itself is not prime." I kind of believe this statement but I'm having trouble proving the general case...
  45. E

    Finding the Product of Primes: A Number Theory Puzzle

    Hi i found a question in number theory, involving two equations, it goes as follows: Let p1, p2, p3 and p4 be 4 different prime numbers satisfying the equations 2p1 + 3p2 + 5p3 + 7p4 = 162 11p1 + 7p2 + 5p3 + 4p4 = 162 Find all possible values of p1p2p3p4. Not knowing what to do, i used the...
  46. R

    To show a ring of order p (prime) is isomorphic to the integers mod p.

    If R is a finite ring of of order p where p is prime, show that either R is isomorphic to Z/pZ or that xy=0 for all x,y in R I know that both R and Z/pZ have the same number of elements (up to equivalence) and that R isomorphic to Z/pZ implies R must be cyclic (I think) but am otherwise...
  47. B

    Factoring large N into prime factors

    Hi, I am writing up a project based on an algorithm for factoring large numbers, I have reached seemingly simple point where I am stuck, I wonder if anyone can help me? I am trying to factor a large N such that N=pq for unknown primes p and q, I have described a method to find a value for...
  48. P

    Isomorphism of relatively prime groups

    Homework Statement Allow m,n to be two relatively prime integers. You must prove that Z(sub mn) ≈ Z(sub m) x Z(sub n) Homework Equations if two groups form an isomorphism they must be onto, 1-1, and preserve the operation. The Attempt at a...
  49. P

    Isomorphism and Generators in Z sub P

    Homework Statement Let P be a prime integer, prove that Aut(Z sub P) ≈ Z sub p-1 Homework Equations none The Attempt at a Solution groups must preserve the operation, be 1-1, and be onto and they can be called an isomorphism. Z sub p-1 has one less element in it so and all the...
  50. qpwimblik

    Some Flat Equation Prime Number Aproximations

    for estimating Pn...
Back
Top