Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [prime-numbers]

Prime numbers are natural numbers greater than 1 not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

A prime number (or a prime) is an element of the greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number ... The fundamental theorem of arithmetic establishes the central role of primes in :

Any integer greater than 1 can be expressed as a product of primes that is unique up to ordering.

Here you get the first 50 millions of primes.

The concept of prime numbers is extended in ring theory, where an element $p$ of a ring $R$ is prime if and only if whenever $p\mid ab$, then $p\mid a$ or $p\mid b$.

One can easily see that this extends the definition of prime numbers in the natural numbers.

12562 questions
4
votes
1 answer

Number of numbers need to check before finding a prime

I am interested in (roughly estimating) how many random integers do I have to check before I find a prime of size say $100$ digits. I was thinking like so: Let the number of primes up to $X$ be denoted by $\pi(X)$. The famous Prime Number Theorem…
Vinyl_cape_jawa
  • 4,794
4
votes
0 answers

Beyond Riemann Hypothesis

Ole Warnaar and Wadim Zudilin write: The Riemann Hypothesis does not just “do better” than the Prime Number Theorem — it is generally believed to be as good as it gets”. That is, we, or far-superior extraterrestrial civilisations, will never be…
Sophia Antipolis
  • 390
4
votes
0 answers

Are there composite numbers that can stump this Pocklington variant?

Related question: Determine N primality knowing ALL factors of (n-1). But note that, unlike that question, I'm not searching for primes. I'm verifying a claim from a possibly mischievous source. I do care about the worst case. So, let's say someone…
KroneckerDelta
  • 111
  • 4
4
votes
3 answers

Finding the smallest prime that is larger than $10^{100}$ or $10^{10^{10}}$

Is there a known tractable way to find the smallest prime number that is larger than $10^{100}$? I'm asking because I want to use this as an example for a task that requires an incredible amount of computation power, and I don't want to embarrass…
Ofer
  • 63
4
votes
2 answers

Explanation of Zagiers Proof for primes of the form $4k+1$

What is the content of Zagiers proof? What is the actual proof and why does it work? I am not sure I understand why, there is only one fixed point, and why that implies that the involution $(x,y,z) \to (x,z,y)$ proves the theorem.
picakhu
  • 4,906
4
votes
1 answer

4 integers smallest sum.

$4$ different positive integers are placed on the vertices of a square. Each pair of numbers on opposite vertices are relatively prime, while each pair of numbers on consecutive vertices are not relatively prime. What is the least possible sum of…
Tom Galle
  • 596
4
votes
2 answers

Prime counting function formulas

Are there any elementary (including floor, ceiling, mod) representations of the prime counting function. Or one without an integral.
Nimish
  • 691
4
votes
4 answers

Does there exist prime number of the form $1010101010101....$ after the trivial one $101$?

I have checked numbers of the form $101010101...$ up to $1(01)_{2500}$ and the only prime I found is 101. I found that numbers of such form are quite rich in number of distinct prime factors. And $1(01)_{18}$ is the only semiprime I found So…
Krishna of the day
4
votes
2 answers

product of prime number sequence and its divisibility

Suppose I have a prime sequence which start with 3, 5, 7, 11.... and I multiply the first 16 prime numbers. Will the result of the multiplication be divisible by any composite number or a product of composite numbers ?
CodeWeed
  • 143
4
votes
1 answer

Can negative integers be prime?

Generally, the definition of prime numbers is all those natural numbers greater than 1, having only two divisiors, the number itself and 1. But, can the negative integers also be thought of in the same way? For example: if we take the case of -1.…
user160370
  • 415
4
votes
2 answers

Arithmetic progression and properties of prime numbers

If three prime numbers, all greater than 3, are in AP, then their common difference must be divisible by both 2 and three. I tried to prove it experimentally for first 10 prime numbers and it worked but was not satisfactory.Can it be proved…
AkashdeepKar
  • 45
4
votes
2 answers

Largest prime number $p$ that cannot be written as the sum of three odd composite numbers?

I consider the sequence of composite odd integers: 9, 15, 21, 25, 27, 33, 35, 41, ... I observe that there are certain large gaps between the composite odd integers and this may contribute towards the solution. So I start by considering some sums…
Haikal Yeo
  • 2,224
4
votes
1 answer

Deriving the Prime Number Theorem: Does this work?

I have my own derivation which seems fairly simple, and I wonder if it is correct; and if it is, whether it has been previously written up. It’s based on the Sieve of Eratosthenes, and it goes like this. You know that when checking for primes, you…
Marty Green
  • 1,917
4
votes
2 answers

How many numbers between $1$ and $6042$ (inclusive) are relatively prime to $3780$?

How many numbers between $1$ and $6042$ (inclusive) are relatively prime to $3780$? Hint: $53$ is a factor. Here the problem is not the solution of the question, because I would simply remove all the multiples of prime factors of $3780$. But I…
cingoz recai
  • 61
1 2 3
…
60 61