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
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 ...
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 ...
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
48 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
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 ...
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 ...
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 ...
2
votes
3answers
52 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\{ ...
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 ...
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 ...
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 ...
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 = ...
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 ...
0
votes
2answers
67 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
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 ...
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 ...
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 ...
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
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. ...
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$
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
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 ...
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 ...
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 ...
6
votes
1answer
121 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
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
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 ...
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
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 ...
-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: ...
1
vote
1answer
40 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
33 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
27 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
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
2answers
67 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 ...
6
votes
0answers
191 views

Two (strictly related) proofs by induction of inequalities.

Predictably, I'm stuck with the inductive steps. Let $p_m$ be the largest prime factor of $a_n$ and set $\lim_{n\to \infty}\frac{\log a_n}{p_m}=1$. Suppose also this ratio converges to $1$ faster than ...
2
votes
1answer
41 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
51 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
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
0answers
64 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
13 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
30 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
627 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 ...
12
votes
2answers
150 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
59 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
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) ...