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

13
votes
2answers
1k views

Twin, cousin, sexy, … primes

Twin, cousin, and sexy primes are of the forms $(p,p+2)$, $(p,p+4)$, $(p,p+6)$ respectively, for $p$ a prime. The Wikipedia article on cousin primes says that, "It follows from the first ...
1
vote
3answers
146 views

this is a conjecture or a result? every arithmetic progression contains a sequence of $k$ “consecutive” primes for possibly all natural numbers $k$?

Writing a little better the previous question: is it true that if we let $a$ and $b$ be coprime integers, then the arithmetic progression : $a + bh: h\in {\mathbb Z}$, contains a sequence of $k$ ...
0
votes
0answers
32 views

Some questions about prime divisors and no. of primes

Let for an integer $n \ge 2$ , $\omega (n)$ denote the no. of distinct prime divisors of $n$ and $\pi (n) $ be number of primes not exceeding $n$. Let $a_1,...,a_k$ be integers greater than $1$ and ...
1
vote
2answers
50 views

Does $p_{1}^x + p_{2}^y = n$ have uniqe solution for $x$ and $y$ ($p_{1}, p_{2}$ are primes).

If I'm given a value $n$. And I know its of the form $p_{1}^x + p_{2}^y$, can I be sure that there is a unique solution for $x$ and $y$ and Can I determine values of $x$ and $y$, If I know the ...
0
votes
0answers
95 views

Is there a formula telling if number is prime? [on hold]

Like the topic.. . I mean.. let's say i'm wondering if 15 is prime or not. Could i calculate it, like function roots? EDITED: I mean something like columbus8myhw said: How about: Define ...
0
votes
2answers
98 views

Why $1$ isn't a prime? [duplicate]

I was wondering the reason behind defining the Prime Numbers in a manner of which $1$ isn't an example. I read in Rotman's A First Course in Abstract Algebra that one reason that $1$ is not called a ...
1
vote
0answers
24 views

Determining the starting value for primality test

This question is about Lucasian primality test for numbers of the form $N=3\cdot 2^n-1$ . There is a following statement in Wikipedia article : Lucas-Lehmer-Riesel test : "If $k = 3$ : if $n = 0$ ...
1
vote
2answers
115 views

Looking for a more efficient primality testing Algorithm than Miller-Rabin

I am looking for a practical probabilistic primality testing algorithm that is more superior than Miller-Rabin. By "more superior", I mean that the probability of giving the wrong answer is better ...
10
votes
6answers
602 views

What are some easy-to-remember prime numbers?

This is a question without much mathematical value, but since I don't immediately see an answer on Google I thought I'd ask anyway ... I'm looking for some largeish (> 10,000) easy-to-remember primes, ...
11
votes
1answer
345 views

A simple way to obtain $\prod_{p\in\mathbb{P}}\frac{1}{1-p^{-s}}=\sum_{n=1}^{\infty}\frac{1}{n^s}$

Let $ p_1 <p_2 <\ldots <p_k <\ldots $ the increasing list in set $\mathbb{P}$ of all prime numbers . By Infinite geometric series $\sum_{k=0}^\infty r^k = \frac{1}{1-r}$ for all $s>1$ ...
4
votes
1answer
38 views

equivalence between Chebyshev estimation and pi estimation in PNT

I searched, but though many posts are close, none of them are dublicates. Our version of PNT states that there is some $c$ s.t. $$\psi(x)=x+O(x\exp(-c\sqrt{\ln x}))$$ We have to prove equivalence ...
8
votes
0answers
36 views

Divisors of sequence $n,P(n),P(P(n)),\ldots$

Let $P(x)$ be a polynomial with nonnegative integer coefficients consisting of more than one nonzero term. Let $n$ be a positive integer. Is the set of prime numbers which divide at least one number ...
3
votes
4answers
175 views

Is there any known relationship between Goldbach's comet G(n) and the prime counting function (${\pi(n)}$)?

The "extended" Goldbach conjecture defines R(n) as the number of representations of an even number n as the sum of two primes, but the approach is not related directly with ${\pi(n)}$, is there any ...
1
vote
2answers
103 views

Distinct Mersenne numbers are coprime

How can you prove that if $p$ and $q$ are distinct primes, then the following holds?: $$(M_p,M_q)=1$$ Note: $M_n=2^n-1$, with $n$ prime number
0
votes
1answer
43 views

Proving $m$ is prime when $a^{m-1}\equiv 1\pmod m$ and factors of $m-1$ satisy $a^n\equiv r\pmod m,r\neq1$

If $a^{m-1}\equiv 1\pmod m$, and all factors of $m-1$, say $n (n< m-1)$ satisfy $$a^n\equiv r\pmod m,r\neq1$$ then $m$ is a prime. I want to prove this proposition, but it is a little difficult ...
1
vote
2answers
63 views

About the infinitude of some kind of primes? [on hold]

