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

0
votes
3answers
538 views

Proof for the divisibility of natural numbers by at least one prime

Like any other natural number, N is divisible by at least one prime number (it is possible that N itself is prime). Is there a proof for this?
7
votes
3answers
208 views

If the set of primes where $p$, $p+2$ is infinite, would this imply that the set of $p$ and $p+2n$ is also infinite?

If the set of primes $p$ such that $p+2$ is also prime is infinite, would this imply that the set of primes such that $p+2n$ where $n$ is any positive integer for each pair is also infinite?
1
vote
1answer
206 views

Euclid's Proof of infinite prime numbers

I think this should probably be obvious, but I having trouble understanding part of the proof: If $N=p_1p_2\cdots p_n+1$, then why is it necessarily true that any given $p$ does not divide $N$?
4
votes
1answer
130 views

Understanding the gamma function in the context of Jitsuro Nagura's Proof

In 1952, Jitsuro Nagura published a classic proof that shows that for $n \ge 25$, there is always a prime between $n$ and $\frac{6n}{5}$. For those interested the paper itself can be found here. I'm ...
5
votes
1answer
580 views

Prime decomposition of an integer: methods of determining the prime factors $ p_1, p_2, …, p_r$ and powers $k_1,k_2, …, k_r$

Any integer n can be written in the form $ n = p_1^{k_1}p_2^{k_2} ... p_r^{k_r} $, where the powers $ k_1, k_2, ...,k_r $ are integers and $ p_1, p_2, ..., p_r$ are primes. Now I am interested in ...
5
votes
2answers
86 views

For which $p\in\mathbb{P}$ does $x^4+4=p$ have solution in $\mathbb{N}$?

Find all primes $p$ for which equation $$x^4+4=p$$ has solutions in set of natural numbers. I already have my own idea in mind, though the proof seems kinda weak to me at some points. But I'm ...
0
votes
2answers
181 views

How to prove there is no algorithm for a problem e.g. generating next prime?

Say I want to find the next prime directly without a test. AFAIK there is no known formula. Is it possible that since we've failed to find a formula, then we might be able to prove that there is no ...
4
votes
4answers
285 views

Constructing arbitrary sized Miller-Rabin Primality Test Case Numbers

The Miller–Rabin (or Rabin-Miller) primality test is an algorithm that determines whether a given number is prime. Is it possible to construct a number that will pass an arbitrary number of ...
9
votes
1answer
253 views

Is the number of alternating primes infinite?

I'm not sure if the recreational-mathematics tag is appropriate, but this problem came up during a practice Putnam seminar so maybe? The problem: Say that a positive integer is alternating if ...
0
votes
3answers
108 views

Proof that if $p\equiv3\,\left(\mbox{mod 4}\right)$ then $p$ can't be written as a sum of two squares

I'd appreciate your help showing that if $p\equiv3\,\left(\mbox{mod 4}\right)$ then p can't be written as a sum of two squares. Thanks!
2
votes
4answers
353 views

If $m^4 + 4^n$ is a prime, for $n,m\geq2$, then $m$ is odd and $n$ is even?

One thing which i got is $m^4 + 4^n$ is congruent to $1 \pmod 8$ when both $n,m$ are odd... Is it an iff condition?
4
votes
5answers
898 views

Determining the next Twin Prime?

A really simple I question I guess. Is there an algorithm or method such that given an integer $N$ there is a way to determine the next twin prime pair greater than $N$? If yes, then could you please ...
1
vote
3answers
201 views

What academic level would one need to be at to fully understand papers published on the twin prim conjecture?

Specifically, what academic level would one need to be at to fully understand Goldston-Pintz-Yildirim's work on twin primes? Undergraduate, Graduate, or PhD?
11
votes
2answers
824 views

How would proving or disproving the Twin Prime Conjecture affect proving or disproving the Riemann Hypothesis if at all?

How would proving or disproving the Twin Prime Conjecture affect proving or disproving the Riemann Hypothesis? What are the connections between both conjectures if any?
3
votes
0answers
193 views

Are There Infinitely Many Primes of a Certain Form?

Definition. Let $S_n = 3^n - 2^n$ for every positive integer $n$. Question. Are there infinitely many primes $p$ such that $S_p$ is (not) prime? Some Facts. (a) For any positive integer $n$ such ...
3
votes
3answers
3k views

Is the difference between consecutive prime numbers always an even number?

If we look at the difference between consecutive prime numbers, $p \gt 2$, it always appears to be an even number. For example, here are the seven consecutive primes starting at the $10^{10th}$ ...
6
votes
3answers
229 views

Good introductory readings to topics related to prime numbers for non-mathematicians

I'm a maths hobbyist who is fascinated by prime numbers. My quest to delve into the interesting parts of the topic is always hindered by my inability to understand the notation and concepts I ...
0
votes
1answer
163 views

