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.

learn more… | top users | synonyms

1
vote
1answer
30 views

Let $p \in \lbrace2,3,4,…\rbrace$. Suppose that for all $x,y \in \mathbb{Z}$, if $p \mid xy$, then $p \mid x \vee p \mid y$. Show that $p$ is prime.

I'm studying for an upcoming exam and came across this question in my textbook. I'm assuming the easiest way to approach this proof is by contradiction. I don't have much so far, I just suppose that ...
0
votes
3answers
65 views

Help explain the end of this proof for infinitely many primes?

by contradiction, assume finitely many primes $p_1, p_2,\cdots, p_k$. let $N = p_1p_2\cdots p_k + 1$. Note $N > 1$. Now, by the fundamental theorem of arithmetic, there exists a number $p_j$, where ...
23
votes
2answers
1k views

Unusual pattern in the distribution of odd primes

I have recently noticed an unusual pattern in the distribution of odd primes. Each one of the following sets contains approximately half of all odd primes: $A_n=\{4k+1: 0\leq k\leq ...
1
vote
1answer
100 views

Generalizing Bertrand's Postulate

Is it possible that for any integer $y \ge 2$, there exists an integer $x$ such that if an integer $n \ge x$, then for all integers $z \le n^y$, there exists a prime $p$ such that $z \le p < z+n$ ...
1
vote
2answers
85 views

Properties of prime mod $3$

We know that if $p$ is a prime congruent to $3 \mod 4$, we cannot represent it as sum of two squares. Is there a positive property of such $p$? That is, do we have any statements that say "$p$ is a ...
1
vote
0answers
35 views

How quickly can we multiply hypercomplexes?

If we start with a hypercomplex number with $2^n$ entries, how quickly can we multiply it by another hypercomplex number, modulo a prime? EXAMPLE For example, with $n=1$, we get the complex numbers. ...
5
votes
7answers
101 views

Primality of number 1

Is number 1 prime as per the definition of prime numbers? Because as per the definition for being prime it should be divided only by 1 and number itself.
0
votes
0answers
38 views

Minimization problem involving a set of prime numbers and modular arithmetics

I'm a student working for curiosity on a general minimization problem where I suppose that there is no efficient algorithm for solving it. I'd like to ask for your valuable advice. Let $P$ be a set ...
3
votes
2answers
9k views

Most efficient algorithm for nth prime, deterministic and probabilistic?

What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically? Deterministic Iterate through only odd values, incrementing by $2$. Divide each ...
7
votes
1answer
158 views

Find the last digit of the exponent $x$.

Let \begin{align} p&=396543857870745963499374527519378569849832249490600276007703072957912\cdots\\ &\phantom{=}8049490077183813353745228056691 \end{align} This number is a 100-digit prime ...
3
votes
0answers
318 views

Prime factors of binomials

Is it true that for each $n\geq 2$ there are two primes $p, q$ such that (at least) one of them divides $\binom{n}{k}$ for each $1\leq k\leq n-1$? Examples: For $n=6: \binom{6}{1}=6; ...
1
vote
0answers
40 views

Numbers with special factorisation

We know that any natural number $n$ can be decomposed as $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$. I am looking for numbers which have $k_1=k_2=k_3=....=k_n=1$ i.e. given a number n, identify if it has all ...
5
votes
3answers
213 views

Are there infinitely many primes of the form $n!+1$?

For some numbers $n!+1$ is prime, but all such numbers are not prime. For example, $5!+1 = 11\times 11$. The question is this: Are there infinitely many primes of the form $n!+1$?
3
votes
3answers
167 views

What is the probability that a Poisson random variable is prime?

Let $X \sim Poisson(\lambda)$, and let $k \in \mathbb{N}$. Consider the quantity $Q(\lambda,k) = P\left( X+k \in Primes\right)$. Obviously $0 < Q(\lambda,k) < 1$. How does $Q(\lambda,k)$ ...
3
votes
1answer
48 views

Find an integer $x$ such that $2^x \equiv 3\pmod{p}$ given prime $p$

So I am studying for finals and I am not able to solve the problem: Let $p=3\times2^{11484018}−1$ be a prime with 3457035 digits. Find a positive integer $x$ so that $$2^x \equiv 3 \pmod p$$ Any ...
1
vote
1answer
42 views

Fermat's Little Theorem - Prim. Root - Find x

So I am studying for finals and I am not able to solve the problem: Let $p=3∗2^{11484018}−1$ be a prime with 3457035 digits. Find a positive integer $x$ so that $2^x \equiv 3 \mod p$ Any guidance ...
1
vote
2answers
136 views

How to find smallest integer which is greater than N positive primes

I know this can't be computed exactly, but I just need a rough estimate. I know one can compute a rough estimate of the number of primes less than N using the famous formula: ...
0
votes
1answer
40 views

Constellations in $\Bbb P^n$

In one of his papers Tao shows that set of Gaussian primes $\Bbb P[i]$ contains arbitrarily shaped constellations (where "shape" is any set of Gaussian integers and "constellation" of that shape is ...
2
votes
3answers
474 views

Proving that a number has at least 3 distinct prime factors.

Let abc be a 3-digit natural number (written in base 10). Prove that the 6-digit number abcabc has at least three distinct prime factors. I know that to prove that the 6-digit number has at ...
1
vote
1answer
72 views

Solving $x^n \equiv a \text{ (mod } p)$ in $\mathbb{Z}$

I want to show that for any integers $a$ and $n,$ ($n > 1$) there are infinitely many primes $p$ such that $$x^n \equiv a \text{ (mod } p).$$ When $n$ is odd, I used the fact that if $(a,p)=1$ ...
0
votes
2answers
93 views

Make a prime number from specified number, by concatenating some more digits on its right?

I am given a number, I don't know whether it's prime or not. The algo says, For eg - Step 1 - Convert char to ints. (Hello - 72101108108111) Ascii values Step 2 - Make a large number. Convert char ...
0
votes
1answer
36 views

Dickson's (and Bunyakovsky's) conjecture with compositeness constraints

Dickson's conjecture, in simple terms, says that for any choice of $a_1,b_1,a_2,b_2,...,a_k,b_k\in\Bbb N$ we have, for infinitely many $n\in\Bbb N$, that all of $a_1+nb_1,...,a_k+nb_k$ are prime, ...
2
votes
1answer
93 views

Well ordering principle and prime factoriation

Is it possible to prove the uniqueness of prime factorisation of natural numbers by the well ordering principle ? My attempt : Let S be the set of all natural numbers whose prime factorisation is ...
2
votes
1answer
127 views

Improvements of Dusart's lower bound for $ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}$.

Let $\gamma$ be the Euler-Mascheroni constant. In this paper (Theorem 6.12) it is proved that for $x\ge 2793$, $$ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}> 1-\frac{1}{5 \left(\log ...
2
votes
5answers
798 views

How to prove that there are infinitely many primes without using contradiction

How can I prove that there are infinitely many primes without using contradiction? I know the proof that is (not) by Euclid saying there are infinitely many primes. It assumes that there is a ...
5
votes
2answers
257 views

Prove that there are infinitely many primes of the form $8k + 3$

Prove that there are infinitely many primes of the form $8k + 3$ I have seen proofs for $4k+1$ and $8k+1$ and $4k+3$ but struggling with this one please help The suggestion given is to consider a ...
11
votes
2answers
187 views
0
votes
0answers
76 views

Can we use the distance to nearest prime to approximate large integers?

Let's say we have two oracles, NearestPrime and IndexOfPrime, defined as follows: Given some integer x, NearestPrime yields the prime number nearest to x that is not greater than x. ...
4
votes
2answers
149 views

Is the series $\sum_{1}^{\infty}\frac{1}{p_{j}}$ where $p_{j}$ is the $j$th prime convergent? [duplicate]

Does the series $\sum_{n=1 }^{\infty}1/p_{j} $ of reciprocal primes converge? Experimentally, it seems convergent.
6
votes
2answers
81 views

Prove or disprove that $p_n > e^{p_n - p_{n-1}}$ for large enough $n$.

Let $p_n$ denote the $n$-th prime. Prove or disprove that for large enough $n$ we have $$p_n > e^{p_n - p_{n-1}}.$$ The inequality trivially holds for all the twin primes larger than $7$. With ...
1
vote
1answer
198 views

How can I know if $2^{2^{2^{2^{2}}}}+1=?$ is prime?

I could calculate the following prime numbers $$2+1=3$$ $$2^{2}+1=5$$ $$2^{2^{2}}+1=17$$ $$2^{2^{2^{2}}}+1=65537$$ Are the following numbers prime??? $$2^{2^{2^{2^{2}}}}+1=?$$ ...
1
vote
2answers
205 views

In Zagier's one-sentence proof, why is S defined to be {(x,y,z)∈ℕ^3:x^2+4yz=p,p prime}?

I've looked at a very clear explanation of Zagier's proof (specifically, it can be found here:http://danielmath.wordpress.com/2012/12/26/one-sentence-proof/) but the first step still eludes me: why is ...
2
votes
1answer
47 views

Does it have convergent subsequence in that form? [duplicate]

Let $P_i$ be sequence of prime numbers i.e $P_1=2,P_2=3,P_3=5 ...$ Euler has proved that the sum $$\sum_{i=1}^{\infty}\dfrac{1}{P_i}$$ is divergent. Set $a_i=P_{P_i}$ then $a_1=P_2=3$ , ...
0
votes
1answer
52 views

Logical contradiction regarding cardinality of sets - help resolve

Consider the set of all natural numbers, $\mathbb{N}$. This set is composed of two subsets, the set of all primes, we'll call $\mathbb{P}$, and the set of all composite numbers (non-primes), ...
1
vote
3answers
93 views

Expressing a number that doesn't exist [closed]

How can one express something like $x \in \pi$ where $\pi$ is a set of prime numbers and $d$ is some divisor such that $\pi = \lbrace n:d|n\rbrace = \lbrace {1, p}\rbrace$? Or should I do something ...
0
votes
1answer
40 views

Number of prime divisors

Is there a way to express all the prime divisors of a natural number x as a function? Thanks in advance.
1
vote
4answers
88 views

I Don't Understand This Proof of Infinitely many Primes

The Proof What Confuses Me I follow the proof up until the point highlighted by the red square. I realize we must have $p_j|a$ (all composite numbers have a prime divisor) but why do we have the ...
4
votes
1answer
68 views

Given a set of powers of two, how “close” can we come to a prime?

Given a natural $n \ge 2$, we can construct a set of all powers of two from $2^n$ to $2^{4n}$: $$\{2^n, 2^{n+1}, 2^{n+2}, \dots, 2^{4n}\}$$ How close does one of these numbers come to a prime in the ...
1
vote
0answers
41 views

Size of increments in commutative ring to reach given number

I have the ring $\Bbb Z_q = \{0,1,\ldots,q-1\}$, where $q$ is a prime. Starting from $0$, I want to make exactly $n$ equally sized increments and reach $a\in \Bbb Z_q$, with $n<q-1$. For example if ...
0
votes
3answers
136 views

Isn't this the most compact binary representation of all numbers?

Here is the transformation: $$\begin{align*} &1\to(0)\\ &2\to(1)\\ &3\to(10)\\ &4\to((1))\\ &5\to(100)\\ &6\to(11)\\ &7\to(1000)\\ &8\to((10))\\ &9\to((1)0)\\ ...
0
votes
1answer
20 views

How to negate $(a=1 \text{ and } b=n) \text{ or } (a=n \text{ and } b=1)$ to get $1<a<n \text { and } 1<b<n$?

n>1 is composite if and only if it can be written as a product $n=ab$ of integers $a$ and $b$ such that $1<a<n$ and $1<b<n$. If a prime number $n$ is the product of two positive ...
7
votes
3answers
302 views

Prime numbers divide an element from a set

Show that if $p$ is a prime number different from 2 and 5, then it divides at least one of the elements of the set $\left \{ 1,11,111,1111,...\right \}$.
3
votes
2answers
135 views

Proving $(a+b)^{p} \equiv a^{p} + b^{p} \pmod{p}$ for prime $p$ [closed]

I am having trouble proving that any prime number $p$ and integers $a$ and $b$, $(a+b)^{p} \equiv a^{p} + b^{p} \pmod{p}$
2
votes
1answer
104 views

Integrating Chebyshev theta function

I'm trying to compute the following integral ($ \vartheta(x) = \sum\limits_{p \leq x}\log(p) $) $$\int\limits_{0}^{\infty}\vartheta(e^x) e^{-(1+s)x} \text{dx}$$ The result is supposed to be $ ...
0
votes
1answer
86 views

Why was 1 considered as prime years ago? [duplicate]

I've seen on Maths Is Fun that years ago, 1 was considered as prime, but now, it is not. How did this happen? I know that a prime number has only two factors, 1 and itself, and we have 1, which is ...
0
votes
1answer
66 views

show that if $2^n -1$ is prime than n is also prime

How to prove the above statement? Do you have to use Fermat's little theorem where $a^p = a (\mod p)$ I cannot see how to use the above here I tried to factorise $2^n -1 = (2-1)(2^{n-1} + 2^{n-2} + ...
1
vote
1answer
36 views

Amount of numbers that are coprime to a Mersenne number

Let $M_p = 2^p-1$ be a Mersenne number, where $p$ is prime. Is it known that almost every number in the interval $[1, M_p]$ is coprime to $M_p$? That is, is it known that $$ \lim_{p \to \infty} ...
0
votes
1answer
63 views

Counting number of elements of prime order.

Let $p$ be prime where $p$ does not divide the order of the group G. Consider these groups: $G\oplus Z_{p^4}; G\oplus Z_{p^3}\oplus Z_p; G\oplus Z_{p^2}\oplus Z_p\oplus Z_p; G\oplus Z_{p}\oplus ...
1
vote
0answers
38 views

prime case function?

Does there exist a name (or assigned to a mathemtician) for a case function $f(x)$ in literature, such that it twould take the value $1$ when $x$ primes, and zero otherwise? I am just looking for a ...
0
votes
1answer
31 views

How to answer the following question regarding a certain number of primes in a certain interval?

For an analytic number theory homework assignment, we are asked to prove the following (using the Prime number theorem $\pi(x) \sim x/\log(x)$ as $x \to \infty$ ): For every $\epsilon > 0 $ and ...