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.

learn more… | top users | synonyms

1
vote
2answers
246 views

Is there a way to show that $\sqrt{p_{n}} < n$?

Is there a way to show that $\sqrt{p_{n}} < n$? In this article, I show that $f_{2}(x)=\frac{x}{ln(x)} - \sqrt{x}$ is ascending, for $\forall x\geq e^{2}$. As a result, $\forall n \geq 3$ ...
2
votes
1answer
176 views

2 dimensional cellular automaton for prime twins?

Is there a 'simple' 2 dimensional cellular automaton to generate all prime twins ? With 'simple' I mean not too many states per cell and not so many rules. Thus a universal turing machine equivalent ...
-1
votes
1answer
146 views

cardinality of possible prime decompositions, countably infinite bijection

Let $A = \{ p_{i},p_{i+1},\ldots,p_{n}\}$ be any finite set of prime numbers, where $i,n \in \mathbb{N}$. And $p_{i}\in A$, is the $i$th prime number i.e. $p_{2} = 3$. Let all possible finite sets ...
5
votes
1answer
188 views

How to prove the equivalence between the two statements of ABC conjecture?

The ABC conjecture stated by wikipedia says the following statements are equivalent: I. For $\epsilon>0$, there are finite coprime triple $(a,b,c)$ satisfying $a+b=c$ such that ...
3
votes
3answers
116 views

Can I use PNT in this way?

I want to show that for large $n$ the $n$-th prime grows like $n\ln (n)$. Is this correct? By PNT $$\mathop {\lim }\limits_{x \to \infty } \frac{{\pi (x)\ln (x)}}{x} = 1.$$ Let $x = {p_n}$, so that ...
1
vote
0answers
135 views

Approximation of distribution of $\pi_k(n)$ using $\zeta(s)$

Let $\pi_k(n) $ be the number of numbers with k prime factors (repetitions included) less than or equal to n. If we take the sums: $z_1(s) = \sum_{n= 1}^\infty \frac{1}{(p_{1,n})^s},~ z_2(s) = \sum ...
2
votes
1answer
472 views

Factoring a number $p^a q^b$ knowing its totient

We are given: $n=p^aq^b$ and $\phi(n)$, where $p,q$ are prime numbers. I have to calculate the $a,b,p,q$, possibly using computer for some calculations, but the method is supposed to be symbolically ...
1
vote
2answers
225 views

What is the fastest algorithm to check if a number has only 3 divisors?

Which is the fastest way to check if a number has only 3 unique factors ? Any help will be highly appreciated?
1
vote
2answers
229 views

prime number theorem and prime counting function

