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

Proof concerning specific class of Proth numbers

Is this proof acceptable ? Theorem Let $N = k\cdot 2^n+1$ with $n>1$ , $k<2^n$ , $k$ odd and $3 \nmid k $ , thus $N$ is prime iff $3^{\frac{N-1}{2}} \equiv -1 \pmod N$ Proof Necessity ...
1
vote
0answers
44 views

Prime numbers that fits in a specific pattern

Any series $\displaystyle \sum_{k=0}^{\infty}a_k2^{-k}$, where $a_k\in\{0,1\}$, converges to some $x\in[0,2]$ and since the sequence $a_n$ is unique for each $x\in[0,2]$ there is an bijection between ...
1
vote
0answers
47 views

Sequence of primes by concatenating digits in a given base.

Given a base, $b$ is there is a sequence $\lbrace a_n\rbrace_{n\geq 0}$ where $a_k \in \lbrace 1,2\cdots, b-1\rbrace$so that the sequence: $$b_n:= \sum_{k=0}^n a_kb^k$$ is a sequence of primes ...
1
vote
0answers
49 views

Fast algorithm for generating consecutive primes larger than N

I'm looking for a fast algorithm to generate primes larger than a random 4096 bit number $N$. I know about the Sieve of Atkin, but AFAIK it can only be used to find all primes up to a certain limit. ...
1
vote
0answers
28 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 3

Following a previous question (here you'll find an introduction): The book states that almost surely $$\pi_S(x+y)-\pi_S(x)=\mathrm{li}(x+y)-\mathrm{li}(x)+O(\sqrt y)$$ as soon as $y/(\log ...
1
vote
0answers
40 views

A Question Related to Zsigmondy's Theorem

I am wondering if there is a way to prove the following statement, which bears some resemblance to Zsigmondy's Theorem. I am not sure if the statement is true, but it seems as though it should be. ...
1
vote
0answers
89 views

How I could transform this into product over primes :$s_p$= $\frac{1}{2^2-1}+\frac{1}{2^3-1}+…\frac{1}{2^p-1}$?

1)Can I transforme this sum into product OVER primes:$s_p$= $\frac{1}{2^2-1}+\frac{1}{2^3-1}+....\frac{1}{2^p-1}$ ? Note : p is prime number and ${2^p-1}$ is prime 2)I would be interest to know ...
1
vote
0answers
34 views

RSA aloghorithm - stuck on d

I'm sorry in advance if this sort of question has been posted before. I couldn't find it. I'm clearly an idiot, and I clearly need help, so here I am. I have a homework assignment which overall is ...
1
vote
0answers
54 views

Wolstenholme Number

Does Wolstenholme Numbers have perfect squares other than 1 and 49? The first few are 1, 5, 49, 205, 5269, 5369, 266681, 1077749 seems to be a complicated problem
1
vote
0answers
33 views

On non-divising primes of an integer $x$

