Prime Definition and 777 Threads

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

    Can two consecutive odd primes sum to a product of three integers?

    Prove that the sum of any two consecutive odd prime numbers can always be written as the product of three integers, all greater than 1. I'm sure this is simpler than it looks. Any help?
  2. S

    Relatively Prime Quadratic Integers

    Hello everybody. I found this example online and I was looking for some clarification. Assume 32 = \alpha\beta for \alpha,\beta relatively prime quadratic integers in \mathbb{Q}[i]. It can be shown that \alpha = \epsilon \gamma^2 for some unit \epsilon and some quadratic \gamma in...
  3. T

    Element in a ring mapping one prime to the next

    Homework Statement Let {p_n}n>0 be the ordered sequence of primes. Show that there exists a unique element f in the ring R such that f(p_n) = p_n+1 for every n>0 and determine the family I_f of left inverses of f. Homework Equations The ring R is defined to be: The ring of all maps...
  4. M

    Is one considered a prime number?

    Is one considered a prime number? I know the definition of a prime number is any number that is constituted only by 1 and itself; does this include one? Why or why not?
  5. C

    Exploring Residues: A Key to Understanding the Frequency of Prime Numbers

    Is there a rule governing the frequency of prime numbers? Also, I've heard that all primes greater than 3 are of the form 6k+1 or 6k-1. I'm assuming that this is because 6 is the lcm of 2 and 3 (the two primes lesser than 3), and the +1,-1 is because if the number was in a range greater than...
  6. S

    Is the set of prime number finite? if?

    Let's say I have this statement. {a^p | p is prime and p < N} a is considered a string so so a^2 = aa, a^3 = aaa and so on... anyway, in this case, since it says that p< N, then is mean that p will be finite right??
  7. R

    Prime Indices & the Divisors of (p'_n - 1): A Lattice-Related Question

    Prime Indices & the Divisors of p'_n - 1 such that Divisors & Indices are equivalent for... p'_n an element of {N} | d'(n) < or = to 2 This set of integers is equivalent to 1 Union the Prime Numbers aka "Primes at the beginning of the 20th Century" where... d'_n denotes the number of divisors...
  8. B

    Prove/Disapprove n2 + 3n + 1 is prime for n > 0

    Prove or disprove that n2 + 3n + 1 is always prime for integers n > 0. I am at a complete loss. I don't even know where to begin. Following are the formulas that I feel might be relevant: 1) a and b are relatively prime if their GCD(a, b) = 1 2) If a and b are positive integers, there...
  9. K

    Prime Factorial Proof: Existence of a Prime Between n and n!

    Prove or disprove: If n is an integer and n > 2, then there exists a prime p such that n < p < n!.
  10. V

    Prime values of integer polynomials

    Hey there, physics forums! A question occurred to me the other day: Is it true that if f \in \mathbb{Z}[x] is monic and irreducible over \mathbb{Q} , then for at least one a \in \mathbb{Z} , f(a) is prime? I can't prove it, but I suspect it's true. Does anyone know if this problem...
  11. O

    Prime divides its binomial coefficient?

    Hi all, this homework problem's been driving me nuts. It seems like it's probably pretty straightforward and I'm missing something obvious, but I just can't work it out. Homework Statement prove that if p is a prime number that p|B(p,m) where B(p,m) is the ordinary binomial coefficient...
  12. T

    Twin Prime Sieve: Calculate All Twins Less Than N - Todd's Version

    I am interested in twin primes and have not been able to find a simple "sieve" type function to calculate them. I created my own. You can find it at this URL: http://www.just-got-lucky.com/math/TwinPrimeSieve_08102010_v01.pdf It calculates all the twins less than N. I also wrote a...
  13. arivero

    Is this a route to the prime number theorem?

    I notice that the trick to define Dirichlet Eta Function can be repeated for each prime number, let p a prime, and then \eta_p= (1 - p^{-s}) \zeta(s) - p^{-s} \zeta(s) = (1 - 2 p^s) \zeta(s) So each prime p defines a function \eta_p that adds a family of zeros at s= (\log 2 + 2 n i \pi) /...
  14. S

    Arithmetic progression of prime numbers

    what is the maximum number of terms can a arithmetic progression of only prime numbers have?
  15. E

    How many prime numbers have we actually solved

    how many prime numbers have we actually solved,,, how can we say that there is no end to prime when we can't even count that high, i think sooner or later all numbers higher than primegod would be not prime
  16. K

    Can a Group of Prime Order Be Proven Cyclic Using Only Basic Group Theory?

    How to prove that a group of order prime number is cyclic without using isomorphism/coset? Can i prove it using basic knowledge about group/subgroup/cyclic(basic)? I just learned basic and have not yet learned morphism/coset/index. Can you guys kindly give me some hints or just answer...
  17. D

    How can the prime number theorem be used to understand this proof?

    could someone please help me understand this proof given in an article by William Miller (attatched) its supposed to follow from the prime number theorem that given, A(x) which is the sum of all primes less than or equal to x and theta(x) which is the sum of the log of all primes...
  18. V

    K-th Prime Proofs & Co-Prime Numbers

    I am having a hard time making head way on two problems related to the k-th prime and one about co-primes that I would really appreciate some help and/or direction! Prove that: (let pk be the k-th prime) and Regarding co-primes... is there any way to find a set of four numbers that are...
  19. S

    Finding Prime Numbers in 2010: Is It Possible?

    Is it possible to write the 2010 numbers from 1 a 2010 in some order so that the 6933 digit number you get is prime?
  20. L

    Least Prime Number for N=7999999999: Interval (x; x+100)

    if N=7999999999 what are the least prime number, which divide to 7999999999? Or i which intervale is it?(intervale must be (x ; x+100)
  21. K

    Another algebra problem about prime and induction

    Homework Statement prove by induction that the n^{\text th} prime is less than 2^{2^{\text n}} Homework Equations hint:assume it is correct for all n \leq k, and then compare p_{k+1} with p_{1}p_{2}...p_{k}+1 The Attempt at a Solution is p_{k+1} smaller/greater than p_{1}p_{2}...p_{k}+1 so...
  22. K

    Abstract prime factorization proof

    Homework Statement A positive integer a is called a square if a=n^2 for some n in Z. Show that the integer a>1 is a square iff every exponent in its prime factorization is even. Homework Equations The Attempt at a Solution Well, I know a=p1^a1p2^a2...pn^a^n is the definition of...
  23. R

    Groups whose order is a power of a prime

    Homework Statement Does every group whose order is a power of a prime p contain an element of order p? Homework Equations The Attempt at a Solution I know it certainly can contain an element of order p. I also feel that |G|=|H|[G:H] might be useful. Any help is appreciated!
  24. T

    Groups of prime order are cyclic. (without Lagrange?)

    I know full well the proof using Lagrange's thm. But is there a direct way to do this without using the fact that the order of an element divides the order of the group? I was thinking there might be a way to set up an isomorphism directly between G and Z/pZ. Clearly all non-zero elements...
  25. C

    Problem with prime and composite numbers

    If p >= 5 is prime, prove that p^2 + 2 is composite. So i noticed if we divide any p >= 5 by 6 we only get remainders of 1 or 5. 6 | 5 , r = 5 6 | 7 , r = 1 6 | 11, r = 5 6 | 13, r = 1 6 | 17, r = 5 and so on so for my proof i am saying for p >= 5, p = 6k + 1 or 6k = 5 so for the first ...
  26. C

    Abstract algebra proof involving prime numbers

    The question states prove, If p is prime and p | a^n then p^n | a^n I am pretty sure I have i just may need someone to help clean it up. There are two relevant theorems i have for this. the first says p is prime if and if p has the property that if p | ab then p | a or p | b the...
  27. S

    Is (2^58+1)/5 a Prime or Composite Number?

    is (2^{58}+1)/5 a prime number or a composite number trust me this one has got an interesting solution
  28. 1

    Proving two number are relatively prime

    Homework Statement show that 5n +3 and 7n+4 are relatively prime for all n. Homework Equations The Attempt at a Solution tried to use induction but didnt work. Trying to find another way.
  29. P

    Prime Numbers: A Mathematical Mystery

    Is there any mathematical formula to predict / generate / or test the prime number??
  30. P

    Test Prime Numbers - Peter's Program

    Hi, I'm new to programming and have written the following code to test for prime-ness, but it doesn't seem to work except for n = 3. I think it may have something to do with my goto statement. Can anyone see a way of avoiding this or any other errors with the program? #include...
  31. M

    Is the Twin Prime Conjecture Finally Proven? A Scientist's Perspective

    Here is my proof of the 'Twin Prime Conjecture'.
  32. M

    Proof of the Twin Prime Conjecture

    I believe I have proved that there are an infinitude of twin primes using elementary algebra and a straightforward thought experiment. My proof will be sent shortly.
  33. N

    Prime Factorial Conjecture: Investigating p! Mod p2 for Prime Numbers

    Is there a name and/or proof for the following conjecture? "For any prime p, p! is congruent to p2-p modulo p2." Thanks much.
  34. B

    How to Prove the Sum of \(1^k + 2^k + ... + (p-1)^k \mod p\)?

    I'm trying to help a friend solve a problem but as I've never studied number theory, I'm having a bit of trouble myself figuring out how to do it. We need to find the sum of 1^{k}+2^{k}+...+(p-1)^{k} (mod p), where p is prime. By writing a program that created a table from test cases...
  35. I

    Making an existentially-quanified statement to define composite number and prime

    Sorry if I'm writing on wrong board. Homework Statement 1) Write an existentially quantified statement to express conditions for composite number ( composite number m is greater than 1 and there is a natural number greater than besides 1 and m, that divides m) 2) Writing definition using...
  36. C

    Prime division & repetition period

    Something odd i noticed while playing around with primes. We have the set of prime numbers P and a p ∈ P. Define a function f:Q → N that will give the period of the repetition in the decimal expansion of some number r ∈ Q. 1) ∀ p ∈ P: ∃ n ∈ N: ∀ q ∈ P, q < p: f(q/p) = n. So n is...
  37. T

    Which Prime Divisors of 4n^2+4n-1 Are Congruent Modulo 8 to \pm 1?

    I need to prove that p congruent modulo 8 to \pm 1 for every prime divisor p of 4n^2+4n-1. 4n^2+4n-1 is odd so we have p \equiv \pm 1,3,5 \pmod{8} I don't know how to continue from here... I need some hint. Thanks.
  38. J

    C Programming: Printing Prime Numbers from 1 to 20

    Homework Statement Hello, i want to calculate and print prime numbers from 1 to 20. I've provided my code below, and the program compiles but its just printing all numbers from 1 to 20, why? also have i used the continue statement correctly, since if it is found that a number is not prime then...
  39. A

    C/C++ C++ : Program that gives u the prime factors

    i need help making a program that only displays the prime factors ex: 100 = 2*2*5*5 i got the program to display all the factors but after that I am lost. here is the code so far oh its in C++ #include <iostream> using namespace std; int main() { cout << "Enter a number: "...
  40. K

    Groups of Prime Power Order: Must There Be an Element of Order p?

    Homework Statement Any help with this question would be great: G is a group such that |G| = pk, p is prime and k is a positive integer. Show that G must have an element of order p. The hint is to consider a non-trivial subgroup of minimal order. Homework Equations Lagrange...
  41. F

    Is Every Ideal Being Prime Indicative of a Commutative Ring Being a Field?

    Homework Statement Given a commutative ring with unity, show that if every ideal is prime than the ring is a field. Homework Equations The Attempt at a Solution I think that I can show that a ring is a field iff it has no nontrivial ideals. So I guess I need to show that if a...
  42. A

    Question about the prime number theorem

    Let p_n be the nth prime number. Can someone help me figure out how to show that \lim_{n\to \infty} \frac{\log (\log p_n)}{\log n} = 0. You're allowed to assume that \lim_{n\to \infty} \frac{p_n}{n \log p_n} = 1. I'm quite confident what I want to show is true, but it's hard...
  43. rcgldr

    Software language comparasons, prime number example

    This needed a separate thread. Here is an APL example where it's all done with no interation using N by N matrices in the intermediate propagation of data. Note, code flow in APL statements is right to left. The []IO<-0 sets the "index origin" to zero so a list of numbers and indexing...
  44. F

    Proving Prime Divisor of Composite Integer ≤ √n

    Homework Statement I need to prove that a composite integer n>1 has a prime divisor p with p<=sqrt(n). Homework Equations The Attempt at a Solution Im not sure how to do this, any help getting started would be great thanks.
  45. RyanJ

    Mathematica How to Create a Prime Number Image in Mathematica?

    Hey guys! Basically I have a table of prime numbers. What is to write this table as an image - from 1 too 480000 - showing each cell that is a prime as white and the others as black. So basically I'm cycling the numbers from 1-480000 and if they are prime then I want the cell white and...
  46. K

    Proving R is a Division Ring or Has Prime #Elements

    Homework Statement Problem 3.5.2 Let R be a ring such that the only right ideals of R are (0) and R. Prove that either R is a division ring or that R is ring with a prime number of elements in which ab = 0 for every a, b \in R. Homework Equations The Attempt at a Solution...
  47. G

    Riemann prime distribution for dummies?

    I saw a documentary recently that talked about the distribution of prime numbers and their similarity to vibrations in a sphere of quartz when struck by metal ball bearings. I tried to look up Riemann online and was overloaded with advanced math. Is there a resource where I can find out more...
  48. W

    Subgroups and prime order elements

    The question: Let n > 1 be a fixed integer and let G be a group. If the set H = {x in G : |x| = n} together with the identity forms a subgroup of G, what can be said about n? I know that n must be prime, but I can't figure out why that would be. The elements of h only have order 1 or n...
  49. K

    Gcd(a,b,c)lcm(a,b,c)=abc => a,b,c relatively prime in pairs

    Claim: If gcd(a,b,c)lcm(a,b,c) = abc, then gcd(a,b)=gcd(b,c)=gcd(a,c)=1. I'm trying to understand why this is true... How can we prove it? Any help is appreciated!
  50. G

    Interesting method for prime discovery?

    Hi, what I did to try to find prime numbers was this (in a computer program) Starting from 2, I set off a sine wave that has an amplitude=0 for every even number and an amplitude=1 for every odd number. What we are looking for, then, are the portions of the sine wave where the derivative...
Back
Top