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

33
votes
2answers
826 views

Proof that $123456789098765432111$ is prime?

The mathematician Charles Weibel asks on his home page the following "fun question": How can you prove that 123456789098765432111 is a prime number? (He notes the fact $$12345678987654321 = ...
6
votes
5answers
1k views

Last digits of primes

A prime number not equal to $2$ and $5$ can't have last digit equal to $2,4,5,6$ and $8$. Is it true that this is the only restriction on last digits of prime numbers? I mean if its true that for any ...
1
vote
1answer
62 views

Characterizing the primes which don't divide any Pell-Lucas number(s)

For integer $n$, let $P_n$ be a Pell number, and $Q_n$ its companion. Is there a characterization of the prime numbers $p$ which don't divide any $Q_n$? By brute-force search, I found that this ...
1
vote
0answers
31 views

RSA aloghorithm - stuck on d

I'm sorry in advance if this sort of question has been posted before. I couldn't find it. I'm clearly an idiot, and I clearly need help, so here I am. I have a homework assignment which overall is ...
0
votes
0answers
14 views

Semiprime error margin

As an extension to this question, the plot below shows $$\pi(x)-R(x)\ \ \text{ (blue)},$$ $$\pi_{(2)}(x)-smoothed\left[ ...
2
votes
0answers
25 views

Semiprime asymptotic step function

Since $$\pi_{(2)}(x)=\sum_{i=1}^{\pi(x^{1/2})}\left(\pi\left(\dfrac{x}{\text{p}_i}\right)-i+1\right),$$ where $\pi_{(2)}(x)$ denotes the semiprimes and $\text{P}_i$ is the $i$th prime, an asymptotic ...
3
votes
1answer
70 views

Probability that two random integers have only one prime factor in common

The probability that two integers picked at random are relatively prime is known to be $1/\zeta{(2)}=6/\pi^2\approx0.607927...$. Generalizing, the probability that $n$ random integers have $\gcd=1$ is ...
1
vote
2answers
58 views

prime powers modulo prime

I stumbled upon the following property: $n\equiv n^5\bmod 5$ for all $n\in\mathbb{Z}$, so out of I tried other (prime) numbers $n\equiv n^p\bmod p$. My question is whether this is true for all primes ...
9
votes
1answer
133 views

Prime Mean of Primes

1) Are there infinitely many primes $p_1,p_2$ such that $\frac{p_1+p_2}{2}$ is also prime? 2) What can we say about the more general problem : Are there infinitely many primes $p_1,p_2,\cdots, ...
0
votes
0answers
93 views

Arithmetic progression and average of two prime numbers

Let $A=(a_n : n \in \mathbb{N})$ be the sequence given by: $$ \ a_n = a_1 + (n - 1)d,\quad a_1,\ d,\ n \in \mathbb N,\quad d\gt a_1,\quad \gcd(a_1,\ d)=1. $$ For all terms of $A$ greater than $\ ...
7
votes
5answers
668 views

Induction hypothesis misunderstanding and the fundamental theorem of arithmetic.

The fundamental theorem of arithmetic is made of two parts: The existence part: There exist primes such that for any natural number $j$, we can write $j$ as a product of prime numbers. The ...
5
votes
0answers
73 views

Is this a recurrence for the characteristic sequence of composite numbers?

The characteristic sequence of composite numbers is equal to 1 if $n$ is not a prime number and equal to 0 if $n$ is a prime number, starting: $$1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1,...$$ where the ...
2
votes
0answers
51 views

totally split primes in a number field

I have to show: For any number field $K$, there are infinitely many prime numbers $p \in \mathbb{N}$, that are totally split in $K$. I think have already shown (with some hints my professor gave) ...
1
vote
2answers
269 views

Divisibility in a recurrent sequence

Let $a_1=0$, $a_2=\alpha$, and $a_n=\lambda a_{n-1}+\mu a_{n-2}$ for $n\geq 3$. Are there positive integers $\alpha$, $\lambda$, $\mu$ such that $$a_{p^2} \equiv 0 \mod p $$ for every prime ...
12
votes
5answers
301 views

How many prime numbers are there in between $1000!+1$ and $1000!+1000$, inclusive?

I know $1000!$ is not a prime number as any number $1000$ or less is a divisor, but how would I know if $1000!+1$ is prime? Any hints? Also, use the above question to prove that you can find $n$ ...
2
votes
2answers
257 views

Application of prime number theorem