Total number of ways to arrange the prime divisor of a number so it can be written using M digits

How many ways we can arrange all the prime divisor of a number so it can be written using M factors, where M <=T. T is the total number of prime divisor of the give number N. Example:N=27, its ...
1
vote
2answers
147 views

$N^2=2M^4-2p^2e^4$ has no integer solution

If $\gcd(M,e)=\gcd(N,e)=1$ and $p$ is prime and $p‎\equiv 5 \mod(16)$ then how I can show that $N^2=2M^4-2p^2e^4$ has no integer solution.
14
votes
1answer
325 views

Are all primes Euclid primes?

I was learning Euclid's theorem. If we repeat his construction (properly modified to give only primes) then will we skip any primes? Formally: $p_1 = 2$, and $p_{n + 1} = \text{smallest} \; q \in ...
2
votes
1answer
118 views

Reference for Brun-Titchmarsh inequality

Does anyone know a proof of the Brun-Titchmarsh inequality in the following form starting from the large sieve inequality? Brun-Titchmarsh inequality: Let $\pi(x;q,a) = |\{p \text{ prime}: p\equiv ...
21
votes
3answers
9k views

How many prime numbers are known?

Wikipedia says that the largest known prime number is $2^{43,112,609}-1$ and it has 12,978,189 digits. I keep running into this question/answer over and over, but I haven't been able to find how many ...
2
votes
1answer
56 views

Quick way to iterate multiples of a prime N that are not multiples of primes X, Y, Z, …?

Is there a way to quickly iterate multiples of some prime $N$ while avoiding multiples of blacklisted primes $X$, $Y$, $Z$, ...? By quickly I mean is there a faster way than: Increment current ...
2
votes
1answer
99 views

Solving $ f(\log x)$

A generalization of the conjecture $$\pi(x+x^{\theta}) - \pi(x) \sim \frac{x^\theta}{\log x} $$ (Ingham, 1937 or earlier) might be $$\Delta \pi_k = \pi_k((x+1)^2) - \pi_k(x^2)\sim \frac{x}{\log ...
23
votes
3answers
2k views

Two Representations of the Prime Counting Function

The bounty for the best work out of Greg's answer, especially the "solving for $\pi^*(x;q,a)$ in terms of all $\Pi^*$ functions (tedious but possible)" part is over. Since Raymond's ...
6
votes
1answer
155 views

Whether a Prime number can be written as sum of a Prime number and $2^n$?

Whether a Prime number greater than can be written as sum of a Prime number and $2^n$? $P_2 = P_1 + 2^N$ Some Examples of this $3=2+2^0$ $5=3+2^1$ $1021=509+2^9$
4
votes
1answer
219 views

Whether a prime number $ p $ can be written in the form $ 3A + 2B $, where $ A,B \in \mathbb{N} $.

I would like to know whether or not a prime number $ p $ can be written in the form $$ p = 3A + 2B, $$ where $ A $ and $ B $ are positive integers.
2
votes
0answers
333 views

Definition of a complex prime

If there would be such a thing as a complex prime number, how would it be defined? A normal prime is defined as a number only dividable by one or itself.. would that be "1+1i" with complex numbers? ...
9
votes
2answers
244 views

“Dirichlet's theorem” on pairs of consecutive primes

The number of primes in each of the $\phi(n)$ residue classes relatively prime to $n$ are known to occur with asymptotically equal frequency (following from the proof of the Prime Number Theorem). ...
12
votes
1answer
277 views

The number of prime years in a lifetime

$2013$ is not a prime: $3 \times 11 \times 61$. I was born in a prime year, and if I live as expected according to the statistics for U.S. males, I will just reach another prime year, $2027$. That ...
4
votes
2answers
184 views

Is there a prime number $> 10$ such that when it is divided by 3 or 5 or 7 always gives a remainder of 1?

Is there a prime number $p > 10$ such that when it is divided by 3 or 5 or 7 gives a remainder of 1, i.e.: $p \equiv 1 \pmod{3}, p \equiv 1 \pmod{5}, p \equiv 1 \pmod{7}$.
2
votes
1answer
255 views

Prime gaps distribution

It is well-known that gaps between successive primes have i.e. multimodal distribution (with peaks at $6 k$): I'm interested to know: what is the most suitable approximation for such weird ...
3
votes
1answer
668 views

Elementary proof that $3$ is a primitive root of a Fermat prime?

The following is exercise 6 of Chapter 4 in Ireland and Rosen's Number Theory. If $p=2^n+1$ is a Fermat prime, show that $3$ is a primitive root modulo $p$. I first recall that any Fermat prime ...
2
votes
1answer
96 views

Is there a sequence of primes whose decimal representations are initial segments of each other?

I.e., is there a sequence of primes whose decimal expansions have the following form: $$a_1,\ a_1a_2,\ a_1a_2a_3,\ a_1a_2a_3a_4, \dots$$ What about with the order of the digits reversed, so each ...
0
votes
1answer
244 views

Evaluating the sum of $\omega(n)$ in an arithmetic progression [closed]

Let $\omega(k)$ count how many distinct prime factors k has, Then I can prove that for any coprime integers $a,b$ $$\lim_{n\to\infty}\frac{\sum_{k=2}^n\omega(ak+b)}{\sum_{k=2}^n\omega(k)}=1$$ Does ...
2
votes
1answer
161 views

Remainders of primes

Maybe an idiot question but I can't find any info! We divide successive prime numbers by some fixed prime number $n$ (e.g. 7 or 17). We'll get some remainders $r[i]= 1..n-1$ Is there any law or ...
0
votes
0answers
79 views

Distribution of binary digits in moduli

Considering the (infinite) set of all positive integers that are a product of $2$ primes only, represented in binary $100...01$. Question: is the distribution of the proportion of $0,1$ digits ...
5
votes
2answers
278 views

Prime sum identity

Let $ \Lambda(k) $ denote the von Mangoldt function: $$ \Lambda(k) \stackrel{\text{def}}{=} \begin{cases} 0 & \text{if $ k $ is not a prime power}, \\ \ln(p) & \text{if $ k = p^{j} $}. ...
6
votes
1answer
894 views

Why the Riemann hypothesis doesn't imply Goldbach?

I'm interested in number theory, and everyone seems to be saying that "It's all about the Riemann hypothesis (RH)". I started to agree with this, but my question is: Why then doesn't RH imply the ...
5
votes
4answers
216 views

How can I prove this inequality involving the primes?

I want to determine whether $${{3({p_n}-p_{n-1})}\over{p_{n-1}}}\ge\prod_{i=3}^{n-1}\Bigg(1-{2\over{p_i}}\Bigg)$$ is true for all sufficiently large $n\gt3$. (I don't know whether or not it's ...
0
votes
1answer
173 views

Whether No. of Prime Numbers inside '$N$' can be found by using Prime numbers less than $\sqrt{N}$

By using Prime numbers less than $\sqrt{N}$, the number of primes less than $'N'$ can be found out. Is this true or false? I have verified it for upto from $10^1$ to $10^3$ for all the tens. So this ...
3
votes
2answers
117 views

Calculating that 13 is a Wilson Prime

I'm confused by the idea of a Wilson Prime. The theorem states that $$p^2=(p-1)!+1$$ This makes sense for $5$: $$5^2=(4\times3\times2)+1$$ so $5^2=25$ But it makes no sense to me for $13$: ...
2
votes
3answers
96 views

Whether twin primes satisfy this one?

It seems that difference of squares of any twin primes $+1$ will always lead to number which might be a) A square of a twin prime b) Itself a twin prime $C$ = ($A^2$-$B^2$ )+$1$ ------> $(1)$ Where ...
16
votes
2answers
430 views

Prove that for any nonnegative integer n the number $5^{5^{n+1}} + 5^{5 ^n} + 1$ is not prime

My math teacher gave us problems to work on proofs, but this problem has been driving me crazy. I tried to factor or find patterns in the numbers and all I can come up with is that for $n > 0$, the ...
3
votes
3answers
127 views

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 ...
6
votes
4answers
7k views

How to find number of prime numbers up to to N?

Is there any way or function to find out the number of primes numbers up to any number? (Say $10^7$ or $10^{30}$ or $200$ or $300$?)
4
votes
1answer
174 views

Functional Prime Sums

Let $ f: \mathbb{N} \to \mathbb{N} $ be a number-theoretic function satisfying $ f(xy) = f(x) + f(y) $ whenever $ \gcd(x,y) = 1 $. How can I prove that $$ \sum_{\substack{p ~ \text{prime}; \\ p \leq ...
4
votes
1answer
82 views

Asymptotics with prime of form 4k+3

I wonder if there is some asymptotics for such sum: $ \sum_{p=2}^{n} \frac{1}{p}$, where the sum is taken over all primes of form $ 4k+3 $? It's well-known that $ \sum_{p=2}^{n} \frac{1}{p}$, where ...
3
votes
2answers
2k views

How many all prime numbers p with length of bits of p = 1024 bits?

How many all prime numbers p with length of bits of p = 1024 bits? And is there any algorithm which generates all prime numbers p?
2
votes
1answer
455 views

Proof of Wilson's Theorem using Fermat's Little Theorem

Wilson's theorem states that a natural number $n>1$ is a prime number if and only if $$ (n-1)! \equiv -1 \pmod {n} $$ Can we prove it using Fermat's Little theorem? If yes, then how?