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

    Is 1466996987 a Prime Number? Factors and Verification

    Im working on prime numbers and I am stuck with the below number is 1466996987 a prime? in my work i got it as a prime. but in http://www.prime-numbers.org/ http://www.prime-numbers.org/prime-number-1466995000-1467000000.htm this number is not shown if it is not a prime, can anyone...
  2. R

    What is the inverse function of f(x) = c/x^(1/n)?

    Hi, I have written a paper (attached) I would be happy to get comments on it Thanks Roupam PS. (Since, there is no independent research in the math section, I have posted here)
  3. L

    Proofing a Prime Number: A Guide

    How to proof? A prime number p is a factor of a non-zero product of integers a*b if and only if it is a facotr of a and/or b.
  4. K

    Proof of Prime & Congruences: Solving x^2\equiv -2 \mod p

    "Let p be a prime such that there exists a solution to the congruence x^2\equiv - 2\mod p. THEN there are integers a and b such that a^2 + 2b^2 = p or a^2 + 2b^2 = 2p." ============================ I don't see why this is true. How can we prove this using basic concepts? We know that there...
  5. Pengwuino

    Isomorphism to C_n with n prime

    Homework Statement Prove taht if the order n of a group G is a prime number, then G must be isomorphic to the cyclic group fo order n, C_n. The Attempt at a Solution We have previously proven that a group can can be written as S = \{A,A^2,A^3,A^4...,A^n = E\} where E is the identity and the...
  6. M

    Understanding Prime Power Proofs

    Hi, I am having trouble understanding this proof. Statement If pn is the nth prime number, then pn \leq 22n-1 Proof: Let us proceed by induction on n, the asserted inequality being clearly true when n=1. As the hypothesis of the induction, we assume n>1 and the result holds for all...
  7. S

    Proving Relatively Prime Property: Integers, gcd, and the Prime Divisor Problem

    Homework Statement I have to prove the following: Let a1,a2, ...,an be integers and set b=a1*a2*...*an. If c is a nonzero integer and c is relatively prime to each ak, then c and b are relatively prime.Homework Equations Definition of relatively prime: Let a and b be integers, not both zero...
  8. B

    Prove p_{1}p_{2}...p_{n}+1 is Not Divisible by Any of These Primes

    Let p_{1}, p_{2},...,p_{n} be primes. Show that p_{1} p_{2}...p_{n}+1 is divisible by none of these primes.Let p_{1}, p_{2},...,p_{n} be primes Let k \in N Assume p_{1}p_{2}...p_{n}+1=kp_{n} \frac{p_{1}p_{2}...p_{n}}{p_{n}}+\frac{1}{p_{n}}=k p_{1}p_{2}...p_{n-1}+\frac{1}{p_{n}}=k This is a...
  9. A

    Prove, if p and q are distinct prime numbers

    Prove, if p and q are distinct prime numbers, then sqrt(p/q) is irrational. I know how to prove that if p is a distinct prime number, then sqrt(p) is irrational. From there let sqrt(p) = q/r and then prove but for this I'm stuck. Do we let sqrt(p/q) = (a/b)/(c/d).Thanks.
  10. S

    Does Every Integer Greater Than 1 Have a Prime Divisor? A Proof by Contradiction

    Homework Statement Let a be an integer greater than 1. Then there exists a prime that divides a. Homework Equations A prime is an integer that is greater than 1 but not composite The Attempt at a Solution Via Contradiction S={x:x is an integer, x>1, x is not divisible by any prime...
  11. S

    Proving the Divisibility Rule for Prime Numbers: A Homework Statement

    Homework Statement If p is a prime greater than 3, then p leaves a remainder of 1 or 5 when divided by 6. Homework Equations I have been given the definition of composite which is an integer a is composite if there exist integers b and c such that a=bc where both b>1, c>1 3. My...
  12. K

    Greatest common divisor | Relatively prime

    Claim: n! + 1 and (n+1)! + 1 are relatively prime. How can we prove this? Can we use mathematical induction? Base case: (n=1) gcd(2,3)=1 Therefore, the statement is true for n=1. Assuming the statement is true for n=k: gcd(k! + 1,(k+1)! + 1)=1 (induction hypothesis), we need to show...
  13. J

    Calculating Prime Number Counts Using PI(N) Formula up to 10^23

    PI(N) = N /{A * LOG(N)^2 +B * LOG(N) + C}. Note: LOG(N) is the common log. This formula works for N up to 10^23. The accuracy depends on the number of digits after the decimal point in the coefficients A, B & C. I used a Lotus123 spreadsheet to calculate them. My calculated values are...
  14. J

    Multiple of prime p + multiple of (integer<p) = 1 proof?

    Let p be a prime number and x be some positive integer less than p. How do I prove that there exist integers a and b such that 1 = ax + bp
  15. J

    Prime number dividing fractions.

    Let p be a prime number. Let A be an integer divisible by p but B be an integer not be divisible by p. Let A/B be an integer. How do I prove that A/B is divisible by p? This sounds like a simple question but I just can't get it. I'm doing it in relation to proving Fermat's little...
  16. B

    1 maximal subgroup -> prime order

    'Prove that if a finite group G has only one maximal subgroup M, then |G| is the power of a prime' I've somehow deduced that no finite group has only one maximal subgroup, and I'm having trouble seeing where I went wrong. This is what I have: Let H_1 be a subgroup of G. Either H_1 is...
  17. H

    Groups of order p^2 where p is prime

    Homework Statement let p be a prime number and let G be a group with order p^2. the task is to show that G is either cyclic or isomorphic to Zp X Zp. a. let a, not equal to the identity,be an element in G and A=<a>. What's the order of A. b. consider the cosets of A: G/A={A,g2A,...gnA}...
  18. K

    Even Perfect and Prime Puzzle

    Determine all possible even perfect number(s) C such that each of C-1 and C+1 is a prime number.
  19. E

    Product of unique prime factors

    Is there a name for product of the unique prime factors of a number? For example, for the number 12, it would be 3x2=6. Thanks.
  20. A

    The Chinese Remainder Theorem for moduli that aren't relatively prime

    Hello, I am looking into proving that the Chinese Remainder Theorem will work for two pairs of congruences IFF a congruent to b modulo(gcd(n,m)) for x congruent to a mod(n) and x congruent to b mod(m). I have gotten one direction, that given a solution to the congruences mod(m*n), then a...
  21. Char. Limit

    Can 2^n-1 Be Proven to Always Be Prime for Real Integer n Greater Than 1?

    First, remember that the OP is new to pure number theory. We all know that not every number that follows the formula 2n-1 is prime. My question is, without using trial and error, how would you prove or disprove this statement? "All numbers that obey the formula 2n-1, when n is a real...
  22. T

    Relationship between primitive roots of a prime

    Hi all, I've been staring at this question on and off for about a month: Suppose that p is an odd prime, and g and h are primitive roots modulo p. If a is an integer, then there are positive integers s and t such that a \equiv g^s \equiv h^t mod p. Show that s \equiv t mod 2. I feel as...
  23. V

    Algebra: show that x > 1 is prime

    Homework Statement 2.4 Show that x > 1 is prime, iff x doesn't have any divisor t; where 1 < t \leq \sqrt{x}. It is given that x,t \in N. Homework Equations ? The Attempt at a Solution The "iff" thing makes me think; what can I do to show this? I have to show that x (x can be 2, 3...
  24. H

    Algorithm to find out whether an input is a prime number or not

    Homework Statement 1- write an algorithm to find out whether an input is a prime number or not. 2-write aa program to compute square root by Newton method 3-write an algorithm to show an input is perfect or not. 4- Homework Equations The Attempt at a Solution
  25. F

    Solving the Fermat Test for 513: Is it Prime?

    Homework Statement Use the Fermat test to show that 513 is not a prime number. Homework Equations The Attempt at a Solution What i have so far is: n=513 Then i pick an 'a' with 1<a<n Let a=8 So i need to compute a^(n-1) mod n -> 8^512 mod 513 If 8^512 is not...
  26. D

    Divisibility problem with prime numbers

    Homework Statement Let's take a prime number p not equal to 5. Now let's take three integers a,b,c. Prove that if p | (a + b + c) \wedge p | (a^5 + b^5 + c^5), then p | (a^2 + b^2 + c^2) \vee p | (a^3 + b^3 + c^3) Homework Equations I think: (a + b + c)^2 = a^2 + b^2 + c^2 +...
  27. B

    Proving 'If (2^n)-1 is Prime, Then n is Prime' Using Groups

    I was trying to prove the statement "If (2^n)-1 is prime then n is prime". I've already seen the proof using factorisation of the difference of integers and getting a contradiction, but I was trying to use groups instead. I was wondering if it's possible, since I keep getting stuck. So far I've...
  28. S

    How many times will you bring drinks to a home game in a 20 game season?

    Homework Statement You bring the drinks for your soccer team every sixth game. Every third game is a home game. How many times will you bring the drinks to a home game if you have a 20 game season? Homework Equations i did the problem in my head, but I need to show my work to get the...
  29. S

    Prime Factorization Homework Problem 3

    Homework Statement In one part of a musical composition, the triangle player in an orchestra plays once every 12 beats. The tympani player plays once every 42 beats. How often do they play together? Homework Equations don't have any The Attempt at a Solution Insufficient...
  30. S

    Prime Factorization Homework Problem 2

    Homework Statement Presidential elections are held every four years. Senators are elected every 6 years. If a senator was elected in the presidential election year of 2000, in what year would he or she campaign again during a presidential election year? Homework Equations dont know...
  31. S

    Prime Factorization Homework Problem 1

    Homework Statement Margo has piano lessons every two weeks. Her brother Roberto has a soccer tournament every three weeks. Her sister Randa has an orthodontist appointment every four weeks. If they all have activities this Friday, how long will it be before all of their activities fall on...
  32. I

    The prime number distribution in R

    Hi, on my site http://ilario.mazzei.googlepages.com/home I've published a pdf containing the prime numbers distribution in R Ilario Mazzei
  33. I

    The prime numbers distribution in R

    Hi, on my site http://ilario.mazzei.googlepages.com/home I've published a pdf containing the prime numbers distribution in R - Part I Ilario Mazzei
  34. D

    Two Minimal Prime Ideals in k[X,Y]/<XY>

    Homework Statement Show that there are exactly two minimal prime ideals in k[X,Y]/<XY>. P is a minimal prime ideal if it is prime and every subset of P that is a prime ideal is actually P. k is a field. The Attempt at a Solution Prime ideals of k[X,Y] are <0> and <f> for irreducibles...
  35. K

    Divisibility of a prime

    if p is any prime other than 2 or 5, prove that p divides infinitely many of the integers 9, 99, 999, 9999, ... If p is any prime other than 2 or 5, prove that p divides infinitely many of the integers 1, 11, 111, 1111, ... Is there a way to do this problem using modular arithmetic? Thanks
  36. L

    Are There Faster Methods to Determine Primes and Their Factors?

    Hi all, I'm reviewing some problems that involve finding the prime factors of composite numbers (e.g. prime factors of 44 are 2, 2, 11) and I had two questions about prime numbers and factors of composite numbers: 1) Is there some sort of quick test to tell if a number is prime? Or, does...
  37. D

    Relatively prime isomorphism groups

    Homework Statement Show that Z/mZ X Z/nZ isomorphic to Z/mnZ iff m and n are relatively prime. (Using first isomorphism theorem) Homework Equations The Attempt at a Solution Okay, first I want to construct a hom f : Z/mZ X Z/nZ ---> Z/mnZ I have f(1,0).m = 0(mod mn) =...
  38. R

    Möbius function and prime numbers

    Let p_i denote the i-th prime number. Prove or disprove that: 1)\quad \displaystyle S(n) : = \sum_{i = 1}^n \mu(p_i + p_{i + 1}) < 0 \quad \forall n \in \mathbb{N}_0 : = \left\{1,2,3,...\right\}; 2)\quad \displaystyle S(n) \sim C \frac {n}{\log{n}}, where C is a negative real constant. In the...
  39. B

    Is p^2 + 2 always composite if p is a prime number greater than or equal to 5?

    Homework Statement If p>=5 is prime, prove that p^2 +2 is composite. Homework Equations If we took p and divided it by 6 we would get remainder possibilities of 0, 1, 2,3,4,5 The Attempt at a Solution p=6q p^2=36q^2 P^2=6(r) P^2+2=6r+2=2(3r+1) composite p=6q+1...
  40. R

    Twin Prime Sieve - A Unique and Efficient Method for Generating Twin Primes

    http://forums.anandtech.com/messageview.aspx?catid=50&threadid=2331345&enterthread=y" I discovered this sieve a couple of weeks ago and could not find anything similar in the liturature. I made a very ugly proof and sent it off to JAMS, where it was rejected immediately. Since then, we...
  41. K

    Hundred Sum and Prime Puzzle

    Substitute each of the capital letters by a different digit from 1 to 9 to satisfy this cryptarithmetic equation: (P*Q)/R + (S*T*U)/V + W*X = 100, where the 2-digit number WR is prime.
  42. E

    Exploring Color Theory: Prime Colors as a Basis?

    Since prime colors cannot be created by any combination of any other colors, and since composite colors are combinations of the prime colors by definition, does this mean that the prime colors could form a basis for a space of colors? If you split up a color into components, like real vectors...
  43. A

    What is the proof for divisibility of prime numbers?

    Homework Statement a, b, P, and any other numbers introduced are members of the integer set. If P is known to be a prime number, and ab can be divided by P, then prove that either a or b can be divided by P. Homework Equations All properties of real numbers. Need not be explicitly...
  44. Loren Booda

    Longest repeated sequence in the prime counting function

    Is there a longest repeated sequence (congruency) in the prime counting function \pi (x) (that which gives the number of primes less than or equal to x)? Recall that \pi (x) , although infinite, may not be random, and itself starts out with an unrepeated sequence \pi (2)=1 and \pi (3)=2...
  45. Loren Booda

    Conjecture for prime pairs of difference two

    Can it be proven that the number of prime pairs with a difference of two (that is, primes separated by only one even number) approaches infinity?
  46. Z

    Are prime fractals, or have a fractal geometry ?

    are prime fractals, or have a fractal geometry ?? my idea is, if we consider the geometry of primes could we conclude they form a fractal ? , for example if we represent all the primes using a computer, it will give us a fractal pattern. according to a paper...
  47. W

    Remainder of the product of the relatively prime numbers

    Hi all, I had a problem, pls help me. Let b_1 < b_2 < \cdots < b_{\varphi(m)} be the integers between 1 and m that are relatively prime to m (including 1), of course, \varphi(m) is the number of integers between 1 and m that are relatively prime to m, and let B =...
  48. S

    Number of prime factors

    Is there a function f(x) that will give the average number of prime factors for x_1 0<x_1<x, in a way similar to the way that Li(x)/x gives the approximate odds that a number from 0 to x is prime?
  49. Loren Booda

    Average minimum tries for prime factorization

    On average, at least how many factors must one try dividing a number N by to decompose it into primes?
  50. Loren Booda

    Possible convergence of prime series

    Does either \frac{\prod_{2N=n}^\infty{p_n}}{\prod_{2N-1=n}^\infty{p_n}} or \frac{\sum_{2N=n}^\infty{p_n}}{\sum_{2N-1=n}^\infty{p_n}} converge, diverge or oscillate, where N are the natural numbers, and pn is the nth prime?
Back
Top