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
50 views

Is there a way of showing there are arbitrarily big gaps between primes by contradiction?

This may be a stupid question. So apologies in advance, if it is, One proof of this is a straightforward construction. For any $N$, consider $(N+1)!+2$, $(N+1)!+3$,..., $(N+1)!+N$. All of these ...
1
vote
0answers
93 views

Sieve for Prime Numbers

I will use some simple arguments on a prime numbers formula that has been deterministically checked by computer. I would like to compare this result with others you already know. The set of all ...
1
vote
0answers
76 views

Is there a proof that Encrypting and then Decrypting any data using AES 256 will result in the same data?

I use AES quite often at work (I'm a software programmer) and I trust that it "works" without understanding the maths behind it. It's a black box to me. Does a mathematical proof exist that AES 256 ...
1
vote
0answers
74 views

Estimating total number of twin primes

Taking my notation from a previous question Define a function $P_6$ as $$P_6(n)=\begin{cases} 0, \ \ 6n-1 \not\in \mathbb P \wedge 6n+1 \not\in \mathbb P \\ 1, \ \ (6n-1 \not\in \mathbb P \wedge ...
1
vote
0answers
64 views

Functions generating prime numbers in math packages

Does anyone have an idea on how prime number generating functions such as Prime[n] in Mathematica generate the $n^{th}$ prime number?
1
vote
0answers
89 views

When is a number like “ddd…ddd”+1 (where d is a digit) a perfect square or a prime?

Inspired by Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?, I wonder when numbers like these are perfect squares. Certainly, all numbers of the form $000...0001$ are ...
1
vote
0answers
143 views

Proving there exists prime numbers between the squares of prime numbers

Conjecture: $\forall $ $p_{n}$, $p_{n+1} \in \mathbb{P}$, $\:$ $p^2_{n+1} = p^2_{n} +\omega_{n} p_{n} + \phi_{n} : \phi_{n} , \omega_{n} \in \mathbb{N} $ and $ \phi_{n} < p_{n}$, $\:$ ...
1
vote
0answers
42 views

straightforward hcf question

This shouldnt be difficult but I can't get it out..: Let c,d,N be integers with hcf(c,d,N) = 1. Show that there exist m, n ∈ Z with hcf(c+mN,d+nN) = 1 Any help appreciated!
1
vote
0answers
42 views

check for primality of a number

Is 2^131 - 1 a prime number? if so how can i proof it, or if no how? In the general is there a way for primality check for a ...
1
vote
0answers
175 views

All the small primes close together yet again

$$ \begin{align} 2254 & = 2\cdot7\cdot7\cdot23 \\ 2255 & = 5\cdot11\cdot41 \\ 2256 & = 2\cdot2\cdot2\cdot2\cdot3\cdot47 \\ 2257 & = 37\cdot61 \\ 2258 & = 2\cdot1129 \\ 2259 & = ...
1
vote
0answers
84 views

Prove that every harmonic divisor number is semiperfect (eq there are no weird harmonic divisor numbers)

Prove that every harmonic divisor number is semiperfect (also called pseudoperfect). A harmonic divisor number is an integer $n$ such that $n\dfrac{\sigma_0(n)}{\sigma_1(n)}$ is an integer, and a ...
1
vote
0answers
133 views

Value of sum with primes

Can anyone tell me the value of sum $\sum_p\left(\log p(\frac{1}{2p}-\psi(\frac{p+2}{2})+\psi(\frac{p+1}{2})\right)-\sum_n\frac{(\log(2^n)}{2^n}$ where $p$ ranges over prime powers and $n$ ranges from ...
1
vote
0answers
71 views

Conjectures about zeta functions and poles

Let $p^*_n$ be the $n$ th element of a subset of primes such that $p^*_{n+1}>p^*_n$ and $p^*_n < O((n+2) ln((n+2))^3)$. Define $f(z)$ as the analytic continuation of $\prod_{n>0} ...
1
vote
0answers
122 views

All Sufficiently Large Squares, Represented as Sum of Two Semiprimes

Define a semiprime to be the product of two (not necessarily distinct) primes, $p_iq_i$. Conjecture: All squares $\ge 4^2$ are representable as the sum of two distinct semiprimes. Case 1: Squares ...
1
vote
0answers
117 views

The effect of roots of Dirichlet's $\beta$ function condenses to $\frac12\left(1+ie^{i2\pi\frac{p}4}\right)$

With the help of Raymond Manzoni and Greg Martin I was able to derive an explicit formula for the number of primes of the form $4n+3$ in terms of (sums of) sums of Riemann's $R$ functions over roots ...
1
vote
0answers
81 views

Prime Numbers and Primitive Roots

Let $p_1$, $ p_2$, $p_3$ different prime numbers. Let $N = p_1p_2p_3$. Given $(p_1-1)|(N-1), (p_2-1)|(N-1)$ and $(p_3-1)|(N-1)$, prove that for every number $a \in \Bbb N$ such that $\gcd(a,N) = 1$ ...
1
vote
0answers
28 views

Reasoning about $\left\lfloor\frac{p_k\#}{p_{k+1}}\right\rfloor$

This is a follow up question to my previous question. Let $$v_i = \left\lfloor\frac{ip_k\#}{p_{k+1}}\right\rfloor + c_i$$ where: $c_i \in \left\{1,2\right\}$ so that $v_i$ is odd and $v_ip_{k+1} ...
1
vote
0answers
157 views

Convergence of infinite series over prime numbers

Consider the following sum: $$\sum_{p\in\mathcal{P}}\frac{1}{p},\mathcal{P}=\{p|p\equiv1(\mod3),p\mathrm{\ is\ a \ prime \ split \ in\ } \mathbb{Q}(\sqrt[3]{3})\}$$ Question: Is this sum convergent ...
1
vote
0answers
66 views

Deriving this recursive expression for Riemann Prime Counting Function?

Why does this work? $f(n,k,1)=0$ $f(n,k,j)= \frac{1}{k} - f(\lfloor\frac{n}{j}\rfloor, k+1, \lfloor\frac{n}{j}\rfloor) + f(n,k,j-1)$ Here, f(n,1,n) computes the Riemann Prime Counting Function. ...
1
vote
0answers
91 views

Lower bound for $\pi(x)$

Is there a way to show that $$\frac{x}{\ln x} < \pi(x),$$ for sufficiently large $x$, using only elementary calculus? Apparently it is true for $x \geq 17$ (see this article). However, I am looking ...
1
vote
0answers
52 views

Ring of the residual classes $(\Bbb Z/p\Bbb Z)^\times$? $p$-adic integer?

In a recent question we raised the theorem: for a given prime $p$ and a given power $m$ the representation of any positive integer $n\in \Bbb N$ in the form: $$ n=(a_u p - b_u) \; p^m$$ is unique ...
1
vote
0answers
63 views

Consequencesof the Hadamard product expression of $L(s, \chi)$

I'm going through my lecture notes and I'm stuck on the proof of For any $t>0$ and primitive $\chi$ modulo $q$ $$\sum_{\rho=\beta+i \gamma: \Lambda(\rho, ...
1
vote
0answers
147 views

Fourier Analysis of Prime Counting Function

I was thinking about the following: Denote $\pi(x)$ as the prime counting function such that: $$ \pi(x) = \#\text{ of prime numbers}\leq x $$ It is well known from the prime number theorem that $$ ...
1
vote
0answers
48 views

conversion from psi function to prime counting function

Can we convert $\psi(x)$ to $\pi(x)$ without using integrals. Also if $\psi(x)>\psi(y)$ when we can say that $\pi(x)>\pi(y)$ . It seems that $\theta(x)>\theta(y)$ so $\pi(x)>\pi(y)$ but ...
1
vote
0answers
55 views

Galois invariant of Tate twists

let $k$ be the maximal extension of $\mathbb{Q}$ unramified outside a set $T$ of primes in $\mathbb{Z}$. Take a $p\in T$ and set $G=Gal(k/\mathbb{Q})$. I would like to now if there is a classical ...
1
vote
0answers
90 views

intuitive meaning behind Mertens' theorem

I have just been introduced the topic of distribution of primes, big O notation and aymptotic functions so please correct me if I say something that does not make sense. I am looking to get an ...
1
vote
0answers
55 views

Something related to Polignac conjecture

I would like that all of you interested in number theory and specially, in prime numbers, to take a look at this quite elementary approach on the problem related to the conjecture of Polignac, which ...
1
vote
0answers
70 views

Any work on properties of $N + \bar \phi (N)$?

I am looking for pointers to any existing materials about the properties of this quantity. For Euler's cototient, if a number $N$ is written as $2^a \cdot b$ with b odd then the cototient is $$\bar ...
1
vote
0answers
109 views

Location of Prime Gaps Subsequence

The primes are : 2,3,5,7,11,13,17,... The prime gaps are thus: 3-2,5-3,7-5,11-7,13-11,17-13,... 1,2,2,4,2,4,... An example subsequence of the prime gaps sequence is: 2,4,2 This subsequence begins ...
1
vote
0answers
77 views

Primes clasification

For all numbers $N > n$ ( $n$ is positive number), let $p$ be an odd prime $<$ $(2N)^{1/2}$ and $d = 2N-2p+1$, then there exist at least an odd number $d$ which does not contain any odd prime ...
1
vote
0answers
89 views

Is This a Good Prime Sieve?

I have played around with deriving a Boolean IsPrime function. http://science.niuz.biz/boolean-t313980.html?s=5e8b6805a1b73daa7c1062fabbe74e90 I have found a simple method for deriving a single ...
1
vote
0answers
136 views

Matiyasevich polynomial proof

Can someone provide a proof, or a link to a proof, of why does the Matiyasevich polynomial always generate primes for the nonnegative results? Any help will be appreciated.
1
vote
0answers
132 views

Approximation of distribution of $\pi_k(n)$ using $\zeta(s)$

Let $\pi_k(n) $ be the number of numbers with k prime factors (repetitions included) less than or equal to n. If we take the sums: $z_1(s) = \sum_{n= 1}^\infty \frac{1}{(p_{1,n})^s},~ z_2(s) = \sum ...
1
vote
0answers
291 views

Modular multiplicative inverse and coprime numbers needed.

I have a 64 bit algorithm that uses modular multiplicative inverse and coprime numbers, and I need to convert it to 32 bit. This math is not my area, and I cannot find an online calculator, so I hope ...
1
vote
0answers
143 views

factoring very very big random “numbers”

This is a variation on the theme of a rather flawed question that I asked months ago. Imagine a doubly infinite sequence, i.e. each member has a successor and a predecessor. Grab one term of the ...
1
vote
0answers
162 views

Prime numbers, Hardy conjecture and Ulam spiral

I would like to know why if the Hardy Littlewood conjecture is true, this could explain the position of the prime numbers on the diagonal of Ulam spiral. Thanks.
1
vote
0answers
94 views

Primes $p$ such that $5$ is a primitive root modulo $p$ , where $p$ is a Woodall prime?

How to prove following statement : Let $~p~$ be Woodall prime of the form : $p=n\cdot 2^n-1$ $5~$ is a primitive root modulo $~p~$ iff $~n \equiv 3,6,9 \pmod {20}$ For example : $5$ is a ...
1
vote
0answers
265 views

Primes p such that $3$ is a primitive root modulo $p$ , where $p=2^a \cdot M_q+1$

Let's define prime number $~p~$ as : $p=2^a \cdot M_q+1$ where $~M_q~$ is a Mersenne prime number such that $q \geq 3$ and $a$ is an even integer . Note that : Since $~M_q \equiv 1 \pmod 6 ...
1
vote
0answers
94 views

Is there a name for a number whose factors' exponents are all prime?

For instance, 864, whose factorization is 2^5 x 3^3.
1
vote
0answers
157 views

Forcing and divisibility

I'm going to bring together a couple of seemingly unrelated questions that I've asked here. This may be silly. Or maybe not? Imagine that $n$ is some sort of infinitely large integer, and thus so ...
1
vote
0answers
127 views

Binary sequences in primes

Is anything known about these problems? If we make a string S of 0's and 1's with 1 in n'th position if the the nth prime $p_n$ is of the form $1+m 2^{9^{9^{9^{9}}}}$, else 0, does every finite string ...
1
vote
0answers
214 views

Easiest way to prove that a subset of even integers is closed under multiplication?

What's the easiest way of showing that; $2\mathbb{Z}\setminus (4n-2)\mathbb{Z}$ is closed under multiplication? (I'm trying to show that $(4n-2)$ is a prime element of $2\mathbb{Z}$ by showing ...
1
vote
0answers
71 views

lower bounds for maximum computing times for integer factorisation

Supposing that n were known to have two prime factors, and that the computer had a database of all the primes $<\sqrt{n}$. Then, unless n is square, one factor would be $<\sqrt{n}$. If an ...
1
vote
0answers
83 views

Conjecture:$ \forall x , \exists m,n$, $ x<m<n $ and make $\pi(p_{m}+m) - m > \pi(p_{n}+n) - n$

$p_i$ is the $i^{\rm th}$ prime. $\pi(x)$ is prime counting function. Firstly, I think that Prime gap inequality holds true for any $i>0$: $p_{i+1} - p_{i} \leq i$. Very often, $\pi(p_{m}+m) - m ...
1
vote
0answers
227 views

Anti-prime sequence

I have permutation from $x$ to $y$. And how to make sequence which $d$ summed numbers from this sequence ISN'T a prime number. if we have sequence $x_1,x_2,x_3,x_4,x_5 \dots y$ than $d$ means : ...
0
votes
0answers
29 views

Upper bound number of distinct prime factors

I want to prove that if $\omega (n)$ is the number of distinct prime factors of $n$ for $n>2$ we have $\omega (n) \leq \frac{\ln n}{\ln \ln n} + O(\frac{\ln n}{(\ln \ln n)^2})$. How can I do this? ...
0
votes
0answers
49 views

Relation between Galois theory and Fermat primes

I am curious about a possible relation between Galois theory and Fermat primes. There is a general solution to any polynomial equation of degree less than or equal to $4$. The only Fermat primes (of ...
0
votes
0answers
39 views

Mapping set of integers to irrational numbers.

Mapping Integers to Irrationals..maybe even primes? Hi i'm an undergrad currently working on a research project. I recently thought of a question that I believe would help me greatly,but have ...
0
votes
0answers
15 views

How to show that $\sum_p \int_{p^m}^\infty f(x) dx = \int_0^\infty \pi(x^{1/m}) f(x) dx$

How do you show that for some function $f(x)$, $$\sum_p \int_{p^m}^\infty f(x) dx = \int_0^\infty \pi(x^{1/m}) f(x) dx$$ where the sum on left is taken over the set of all prime numbers $p$ and ...
0
votes
0answers
15 views

Upper bound for number of primes in an interval

Let $S(x,y)$ be the number of primes $p$ in $(x, x + y]$ such that also $p + 6$ and $p + 12$ are primes. I know that $$ T(x, y) \leq 48 c \frac{y}{\log^3 y} \left( 1 + O \left ( \frac{\log \log ...