We know more about divisor than non-divisors, If we consider the sets : $$P^{1}_{x} =\left \{ p \leq x : \ p \in \mathbb{P} \right \}$$ ($\mathbb{P} $ is the primes set) $$ P^{2}_{x} =\left \{ ...
1
vote
0answers
38 views

What is the status of research on primes as an example of general sieve-generated sequences?

I have been interested in treating the prime numbers as a special case of sieve-generated sequences, however they may be defined by different authors. Can someone here give me any information about ...
1
vote
0answers
28 views

Is there a Poulet number with this condition?

Is there a Poulet number $n$ with this condition: $◎(n)=\frac{n+1}{2^x}$ or $\ ◎(n)=\frac{n-1}{2^x}, \ x \in \mathbb{N}_{\gt 0}$? (Recall that a Poulet number is a composite $n$ such that $2^n−2$ is ...
1
vote
0answers
40 views

Existence of primes $p$ such that all the prime divisors of $p+1$ divide $p-1$

This question recently came up to me in a project and is not taken from a textbook. I would like to know if any characterization of such primes is known from literature. They are seemingly rare but do ...
1
vote
0answers
45 views

Are there such prime giving functions?

Here let us define a function $f : \mathbb{N} \rightarrow \mathbb{N}$ , such that for every $n$ , The sequence $\{f(n) ,f(n)+1 ,f(n)+2 , f(n)+3, \dots , f(n)+n\}$ contains atleast $1$ prime . Let us ...
1
vote
0answers
65 views

Prime Zeta Function

Does $$\sum_{p \text{ prime}} \frac{1}{p^s} \sim \log \zeta(s) \quad \text{as} \quad s \to 1^+$$ imply $$\sum_{p \leq n} \frac{1}{p} \sim \log H_n \quad \text{as} \quad n \to \infty,$$ where $H_n$ is ...
1
vote
0answers
54 views

About a paper by Gold & Tucker (characterizing twin primes)

I've carefully looked at the questions on prime and twin prime, but the following question seems not to habe been asked before. Context: In the paper by Jeffrey F. Gold and Don H. Tucker titled A ...
1
vote
0answers
38 views

Estimating the Twin prime constant

http://numbers.computation.free.fr/Constants/Primes/twin.html it says: "This last constant occurs in some asymptotic estimations involving primes and it's interesting to observe that it may be ...
1
vote
0answers
61 views

Density of “fake” prime numbers?

I suspect I've stumbled upon something, which may, hopefully, have certain significance. I'd greatly appreciate any input. Let's consider a sequence of real and "fake" prime numbers, e.g. $\{2, 3, 5, ...
1
vote
0answers
87 views

How to prove this sieve of prime form 12 * i + 5 is correct?

Step 1, make x columns rows data A and data B: ...
1
vote
0answers
37 views

Infinitely many primes in second-order recurrence

I just wondered about the following question: Suppose that we are given a homogeneous second-order recurrence relation, $x_{n+2}+ax_{n+1}+bx_n=0$ for all $n\in\mathbb{N}$. Can we choose integers ...
1
vote
0answers
41 views

Existence of a prime in an interval that is not a linear combination of two specified primes?

If $ n = \left( \frac{p+q}{2 } \right) + p q :p,q \in\mathbb{P}-\left\{2\right\} $ Can we show there exists a prime number $\theta : \sqrt{2n} \leq \theta \leq n $ and $\theta$ is not a linear ...
1
vote
0answers
41 views

Program for Handling Huge Primes

I am trying to run a program with really large primes (around the $10^{20}$th prime), but Mathematica seems to only be able to handle around the first $10^{12}$ primes. Is there any software that can ...
1
vote
0answers
14 views

Creating Polynomial

By relative prime factor theorem $$R = (Zm,+,.)$$ where R is the ring structure the input is $e_0 = 0$ and $e_1=1$ output is $$S_0 = { k : \gcd(m,k)>1 }$$ $$S_1 = { k : \gcd(m,k) = 1}$$ Now ...
1
vote
0answers
65 views

Prime number greater than n

Consider the follwing problem: Given $n$ (in binary) output a prime number $p \geq n$ (not necessarily the first prime number after $n$) Are there better techniques than the trivial one that scans ...
1
vote
0answers
34 views

Find prime pairs satisfying the equation

Find all ordered pairs $(p_{k},p_{k+1})$, where $p_k$ denotes the $k$-th prime, such that for every $m\ \in \mathbb{N}$ there exists $\alpha \in \mathbb{N}$ s.t. $\Omega(\alpha) = m$ so that ...
1
vote
0answers
39 views

About Abel Summation

http://arxiv.org/pdf/math/0504289v3.pdf Here i'm trying to understand page 5. Writer uses the abel sum to find the sum of the prime's reciprocals. So he founds the formula (2.2.1) Now here y=2 ...
1
vote
0answers
62 views

Primality of $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , when $q$ is prime, $j\ge0$?

Let $P_{q,j}=(2^{q^{j+1}}-1)/(2^{q^j}-1)$ , $q$ prime and $j\ge0$. $P_{2,j}$ is a Fermat number, $P_{q,0}$ is a Mersenne number. Apart from Fermat primes and Mersenne primes, and apart from ...
1
vote
0answers
62 views

Integration by parts of the Logarithmic Integral

I am doing work on analytic number theory, and I am currently looking at the Prime Number Theorem, that is $$\pi(x) \sim Li(x)$$ Some of my sources say that I can do integration by parts on the ...
1
vote
0answers
74 views

Is this wave noisy at prime powers and silent at composite numbers?

Mathematica knows that: $$\log(n) = \lim\limits_{s \rightarrow 1} \zeta(s)\left(1 - \frac{1}{n^{(s - 1)}}\right)$$ And the von Mangoldt function should then be: $$\Lambda(n)=\lim\limits_{s ...
1
vote
0answers
62 views

How to solve diophantine equation $\frac{x^p-y^p}{x-y}=n$

$$\frac{x^p-y^p}{x-y}=n$$ whit $p$ a prime greater than or equal to $3$,for what value to $n$, it's solvable and how to solve,and whether $\frac{x^p-y^p}{x-y}=q_1$ $\frac{x^p-y^p}{x-y}=q_2$ is ...
1
vote
0answers
27 views

Why do we need the extra assertion in this question?

Proposition: Let $2^i$ be the highest power of 2 dividing m, let a be odd and assume that $x^{m} \equiv a\space (mod\space 2 ^ {2i+1}$ ) is solvable. Then $\forall$ $j \geq$ 2i + 1, $x^{m} ...
1
vote
0answers
43 views

Identity based encryption

I am implementing ID based encryption in c# right now i am having problem at the following mathematics $$H_1: \{0,1 \}^n \times \{0,1 \}^n \to \mathbb{Z}^*_p, \text{ what does this expression ...
1
vote
0answers
114 views

About $f(s)=\sum_{a^2+b^2>0} \frac{(-1)^{a^2+b^2}}{(a^2+b^2)^s}=0$ and the Extended Riemann Hypothesis.

Let $s$ be a complex number with a strictly positive real part ($Re(s)>0$). Let $f(s)=\sum_{a^2+b^2>0} \dfrac{(-1)^{a^2+b^2}}{(a^2+b^2)^s}$ where the sum runs over all positive integers $a,b$ ...
1
vote
0answers
76 views

The maximum distance between two successive coprimes of n

I am exploring the symmetries and distribution of the coprimes of a natural number $n$. Does anyone have any insight into how to express the maximum distance between two successive coprimes of $n$? ...
1
vote
0answers
76 views

Does the Riemann zeta function tell us about the order theoretic properties of the natural numbers?

The classical Möbius function $\mu(n)$ fulfills the multiplicative inversion formula, e.g. see this thread. Now I see in the theory of posets, they generalize the concept of that function, see ...
1
vote
0answers
34 views

Schoenfeld's limits & almost primes

If I am correct in my understanding, the Tao-Green theorem employed almost primes as density normalisers. If $N_k(x)$ is the counting function of almost primes, is the study of almost primes 'useful' ...
1
vote
0answers
90 views

Question about tetration modulus a prime $p>100$

Define $x§y$ as the power tower : $x^{x^x...}$ where $...$ means $y$ times. For instance $2§1=2,2§2=4,2§3=16,2§4=2^{16}$. See : http://en.wikipedia.org/wiki/Tetration Let $p$ be a prime larger than ...
1
vote
0answers
70 views

Using Bayes' Theorem to calculate if a number is prime if it passed a primality test

According to this, I can use Bayes theorem to calculate if $n$ is composite given that it passed the Miller-Rabin primality test: ...
1
vote
0answers
51 views

Decomposition subgroup of Cyclic Galois Extension

My question: Say we have a cyclic Galois extension of degree $n$ over $\mathbb{Q}$. Denote the Galois group as $G$. If $H\leq G$, then does there exist a prime, $q$ in $\mathbb{Z} \subset \mathbb{Q}$ ...
1
vote
0answers
80 views

Estimations for the number of prime factors, counted with multiplicity (elementary combinatorics)

If $N_k(x):=\ \mid\{n\leq x : \Omega(n)=k\}\mid$, where $\Omega(n)$ is the number of prime factors (counted with multiplicity) in $n$, I am trying to reason a crude under-estimate for large $k$ and ...
1
vote
0answers
28 views

A sequence converging to the number of decompositions of $2n$ as a sum of 2 primes

For every even positive integer $n>2$ and every non-negative integer $k$, let's define the sequence $N_{k}(n)$ as follows: ...
1
vote
0answers
110 views

Special matrices with determinant 0

Define a quadratic matrix A with n rows and n columns by filling it with consecutive primes, starting with some prime p. The object is, to find the least starting prime p, such that A has determinant ...
1
vote
0answers
46 views

Asymptotics for prime factors

Am I correct in assuming that the same result: $$ N_k(x):=\ \mid\{n\leq x : \Omega(n)=k\}\mid \ \sim \frac{x}{\log x}\frac{(\log_2 x)^{k-1}}{(k-1)!}\ (x \rightarrow \infty) $$ also holds for: $$ ...
1
vote
0answers
91 views

Is this statement equivalent to Goldbach's conjecture

Given a number $n\ge 3$, then one of these is true: \begin{equation} \begin{cases}2n = (6m-1)+P, \ \ \ P \in \mathbb P, \ 6m-1 \in \mathbb P, \ 6m+1 \in \mathbb P \ \ \ \ (1) \\ 2n-1 \in \mathbb P, \ ...
1
vote
0answers
44 views

How to express coprimality as a constraint in an optimization problem over integers?

I am currently working with an optimization problem that is defined over a a set of $D$-dimensional integer vectors where each component is bounded by $M$. Let us refer to this optimization problem ...
1
vote
0answers
37 views

Proving irrationality i p,s and k are primes number?

Can you prove that $\frac{k^{\frac13}-p^{\frac13}}{s^{\frac13}-p^{\frac23}}$ is irrational if p, k and s are different prime numbers. I am certain it is but i dont know how to prove it.
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
105 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
84 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
81 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 ...