Prime numbers are natural numbers not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.
7
votes
3answers
399 views
How to find the solutions for the n-th root of unity in modular arithmetic?
$$\begin{align*}
x^n\equiv1&\pmod p\quad(1)\\
x^n\equiv-1&\pmod p\quad(2)\end{align*}$$
Where $n\in\mathbb{N}$,$\quad p\in\text{Primes}$ and $x\in \{0,1,2\dots,p-1\}$.
How we can find the ...
7
votes
1answer
136 views
Sum of reciprocals of primes
If $p_i$ is an infinite set of distinct primes such that $c=\sum\frac{1}{p_i} < \infty$, must $c$ be a transcendental number?
7
votes
3answers
420 views
What is the largest $n$ for which the $n$th prime is known?
$p = 2^{43,112,609} - 1$ is currently the largest known prime, but the $n$ for which this $p$ is the $n$th prime is, presumably, unknown. What is the largest $n$ for which the $n$th prime is known? ...
7
votes
3answers
180 views
Combinatorics question: Show divisibility
Let $a\geq2$, $b\geq2$ be two prime numbers and k be a natural number with $k\leq min(a,b)$.
How can one show that $z := \binom{a+b}{k} - \binom{a}{k} - \binom{b}{k}$ is divisible by the product ...
7
votes
2answers
170 views
Generalized PNT in limit as numbers get large
If $\pi_k(n)$ is the cardinality of numbers with k prime factors (repetitions included) less than or equal n, the generalized Prime Number Theorem (GPNT) is:
$$\pi_k(n)\sim \frac{n}{\ln n} \frac{(\ln ...
7
votes
2answers
458 views
Can insight be derived from direct formulae for prime number functions?
Dear StackExchange Community,
I am an amateur enthusiast and was attempting to construct a formula for the n th prime using elementary functions - I didn't achieve this* but I did come up with some ...
7
votes
1answer
393 views
Finding the 10001th Prime
I'm helping my son with Project Euler and we're working on problem 7, "What is the 10001st prime number?" We'll use a Sieve of Eratosthenes and we'll increase the size of the initial array until ...
7
votes
3answers
167 views
Generating random numbers with the distribution of the primes
I would like to generate random numbers whose distribution mimics that of the primes.
So the number of generated random numbers less than $n$ should grow like $n / \log n$,
most intervals ...
7
votes
4answers
231 views
Is there a “canonical” representation of integers using numbers other than primes?
Consider the (cumbersome) statement: "Every integer greater than 1 can be written as a unique product of integers belonging to a certain subset, $S$ of integers.
When $S$ is the set of primes, this ...
7
votes
2answers
548 views
Is it possible to prove that $3$ is a primitive root of any Fermat prime without quadratic reciprocity?
Browsing around online, I find a handful of proofs that $3$ is always a primitive root of any Fermat prime $2^n+1$. One particular proof is found in problems 4 and 5 here. Another proof I found on a ...
7
votes
2answers
483 views
Accuracy of approximation to inclusion-exclusion formula in prime sieve
This thing came up in a combinatorics course I am taking.
Choose a fixed set of primes $p_1,p_2,\dots,p_k$ and let $A_n$ be number of integers in $\{1,2,\dots,n\}$ which are not divisible by any of ...
7
votes
2answers
67 views
Need help on Furstenberg's proof on the infinitude of primes
I have a question on this proof given by Furstenberg proof on the infinitude primes. I am a non-mathematician with some basic knowledge on set theory and topology.
Define for $a,b\in\mathbb{Z}$ where ...
7
votes
1answer
46 views
Apparent patterns in ratios of consecutive primes
I was plotting the values of $\frac{P(n+1)}{P(n)+2}$, where $P(n)$ is the nth prime number. I noticed very easily that the values seem to belong very nicely to a set of "trajectories". They clearly ...
7
votes
1answer
470 views
Even numbers have more factors than odd numbers…
This was an exercise to show that, in a sense, the even numbers have more prime factors than the odds, but--if it's right-- I still have a question.
As an heuristic calculation, we could take a large ...
7
votes
1answer
227 views
interpolating the primorial $p_{n}\#$
The primorial $p_{n}\#$ is given by the product $p_n\# = \prod_{k=1}^n p_k$ (where $p_{k}$ is the $k$th prime) -- is there a natural (a la the gamma function $\Gamma(z)$) way of interpolating it for ...
7
votes
1answer
150 views
Asymptotics of sums of Dirichlet-Characters over prime numbers
Again in relation with some stuff I am currently reading, the authors make use of the following "standard argument in prime number theory":
Let $\chi$ be a non-principal Dirichlet-character. Then
...
7
votes
2answers
81 views
Relative sizes of prime gaps
There are no prime numbers between the two primes $113$ and $127$. That gap seems quite large by comparison to the sizes of the numbers in it.
$$
\frac{\text{size of gap}}{\text{prime just below the ...
7
votes
1answer
843 views
Pollard-Strassen Algorithm
I'm aware that the Pollard-Strassen algorithm can be used to find all prime factors of $n$ not exceeding $B$ in $O\big(n^{\epsilon} B^{1/2}\big)$ time. This is really useful because I need to find all ...
7
votes
1answer
59 views
Parameters giving maximal-length Collatz-like sequence
In a recent question the following recursive sequence was considered:
$$
a_{n+1} = \cases{\frac{a_n}{2} & $a_n$ is even \\ a_n +d & $a_n$ is odd}, \quad a_1 = d + 1
$$
where $d$ is an odd ...
7
votes
1answer
135 views
Prime spirals on surfaces of revolution
This is an entirely naive question, and in addition, vague. Apologies in advance!
Imagine wrapping the Ulam prime spiral around a surface in $\mathbb{R}^3$,
something like this:
This suggests ...
7
votes
1answer
128 views
Prime number generating function as product expansion
I am interested in prime number generating function.
$$f(x)=1+\sum \limits_{k=1}^\infty p_{k}x^k=1+2x+3x^2+5x^3+7x^4+11x^5+....$$
I would like to find the function as product expansion and to check ...
7
votes
2answers
123 views
A problem about a sequence and prime factorization
A long time ago I solved the following theorem
Let $p_1,p_2,\ldots,p_k$ be distinct primes. Let
$\{a_i\}^\infty_{i=1}$ be the increasing sequence of positive integers
whose prime factorization ...
7
votes
1answer
187 views
primegaps w.r.t. the m first primes / jacobsthal's function
Maybe I don't see the obvious here; but well.
I looked at an old discussion concerning prime gaps. I now tried to ask a somehow opposite way:
Assume the set $\small P(m)$ of first m primes $\small ...
7
votes
2answers
131 views
Find all values x, y and z which satisfy the equation $(x^2 + 1)(y^2 + 1) = z^2 + 1$ given that $(x^2 + 1)$ and $(y^2 + 1)$ are both primes.
Find all positive integers x, y, z which satisfy the equation $(x^2 + 1)(y^2 + 1) = z^2 + 1$ given that $(x^2 + 1)$ and $(y^2 + 1)$ are both primes.
It seems trivial that the only set of integers x, ...
7
votes
1answer
125 views
Convergence of alternating series based on prime numbers
I've been experimenting with some infinite series, and I've been looking at this one,
$$\sum_{k=1}^\infty (-1)^{k+1} {1\over p_k}$$
where $p_k$ is the k-th prime. I've summed up the first 35 terms ...
7
votes
1answer
125 views
Is every natural number a prefix of a prime number? [duplicate]
Possible Duplicate:
Proof that there are infinitely many prime numbers starting with a given digit string
Let n be the representation of a natural number in a non-unary base. Is it a prefix ...
7
votes
4answers
1k views
How can one efficiently generate n small relatively prime integers?
The definition of small is that they have O(lg n) bits. One way is just to test the integers 2,3,... for primality and keep the first n primes, but this takes at least O(n log n) time (times the cost ...
7
votes
0answers
314 views
Why does this identity equal the number of primes?
Can someone explain why this identity gives the number of primes? I don't understand it.
$D_{0,a}(n) = 1$
$D_{k,a}(n) = \displaystyle\sum_{j=1}^{k} \binom{k}{j}\sum_{m=a+1}^{\lfloor ...
7
votes
0answers
111 views
Numbers of the form $(p_{1}^{\alpha_{_{_1}}})^{2}+(p_{2}^{\alpha_{_{_2}}})^{2}+\cdots+(p_{n}^{\alpha_{_{_n}}})^{2}=(p_{m}^{\alpha_{_{_m}}})^{2}$
I'm looking for numbers of the form
$$(p_{1}^{\alpha_{_{_1}}})^{2}+(p_{2}^{\alpha_{_{_2}}})^{2}+\cdots+(p_{n}^{\alpha_{_{_n}}})^{2}=(p_{m}^{\alpha_{_{_m}}})^{2}$$
where $p_{i}$ are prime numbers, ...
7
votes
3answers
633 views
Proving a statement regarding a Diophantine equation
FINAL EDIT : Prove that if $p^z|n^2-1$
$$p^{x-z}(p^{z}-1)=\dfrac{ n^2-1}{p^z}-3$$ doesn't hold for any chosen values of $p,x,n$ and $z$.
Here $p>3$ is an odd prime , $x=2y+z, \ ...
7
votes
0answers
147 views
Weak version of Fortune's conjecture
Let $p\#=2\cdot3\cdot5\cdots p$ denote the primorial and $N(x)$ the smallest prime greater than or equal to $x$. Then Fortune's conjecture is that $N(p\#+2)-p\#$ is prime for all $p$. (Heuristic: to ...
7
votes
3answers
298 views
Which is the most restrictive closed-form expression that still generates all primes?
"The set $\{f(n)\}, n=1,2,\ldots$ includes all primes except a finite number of exceptions."
This statement is true for
$$f(n)=\sqrt{1+24n},$$
for which the exceptions are 2 and 3. It also generates ...
6
votes
5answers
1k views
Why do we consider prime numbers important, and what are their applications other than number theory in pure math?
Why do we consider prime numbers important, and what are their applications other than number theory in pure math? I know that Number theory is devoted to studying prime numbers, but there must be ...
6
votes
4answers
803 views
The least prime greater than 2000
I'm a bit curious as to how "real" mathematicians would solve this problem.
"Find the least prime number greater than 2000."
Of course, I can always go brute force:
...
6
votes
4answers
848 views
Alternate definition of prime number
I know the definition of prime number when dealing with integers, but I can't understand why the following definition also works:
A prime is a quantity $p$ such that whenever $p$ is a factor of ...
6
votes
5answers
477 views
Can this number theory MCQ be solved in 4 minutes?
The Problem: ( 270 + 370 ) is divisible by which number? [ 5, 13, 11 , 7 ]
Using Fermat's little theorem it took more than the double of the indicated time limit. But I would like to solve it quickly ...
6
votes
6answers
2k views
Is a prime factor of a number always less than its square root?
I was going through the fundamental theorem in Number Theory where any non zero integer n can be represented as a product of distinct primes. A related problem with this theorem is to prove that for ...
6
votes
2answers
479 views
Finding the 2,147,483,647th prime number
In computer science an array is indexed by an integer (int). Unlike in mathematics, the computer science integer (int) has a ...
6
votes
3answers
330 views
Characterizations of primes
Let $\mathbb{P}$ be the primes set.
We know from Wilson's Theorem that
$$(p-1)!\equiv-1 \pmod p \iff p \in \mathbb{P}$$
What another formulas we have with an if and only if ($\iff$) statement to ...
6
votes
2answers
652 views
prime numbers in Pascal's triangle
Just wondering about this:
Is it true that there are no prime numbers in Pascal's triangle, with the exception of $\binom{n}{1}$ and $\binom{n}{n-1}$?
From the first 18 lines it appears that this is ...
6
votes
2answers
387 views
It it possible to “compress” a list of large numbers using their prime factors?
On a computer I can have integers on arbitrary size thanks to GMP, so it's represented in base 2 in memory.
I'm wondering if it's possible in theory to use less memory if I store only prime factors ...
6
votes
2answers
338 views
Highly composite number
Definition: n is said to be a highly composite number if and only if $d(n)>d(m)$ for all $m<n$, where $d(n)$ denotes number of divisors of n.
Questions:
1) Are there any theorems about highest ...
6
votes
3answers
663 views
For any $n$, is there a prime factor of $2^n-1$ which is not a factor of $2^m-1$ for $m < n$?
Is it guaranteed that there will be some $p$ such that $p\mid2^n-1$ but $p\nmid 2^m-1$ for any $m<n$?
In other words, does each $2^x-1$ introduce a new prime factor?
6
votes
3answers
317 views
Proof that for all distinct primes $p, q$, there exists $n$ so that $p+n$ is prime, but $q+n$ isn't
Imagine two distinct prime numbers $p$ and $q$. Intuitively, I'd say that there is always a natural number n so that $p+n$ is a prime number, but $q+n$ isn't.
I was given two hints:
for each ...
6
votes
2answers
167 views
Showing the equivalence of two forms of the Goldbach Conjecture
My number theory textbook has the following (paraphrased) exercise:
Goldbach wrote a letter to Euler with the following conjecture:
Every integer greater than five can be written as the sum of three ...
6
votes
1answer
356 views
Rationals of the form $\frac{p}{q}$ where $p,q$ are primes in $[a,b]$
Consider the closed interval $[0,1]$, there is $\frac{2}{3} \in [0,1]$ where $p=2$ and $q=3$. Similarly consider $[2,3]$, one can have $\frac{5}{2} \in [2,3]$ where $p=5$ and $q=2$. Does every ...
6
votes
2answers
600 views
Sum of reciprocal prime numbers
How can the following equation be proven?
$$ \forall n > 2 : \sum_{p \le n}{\frac1{p}} = C + \ln\ln n + O\left(\frac1{\ln n}\right), $$ where $p$ is a prime number.
It's not homework; I just ...
6
votes
3answers
150 views
Showing $\pi(ax)/\pi(bx) \sim a/b$ as $x \to \infty$
I'm having a bit of a problem with exercise 4.12 in Apostol's "Introduction to Analytic Number Theory". I don't think it's supposed to be a very hard exercise, it's the first one in its section ...
6
votes
3answers
143 views
Number of $k^p \bmod q$ classes when $q\%p > 1$
I want to show that when $p, q$ are primes, $k^p\bmod q$ takes on $q-1$ distinct values (as $k$ ranges over positive integers) if and only if $q \not\equiv 1 \pmod p$. (It is easy to verify this ...
6
votes
2answers
261 views
A Question on RH relating to Prime Number theorem
Well, in a previous post regarding the explanation of Riemann Hypothesis Matt answered that:
The prime number theorem states that the number of primes less than or equal to $x$ is approximately ...