$\pi(x)$ is the prime counting function (no. of prime within x) For the interval $(x, x + \delta x]$, $\delta > 0$, what is the smallest integer $x_{0}$ such that for any $x >= x_{0}$, $\pi(x + ...
6
votes
0answers
77 views

Statement about Woodal primes.

A Woodal number is an integer of the form $n 2^{n}-1$. A Woodal prime is an integer that is both a prime and a Woodal number. Let $p$ be a prime of the form 1 mod 4. Then $p 2^{p} -1$ is never a ( ...
2
votes
1answer
320 views

Implementing AKS Primality Prover

I am a computer programmer interested in prime numbers. I have implementations of several algorithms related to prime numbers at my blog. I want to add an implementation of the AKS primality prover to ...
1
vote
1answer
286 views

Prime numbers and their products

I've been reading a bit about prime numbers and their use in cryptography. If i would create a table of primes and their products, would there be any way to point out the area where a given number x ...
3
votes
1answer
786 views

Estimate for the product of primes less than n

In this paper Erdős shows a shorter proof for one of his old results stating that $$ s(n) = \prod_{p < n} p < 4^n$$ where the product is taken over all primes less than $n$. He also remarks that ...
2
votes
0answers
96 views

Searching for prime candidates

For some additional excitement, I've been searching for primes $p \gg q = 104729$, where $q$ is of course the ten-thousandth prime. It seems that the best way to search for prime candidates $p$ is to ...
2
votes
1answer
86 views

Factorization, Prime Numbers, and Limits to Our Grasp of Each

I have been fascinated with prime numbers ever since I was very young and actually setup a "Sieve of Eratosthenes" long before I ever knew that something like that existed. As I have gotten older and ...
1
vote
1answer
338 views

Perfect codes and the Golay codes

I've been working on exercises from various textbooks to get a better understading about perfect codes. There is a theorem that states: Theorem: The only nontrivial perfect multiple ...
0
votes
1answer
102 views

Primes of the form $a^k + b^k$

How many primes are there of the form $a^{k/2} + b^{k/2}$ exist for $a$ and $b$ (positive integer solutions). I am hoping there is only one. EDIT $k > 1$
3
votes
1answer
161 views

Summation mod$ (2^{16} +1)$

How can we calculate $\displaystyle\sum\limits_{k=1}^{2^{16}} \binom{2k}{k}(3\times 2^{14} +1)^k (k-1)^{2^{16}-1}$ mod $(2^{16} +1)$? I am aware that $2^{16} +1$ is a prime.
1
vote
2answers
319 views

Is there a largest “nested” prime number?

There are some prime numbers which I will call "nested primes" that have a curious property: if the $n$ digit prime number $p$ is written out in base 10 notation $p=d_1d_2...d_n$, then the nested ...
7
votes
2answers
217 views

Extensions of Bertrand's Postulate

Two questions came to mind when I was reading the proof for Bertrand's Postulate (there's always a prime between $n$ and $2n$): (1) Can we change the proof somehow to show that: $\forall x > ...
1
vote
3answers
178 views

Explain why 67 is prime based on the fact that order of 2 mod 67 is 66

Without using the fact that 67 is prime, show that the order of 2 mod 67 is 66. Explain why this result proves that 67 is prime What I understand: The order of 2 in $\mathbb{Z}_{67}$(or mod $67$) $ ...
2
votes
2answers
416 views

Show $[(p-1)!]^{p^{n-1}} \equiv -1 $ (mod $p^n$) for n $\in \mathbb N$

Show $[(p-1)!]^{p^{n-1}} \equiv -1 $ (mod $p^n$) for n $\in \mathbb N$, by induction. p a prime and p>2. I can't seem to prove the inductive step for this. Would appreciate help. My approach has ...
3
votes
4answers
190 views

Twin-prime averages

Sorry if this is trivial! Consider the set 3, 6, 9, 15, 21, 30, 36, 51, 54, 69, These are all such that $2x-1$ and $2x+1$ are both prime. Why are they all divisible by 3? And if say $yx-1$ and ...
35
votes
2answers
1k views

Small primes attract large primes

$$ \begin{align} 1100 & = 2\times2\times5\times5\times11 \\ 1101 & =3\times 367 \\ 1102 & =2\times19\times29 \\ 1103 & =1103 \\ 1104 & = 2\times2\times2\times2\times ...
2
votes
1answer
106 views

Sieve higher powers with logarithmic optimization

I am factoring number $N = 90283$ using quadratic sieve. Bound is $B = 44$. I find factor base to be $\{2, 3, 7, 17, 23, 29, 37, 41\}$. I have $50$ element sieving interval: $\{318, 921, 1526, ...
0
votes
2answers
144 views

Use Lucas' test with $a=7$ and prove $71$ is prime

My working so far: $71-1=70$ and Prime factors of $70$ are $2 \times 5 \times 7$ Check $a=7$: $7^{(\frac{70}{2})} \equiv 7^{35} \equiv x (mod 71)$ How do I find $x$? Usually I would use Fermat's ...
4
votes
5answers
177 views

$p$ a prime, $p \equiv 3 \pmod 4$. Prove that $\frac{p-1}{2}! \equiv \pm 1 \pmod p$

Let $p$ be a prime, $p \equiv 3 \pmod 4$. Prove that $\frac{p-1}{2}! \equiv \pm 1 \pmod p$. This is an exercise in one of my lecture notes. I couldn't seem to figure out how to do it. We've just ...
1
vote
1answer
103 views

Series of Mersenne primes

If the 'Lenstra - Pomerance - Wagstaff' conjecture is true, there are infinite Mersenne primes. In this case, if we consider the series: $$S_N=\sum_{k=1}^N \frac{1 }{M_k}$$ where $M_k$ is $k^{th}$ ...
15
votes
2answers
2k views

Every even integer can be expressed as the difference of two primes?

Every even integer can be expressed as the difference of two primes? If so, is there any elementary proof?
3
votes
1answer
256 views

Solvability of $x^q=2\mod p$

I've been discussing a problem recently Let $p, q$ be primes. If $x^q\equiv2\pmod p$ has no solution then $p\equiv1\pmod q.$ This is not a bi-equivalence (though it is "nearly" one): there are 811 ...
0
votes
2answers
134 views

How many multiples of two primes equal eachother

Given two distinct primes, $p_1,p_2$, is it true that there are no non-zero integers $k_1,k_2$,$|k_1| < p_2$, $|k_2|<p_1$ such as that: $$k_1p_1=k_2p_2$$ If so, how to prove it?
21
votes
2answers
938 views

Did H. Lebesgue claim “1 is prime” in 1899? Source?

John Derbyshire, in his text "Prime obsession: Bernhard Riemann and the greatest unsolved problem in mathematics" states that The last mathematician of any importance who did [consider the number ...
0
votes
0answers
69 views

sum over prime index done by a weird sieve?

As you might have noticed i considered in 2 previous questions sums of the form $f(p_i x)$ where the sum is over the primes $p_i$ ( between some integer bounds : $a \leqslant p_i \leqslant b$ ) , $x$ ...
1
vote
0answers
345 views

Modular multiplicative inverse and coprime numbers needed.

I have a 64 bit algorithm that uses modular multiplicative inverse and coprime numbers, and I need to convert it to 32 bit. This math is not my area, and I cannot find an online calculator, so I hope ...
1
vote
3answers
460 views

Finite or infinite set?

Due to my not-so-advanced math skills, this question may take a few attempts to state clearly: Consider the unordered pair (2-tuple) partitions of n (e.g. with n=4, we have {{4,0},{3,1},{2,2}}). ...
13
votes
1answer
757 views

What's the probability that a sum of dice is prime?

Prompted by today's Minute Math question on the MAA site (http://amc.maa.org/mathclub/5-0,problems/T-problems/T-web,ia/2005web/tb05-12-ia.shtml), I started thinking about the probability that the sum ...
2
votes
1answer
232 views

Can we give an upper bound for the sum over primes $p_{i}$ of $\sin(p_{i} x)$?

Let $x$ be a positive real number. Consider the sum $\sum \sin(p_i x)$ taken over all primes $p_i$ from 2 till $n$. Call this function $f(n,x)$. Can we give good upper and lower bounds of $f(n,x)$ ...
7
votes
1answer
601 views

how to prove this extended prime number theorem?

A Generalized Prime Number Theorem? Conjecture Let $n$ and $k$ be positive integers with $n - 50 > k^2 > 0$ and $n$ sufficiently large. Then for the odd primes we have, when $p$ is the biggest ...
3
votes
1answer
474 views

Chebyshev's first $\vartheta(x)$ function question

This was an exercise using the first Chebyshev function, $\vartheta(x)= \sum_{p \leq x} \log p.$ The question is simply how to prove (2) below, the rest is my two thoughts on how to proceed. [Edit: ...
10
votes
7answers
623 views

Can true randomness come out of mathematical rules?

For example, prime numbers, they seem very random, and they are defined by a simple set of rules. I can't see how real randomness could exist in the real world, but what about mathematics?
3
votes
2answers
184 views

Can all primes be written as a Mersenne prime?

Do all primes can be written in form of Mersenne prime? If not, why Mersenne form is important?
3
votes
2answers
1k views

Algorithm to generate a prime number which is n-digits long

Is there an algorithm which, given the number of digits n, generates a prime number which is n-digits long, in polynomial time complexity?
2
votes
0answers
190 views

How many co-primes are there for a big integer N over a specified interval?

How many co-primes are there for a big integer $N$ over a specified interval ? bounds of $N$ are $[1,10^9]$ and the interval is $[a,b]$ where ($1\leq a\leq b \leq 10 ^{15}$) and there are $100$ ...
0
votes
3answers
208 views

If prime $p \equiv 1\pmod 4$ and $b = ((p-1)/2)!$ then show that $b^2 \equiv -1\pmod p$. [duplicate]

This question is from Victor Shoup's book on number theory chapter 2. The problem statement is as mentioned in the title of the question. I haven't been able to crack this one till now. I focused on ...
2
votes
3answers
396 views

Finding the last digit of largest mersenne prime

I was wondering what the best way was to find the last digit of the largest known Mersenne prime $2^{6972593} - 1$? Is there any logical way to do this or will I have to just some how compute the ...
0
votes
2answers
212 views

Primes, congruent, Fermat squares

I need some proof or procedure to solve the question: For given n = 1 or > 1, We know by fermat, $p = x^2 + ny^2$ for an odd prime $p$. Now, can we proof the (a) $(-n/p) = 1$ and $(p/q) = 1$ for ...
9
votes
1answer
4k 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 ...
1
vote
1answer
212 views

Combining primes

A friend felt the need to explore wikipedia and stumbled across "prime notation". I've been working with primes for awhile (cryptography programmer) and have never seen a notation for "combining ...
6
votes
2answers
532 views

Is the number of primes congruent to 1 mod 6 equal to the number of primes congruent to 5 mod 6?

(I know that there's an infinity of primes congruent to 5 mod 6, but I don't know if there is an infinity of primes congruent to 1 mod 6.) But what I'd really like to know is whether or not the ...
2
votes
0answers
33 views

Solving $key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$ with High limits

I was solving this equation:- $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given $$ 1,000,000,000 < a, n, m \; < 5,000,000,000 $$ $$ a, m \; are \;coprime $$ I solved it bruteforcely but it ...