I will propose this proof: A Mersenne number always has the form $$2^{p}-1=4n+3$$ since for all $p≥2$ we have $$2^{p}-1≡-1(mod4)≡3(mod4)$$ The Dirichlet prime number theorem ...
4
votes
1answer
62 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) ...
3
votes
1answer
89 views

Extending the zeta function to semiprimes, etc.

The Riemann Zeta function is defined for $s > 1$ as \begin{align} &\prod _{n=1}^{\infty}\dfrac{1}{1 -\ p_{n}^{\ \ -s}}\\ \end{align} It is possible to extend the zeta function to semiprimes ...
1
vote
2answers
57 views

A Generalization of Carmichael Numbers

Obviously, from Fermat's Little Theorem, the condition of $p$ being prime is equivalent to there being some number $a$ of multiplicative order $p-1$ mod $p$. Moreover, this is equivalent to saying ...
7
votes
0answers
96 views

A little more on $\sqrt[3]{\cos\bigl(\tfrac{2\pi}7\bigr)}+\sqrt[3]{\cos\bigl(\tfrac{4\pi}7\bigr)}+\sqrt[3]{\cos\bigl(\tfrac{8\pi}7\bigr)}$

Using a special case of an identity by Ramanujan, we find that given the roots $x_i$ of $$x^3 + x^2 - (3 n^2 + n)x + n^3=0\tag1$$ which, since its discriminant is negative, always has three real ...
2
votes
3answers
53 views

Is there a number congruent to 1 modulo infinitely many primes?

Let $A=\left\{ p_{r},p_{r+1},\dots\right\}$ a (infinte) set of consecutive prime numbers (if you prefer, if $\mathfrak{P}$ is the set of all prime numbers, $A=\mathfrak{P}-\left\{ ...
1
vote
2answers
281 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 ...
5
votes
1answer
41 views

Choosing primes uniformly at random

I'm interested in efficient methods of generating prime numbers in a given range [a, b] (or with a given number of bits/digits, etc.). By "efficient" I mean minimizing time, randomness, and perhaps ...
54
votes
10answers
3k views

Is $1$ a prime number?

Is 1 classified as a prime number? And if so, why? If not, why not?
7
votes
0answers
108 views

What's so special about primes $x^2+27y^2 = 31,43, 109, 157,\dots$ for cubics?

While trying to find a closed-form solution for particular cubics as sums of cosines (related to this question), I came across this family with all roots real, $$F(x) = x^3+x^2-2mx+N = ...
3
votes
2answers
64 views

Do we still need probabilistic primality testing methods for practical applications?

Probabilistic primality testing methods like Rabin Miller and Solovay Strassen, were created at the time when mathematicians were not sure whether there is a deterministic polynomial algorithm. After ...
0
votes
2answers
38 views

let $G$ to be finite abelian group of order O(G), let n to be prime number and (O(G),n)=1 prove that $g=x^n$ for any $ x \in G$

let $G$ to be finite abelian group of order O(G), let n to be prime number and (O(G),n)=1 prove that $\forall g \in G$ we can write $g=x^n$ for any $ x \in G$
4
votes
3answers
2k views

Can Prime numbers be negative?

I was wondering, can a prime number be negative? We had a question over at security.se which stated that prime generation with openssl: openssl dhparam -text 1024 ...
0
votes
2answers
68 views

Prove that as $x\to\infty $, $\sum\limits_{p \leq x} \frac{1}{p \log \log p} \approx \log \log \log x$

Prove that as $x\to\infty$, $$\sum_{p \leq x} \frac{1}{p \log \log p} \approx \log \log \log x$$ Here sum is taken over primes.I tried to use the partial summation formula but could not ...
1
vote
3answers
673 views

How many elements are in the invertible set $\mathbb{Z}_n$?

My question is directly, how many elements are in the invertible set $Z_{35}$? It's my understanding that for any $Z_n$, if $n$ is prime, then the number of invertible elements is equal to $n-1$. In ...
13
votes
2answers
646 views

Evidence against Goldbach's Conjecture?

It recently occurred to me that, unless I'm much mistaken, Goldbach's conjecture can easily be seen to be equivalent to a seemingly more general statement: Every number $n$ divisible by any ...
1
vote
2answers
22 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
45 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 ...
20
votes
2answers
884 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 ...
0
votes
0answers
10 views

Is it ever possible for hypercomplexes to generate every element modulo a prime?

To start, we can take a well-chosen complex number, modulo a prime $p$, and generate every complex element modulo $p$. For example, if we take $(1+2i)^k \pmod 3$, each power of $k$ up to $(3 \cdot 3 ...
1
vote
1answer
74 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
62 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
23 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. ...
4
votes
7answers
84 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
25 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 ...
2
votes
2answers
4k 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 ...
6
votes
1answer
122 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
75 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
34 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 ...
4
votes
3answers
127 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
129 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
29 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
29 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 ...
-2
votes
3answers
103 views

Which number is odd one out in set $\{5, 7, 11, 29, 41\}$ [closed]

Which of the set element should not belong to set? $$\{5, 7, 11, 29, 41\}$$
1
vote
2answers
26 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: ...