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
0answers
36 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 ...
6
votes
1answer
125 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 ...
1
vote
1answer
83 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
1answer
32 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 ...
3
votes
1answer
35 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
2answers
63 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
2answers
28 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: ...
1
vote
1answer
45 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$ ...
3
votes
3answers
44 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 ...
0
votes
1answer
28 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 ...
4
votes
7answers
90 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
2answers
70 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 ...
8
votes
0answers
300 views

Two (strictly related) proofs by induction of inequalities.

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
2
votes
1answer
45 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 ...
3
votes
1answer
56 views

How find prime numbers $p_{i}$ such $p_{1}+p_{2},p_{2}+p_{3},p_{3}+p_{4},\cdots,p_{n}+p_{1}$ is square number

Question: Let $n\ge 5$ be an odd number, show that: there exist (or does not exist) primes $p_{i}\:;\:i=1,2,\cdots,n$ such that $$p_{1}+p_{2},p_{2}+p_{3},p_{3}+p_{4},\cdots,p_{n}+p_{1}$$ all ...
3
votes
3answers
131 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)$ ...
4
votes
1answer
116 views

Goldbach's conjecture can't be proved to be undecidable?

Conjectures concerning natural numbers which could be settled by a counterexample can, as far as I understand, not be proved to be undecidable without being proved not having a counterexample at the ...
10
votes
3answers
1k views

What is wrong with this proposed proof of the twin prime conjecture?

I was thinking on the twin prime conjecture, that there are an infinite number of twin primes... I came up with a proof. I have to think that it is incomplete or wrong, because many great minds ...
0
votes
1answer
16 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
0answers
32 views

Is there is any result claiming that there cannot be any other twin Mersenne primes?

There are 3 known Twin Mersenne Primes: $M3$ and $M5$, $M5$ and $M7$, $M17$ and $M19$. More precisely, if both $M(p)$ and $M(p+2)$ are both prime, then they are called Twin Mersenne Primes. My ...
2
votes
5answers
639 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 ...
10
votes
2answers
157 views

How can I prove analytically the number $2^{100000}+1$ is not prime??

How can I prove analytically the number $$(2^{100000}+1)$$ is not prime??
0
votes
0answers
64 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
1answer
66 views

Fairly good semiprime estimate

I have found a nice estimate for the semiprime counting function \begin{align} &f_{2}(x):=x \log \left( \log (x)/\log \left( a+a/ \exp\left( (\log (\log (x)-2)-1)^2/2\right) (\log (x)-2) \right) ...
5
votes
2answers
68 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 ...
4
votes
1answer
170 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=?$$ ...
2
votes
2answers
41 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
44 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
38 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
4answers
144 views

How can prime numbers be found mentally?

At a careers fair I was given a test to see how good I am at mental maths, And I was given multiple questions, asking whether a number was a prime. Example question: Which of these numbers isn't a ...
1
vote
3answers
60 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
26 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
71 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 ...
3
votes
1answer
60 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 ...
7
votes
0answers
91 views

Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
2
votes
0answers
34 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 ...
2
votes
1answer
83 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 ...
0
votes
3answers
83 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
18 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 ...
4
votes
2answers
111 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 ...
8
votes
3answers
274 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 \}$.
2
votes
2answers
122 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
29 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
75 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
47 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
25 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
30 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
33 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 ...
2
votes
3answers
53 views

Probability that a Mersenne number is prime

Let $p$ be a prime and let $M_p = 2^p-1$ be a (Mersenne) number. Is there any known result on the probability that $M_p$ is prime? In particular is it known whether the probability tends to $1$ as $p ...
15
votes
1answer
228 views

Nature of the series $\sum\limits_{n}(g_n/p_n)^\alpha$ with $(p_n)$ primes and $(g_n)$ prime gaps

Let $p_n$ denote the $n$th prime number and $g_n=p_{n+1}-p_n$ the $n$th prime number gap. This is to ask for which values of $\alpha$ the series $S_\alpha$ converges or diverges, where ...