In the following I am referring to a small argument made in "A counterexample to Borsuk's conjecture" by Jeff Kahn, Gil Kalai (see http://arxiv.org/abs/math.MG/9307229) In this paper the authors bound ...
6
votes
1answer
112 views

Prime Number Theorem and sum of reciprocals of primes

This is not a homework problem. I am a mathematician (group representations and classical analysis) who never studied number theory and am beginning with Niven’s book. My question concerns the ...
7
votes
3answers
156 views

Finding a prime number between $n$ and $2n$

I am trying to find a prime number between $n$ and $2n$. I know that the number of primes between $n$ and $2n$ is $n/(2\ln n)$. I was thinking of choosing a random number between $n$ and $2n$ and ...
3
votes
3answers
126 views

Number of primes less then $6000$ using $n/ \log n$

So I am trying to use this formula here and is giving me some trouble. If I just substitute $6000$ into the formula, the answer is approximately $1500$. But the number of primes under $6000$ is ...
0
votes
2answers
211 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
5
votes
0answers
371 views

The prime number theorem and the nth prime

This is a much clearer restatement of an earlier question. In section 1.8 of Hardy & Wright, An Introduction to the Theory of Numbers, it is proved that the function inverse to $ x ⁄ \log⁡ x$ is ...
0
votes
1answer
40 views

An Inequality Involving Prime Numbers

Let $p_i$ be the $i^{th}$ prime number. It seems as though the following inequality is true for all positive integers $m$ and real numbers $x>1$: ...
71
votes
14answers
7k views

Infiniteness of non-twin primes.

Well, we all know the twin prime conjecture. There are infinitely many primes $p$, such that $p+2$ is also prime. Well, I actually got asked in a discrete mathematics course, to prove that there are ...
10
votes
4answers
839 views

If $n = 51! +1$, Then find no of primes among $n+1,n+2,\ldots, n+50$

If $n = 51! +1$, Then find no of primes among $n+1,n+2,\ldots, n+50$ Really speaking, I don't have any clue ...
0
votes
2answers
48 views

Question regardles primes and the fundamental theorem of arithmetic

I have been reading through my book of practice proofs and came across this particular question which has stumped me. $p$ and $q$ are primes. Prove $\forall p \in \mathbb{Z}, \forall k \in ...
3
votes
0answers
61 views

Resources about infinite primes of form $n^2 + 1$

Where can one find existing work on the following problem? Prove there are infinitely many primes of the form $n^2 + 1$. Resources about related work would also be appreciated.
36
votes
1answer
1k views

Generalizing Ramanujan's proof of Bertrand's Postulate: Can Ramanujan's approach be used to show a prime between $4x$ and $5x$ for $x \ge 3$

Perhaps, I've been thinking too long about Ramanujan's proof, but it appears to me that his argument can be generalized beyond $x$ and $2x$. My argument below attempts to show that for $x \ge 1331$, ...
49
votes
12answers
10k views

Why is Euclid's proof on the infinitude of primes considered a proof?

I've expressed Euclid's proof on the infinitude of primes on Mathematica: ...
0
votes
2answers
758 views

Checking the Harald Helfgott proof of the little Goldbach conjecture without a public release of numerical checks?

A few month ago, a proof of the little/ternary Goldbach conjecture has been claimed by Harald Helfgott with three articles: Major arcs for Goldbach's theorem Minor arcs for Goldbach's theorem ...
12
votes
2answers
655 views

Ulam spiral: Is there an “unusual amount of clumping” in prime-rich quadratic polynomials?

I was reading Martin Gardner's Mathematical Games column on the Ulam spiral which appeared in the March 1964 issue of Scientific American. (The spiral actually featured on the cover of that issue.) ...
2
votes
0answers
81 views

Questions about central polygonal numbers $1, 2, 4, 7, 11, 16, 22, 29, 37, 46,\cdots$

Formula for Central polygonal numbers is $\frac{n(n+1)}{2} + 1$, if $n=1$ or $n$ is prime, we get the new sequence $A$: 2, 4, 7, 16, 29, 67, 92, 154, 191, ... It seems that all primes either is ...
2
votes
0answers
58 views

Birthday problem & primes

Let $\pi_k(n)$ be the almost prime counting function, then $\pi_k(2^kn)$ reaches a max value, since $\pi_k(2^kn)=\pi_{k+1}(2^{k+1}n)$ for large enough $k$. (eg, ...
2
votes
1answer
69 views

$\text{lcm}(1,2,3,\ldots,n)\geq 2^n$ for $n\geq 7$

I can prove that $\text{lcm}(1,2,3,\ldots,n)\geq 2^{n-1}$. Newly, i read in a paper that for $n\geq 7$ we have: $$\text{lcm}(1,2,3,\ldots,n)\geq 2^n$$ Can you prove it? (this inequality is an ...
21
votes
4answers
9k views

Is there a known mathematical equation to find the nth prime?

I've solved for it making a computer program, but was wondering there was a mathematical equation that you could use to solve for the nth prime?
9
votes
3answers
543 views

Equivalence to the prime number theorem

I was just reading this question and answer: How will this equation imply PNT and it raised a whole new question: Given that $\sum_{n\le x} \Lambda(n)=x+o(x)$, prove that $$\sum_{n\le x} ...
3
votes
1answer
44 views

Can a Mersenne number be a power (with exponent > 1) of a prime?

Let $n \geq 1$ and consider the (Mersenne) number $M_n = 2^n-1$. Is it possible that $M_n = p^k$ for some prime $p$ and some (necessarily odd) $k > 1$? Thanks in advance.
0
votes
1answer
55 views

AP term multiple of prime number

I am having this equation : (a+(n-1)d)%p=0 Here a and d can go upto 10^18 and p is prime number upto 10^9 . How to find the least value of n here? Example : If ...
3
votes
0answers
34 views

Prime Triangle:: How to find the position(row and column) of prime number in a triangular arrangement

I was working on problem which asks the position of a prime number in a triangular arrangement. If we arrange the all prime up to 10^8 as shown in image we can find the row and column number of a ...
3
votes
1answer
60 views

Improving Bertrand's postulate

Recall that Bertrand's postulate states that for $n \ge 2$ there always exists a prime between $n$ and $2n$. Bertrand's postulate was proved by Chebyshev. Recall also that the harmonic series $$ 1 + ...
3
votes
4answers
112 views

Expressing $\Bbb N$ as an infinite union of disjoint infinite subsets.

The title says it. I thought of the following: we want $$\Bbb N = \dot {\bigcup_{n \geq 1} }A_n$$ We pick multiples of primes. I'll add $1$ in the first subset. For each set, we take multiples of some ...
1
vote
1answer
21 views

How to combine three integers from three sequences such that all the numbers in the triplet be coprime.

So there are three sequences of integers denoted $s_1, s_2$ and $s_3$. Each of them starts at $2$ and goes up to an integer $N$. In other words, they're all identical sequences of numbers of the form ...
2
votes
1answer
236 views

is it possible to get the Riemann zeros

since we know that the number of Riemann zeros on the interval $ (0,E) $ is given by $ N(E) = \frac{1}{\pi}\operatorname{Arg}\xi(1/2+iE) $ is then possible to get the inverse function $ N(E)^{-1}$ ...
1
vote
0answers
45 views

Wolstenholme Number

Does Wolstenholme Numbers have perfect squares other than 1 and 49? The first few are 1, 5, 49, 205, 5269, 5369, 266681, 1077749 seems to be a complicated problem
2
votes
1answer
30 views

Extrema of the Ratio of Consecutive Primes

Let $p_i$ denote the $i$th prime number. We know that $\frac{p_{n+1}}{p_n}\rightarrow 1$ as $n\rightarrow\infty$. Therefore, if we pick some real number $c>1$, there should be some positive integer ...
3
votes
1answer
33 views

Physical reflections of prime-number distribution

Not a purely mathematical question: I have read somewhere that Atomic Orbital is closely related to the distribution of prime numbers, but I am unable to find any reference to that. Can someone ...
1
vote
1answer
44 views

Proof for Carmichael theorem

if $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots p_r^{a_r}$ and $\lambda(n) = lcm[(p_1-1)(p_1^{a_1-1}),(p_2-1)(p_2^{a_2-1}),(p_3-1)(p_3^{a_3-1}),\dots,(p_r-1)(p_r^{a_r-1})]$ then $k^{\lambda{n}} \equiv ...
0
votes
1answer
56 views

The binomial coefficients $\binom{n}{ p}$ are divisible by a prime $p$ only if $n$ is a power of $p.$

I'm looking for a "high school / undergraduate" demonstration for the: All the binomial coefficients $\binom{n}{i}=\frac{n!}{i!\cdot (n-i)!}$ for all i, $0\lt i \lt n$, are divisible by a prime $p$ ...
1
vote
1answer
42 views

How many $\overline{a}\in\left(\mathbb{Z}/91\mathbb{Z}\right)^\times$ pass the Fermat and Miller-Rabin primability tests?

Let $$\text{F}_{91}:=\left\{\overline{a}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times:91\text { passes the Fermat primality test to base }a\right\}$$ and ...
3
votes
4answers
228 views

A congruence involving prime numbers

This congruence appears in a textbook I'm reading anf it left the proof to the reader, however I cannot find my way around it. $$(a+b)^ p \equiv a^p+b^p \pmod p\text{ when $p$ prime and ...
1
vote
2answers
84 views

How can I solve this problem without having to do it by hand?

I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement without forcing me to do it ...