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
2answers
37 views

Is this proof for number of divisors correct?

I'm trying to prove that the number of divisors of any given number is $(a_1+1)(a_2+1)...(a_r+1)$ Where $a_1, a_2 ... a_r$ are from $p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$ The problem is that the proof ...
0
votes
2answers
52 views

Summation of a series of Positive Prime numbers

Is there a way to find the sum for a set of positive prime numbers (e.g., the first $25$ prime numbers) without just arbitrarily adding them up shorthand?
5
votes
1answer
62 views

Is (73, 37) the only pair of reversible primes (p, q), s.t. p=2q-1?

In addition to being probably the only Sheldon Cooper prime, $73$ is a reversible prime $p$ (or emirp), such that its reverse is $q=(p+1)/2$. It is not hard to see that all other reversible primes ...
2
votes
1answer
34 views

Understanding Wright's proof of Landau's theorem

I'm reading Wright's A simple proof of a theorem of Landau in which the core argument is a proof by induction and I find myself stuck on a major point. I must be misunderstanding notation or something ...
6
votes
2answers
96 views

Do the sum of all prime reciprocals with the digit $3$ converge or diverge?

$$\frac{1}{3}+\frac{1}{13}+\frac{1}{23}+\frac{1}{31}+\frac{1}{37}+\frac{1}{43}\cdots$$ Intuitively, I feel that this sum converges, but I really don't know why, (or if I am correct). Can I have a ...
0
votes
1answer
61 views

Out of all the proofs of the PNT, which one is the most accessible?

I have been studying the continuation of the Riemann zeta function $\zeta(s)$ for the past while. I can prove that all the zeroes must lie in the critical strip.I am currently in the process of using ...
0
votes
1answer
45 views

Sum of factors of multiplication of different numbers

Given $N$ numbers $n_i$ such that $\forall i \le N, n_i$ $\le10^9$, is there a method to calculate the sum of divisors of their product? For example, given $\{11,15,17\}$ their product would is ...
0
votes
0answers
58 views

Prime divisors in Andy Loo's proof…

http://arxiv.org/pdf/1110.2377v1.pdf I have one more question related to that proof. Look at the definition of the symbol ${s \brace r}$ (page 4). Why if $\frac{3n}{4}<p\le \frac{4n}{5}$, then $p$ ...
1
vote
2answers
69 views

$a^4+b^4+c^4+d^4 \neq 2^{2011}$

Prove (elementary, meaning no high level theorems used) that there can not exist 4 prime numbers a,b,c,d $\geq$ 7 such that \begin{equation}a^4+b^4+c^4+d^4=2^{2011}\end{equation} I tried the ...
1
vote
1answer
33 views

Distribution of primes and product of primes

I know for large numbers $\le N$, the distribution of primes is about $N / \ln(N)$. I want to know thet distribution for primes and the product of unique primes ($p_0, ..., p_0 p_1, ..., p_0 p_1 ...
3
votes
1answer
67 views

A few questions about Andy Loo's proof of existence of primes between 3n and 4n…

I have a few questions about Andy Loo's proof (get it here): why, for example, if $2n<p\le3n$, then $p$ does not divide $\binom{4n}{3n}$? Same situation for $\frac{4n}{3}<p\le\frac{3n}{2}$... ...
5
votes
1answer
244 views

Conjectured compositeness tests for $N=k\cdot 2^n \pm 1$ and $N=k\cdot 2^n \pm 3$

How to prove these conjectures ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ~\text{are ...
0
votes
2answers
54 views

Analytic continuation of primality function

(There is my initial question, but by advice of @Charles I'm splitting it) For integers we have a primality function: $$ isprime(n)=\begin{cases}1,&\text{$n$ is prime}\\0,&\text{$n$ is not ...
0
votes
0answers
57 views

Is there a systematic way of referring to a prime?

Is there a systematic scheme for identifying primes? For small numbers, it is easy to simply reproduce the whole prime, but for larger numbers, it seems like it could get cumbersome. For instance, ...
1
vote
2answers
37 views

How many $2$-Sylow subgroups in $G$ with $|G| = 2^2\cdot 3$?

I have a group $G$ with $|G| = 2^2\cdot 3$. I also know it has $4$ Sylow-$3$ subgroups. I need to show that there is $1$ Sylow-$2$ subgroup. (This is all I have left from the full question.) Any ...
6
votes
1answer
101 views

Prove for $2p +1$ divides $2^p + 1$

The following theorem is well known and already proven by Lagrange 1775 Let $p = 3$ (mod $4$) be prime. $2p+1$ is also prime if and only if $2p+1$ divides $2^p - 1$. But how can we prove this: Let ...
0
votes
1answer
30 views

For $n$ an even number and $p$ a prime, does $\lfloor {\frac {n}{4}} \rfloor= \frac{1}{\pi (n)-\pi (n/2)} \sum_{n/2<p<n} p-\frac {n}{2}$ hold?

I was playing around with prime numbers and I noticed that for $n$ an even number, the average of the distance between all primes between $n/2$ and $n$ and $n/2$ is equal to $\lfloor {\frac {n}{4}} ...
2
votes
1answer
56 views

Solutions of $(2x-1)^x\equiv1\mod\ p$ [closed]

Has the equation $(2x-1)^x\equiv 1\mod{p}$, for $p=1+6qx$, where $p$, $q$ are primes, $x$ is an odd integer and $x<p$ any solutions except $x=1$? Many thanks.
0
votes
1answer
66 views

Sum of primes at minimal $\gt t!$

$$2+3+5+17+97+599\cdots a_t \gt t!$$ What does that mean? Well it is a sum that follows specific rules. For one, the number of terms in the sequence is $t$. Similarly, $a_t$ represents the $t$'th ...
1
vote
1answer
34 views

Weierstrass factorization theorem and primality function

I'm interested in application of the Weierstrass factorization theorem to the primality function. Let $np(x)\colon \mathbb N\to \mathbb N$ is a "not-prime" function: $$ np(x) = \begin{cases}1, & ...
2
votes
1answer
27 views

A congruence for the prime counting function in Wolfram.What does it actually say?

I saw today in functions.wolfram.com a congruence for the prime counting function which says $\binom {2prime(k)-1} {prime(k)-1} \pmod{prime(k)^3}=1$ (the third congruence at the bottom). What does ...
0
votes
2answers
47 views

On primality of the numbers of the form $10^{2k} - 10^{(k+1)} -1$

Has anyone seen proof that numbers of the form $10^{2k} - 10^{k+1} - 1 \space \forall k \ge 2$ are prime?
2
votes
2answers
33 views

Using a sieve and Mertens' theorem to show a formula for $\pi(x)$ - Does this work?

When I was younger, just starting highschool, I loved tinkering with prime sieves. I still have notes that I took. I had written down that $$\pi(x)\sim x\prod_{n=1}^m\frac{p_n-1}{p_n}+m-1.$$ ...
3
votes
3answers
69 views

Number of primes from $n!+1$ to $n!+n$

Why aren't there any primes between $n!+1$ and $n!+n$ for all $n>1$? This question was on AHSME 1969 #23, but the question is trivial because it's multiple choice. However, I have no idea how to ...
3
votes
1answer
91 views

Intersection between the sums of the first positive integers, primes and non primes

Conjecture : $$\left\{\sum\limits_{\begin{array}{c}k=1\\k\in\mathbb{Z}\end{array}}^nk \ |\ n\in\Bbb Z\right\} \cap \left\lbrace ...
4
votes
2answers
71 views

If for almost all $p \equiv 1$ (mod a) it holds that $p \equiv 1$ (mod m), then…

Let $a,m\in \mathbb N$ Suppose that for almost all primes $p \equiv 1$ (mod a) we have that $p \equiv 1$ (mod m) Can we say something about $a$ and $m$? For example $m$ divides $a$ or vice versa? I ...
3
votes
2answers
34 views

Is it known whether there are ever infinitely many primes of the form $\prod_i p_i^{n_i} + 1$ where the $p_i$ are fixed primes but the $n_i$ can vary?

So if we fix finitely many primes $p_i$, where one $p_i$ is $2$, but let the powers $n_i$ on the $p_i$ vary, is it known whether it is ever possible to have infinitely many primes of the form $\prod_i ...
2
votes
1answer
48 views

Comparing $\pi(x)$ and $\pi^{(k)}(x)$

We say a k-almost prime is an integer that results as the product of k prime, counting repetition. For example, $12$ is a $3$-almost prime as $12= 3 \times 2 \times 2$. Additionally, we define ...
0
votes
0answers
10 views

Convenient goedel numbering for finite register machines?

Overview I'm trying to find a goedel numbering for finite register machines, which is convenient in two ways: when ordering machines by their numbering, simple machines shall come first, i.e. ...
2
votes
1answer
72 views

How do computers generate primes so quickly?

From what I understand, when a computer encrypts a file using an encryption standard like RSA, one of the steps is to generate two large primes, and multiply them together. I have created RSA keys on ...
6
votes
2answers
334 views

Smallest Positive Integer Not Coprime to a Collection of Consecutive Integers

Let $n\in\mathbb{N}$. Define $f(n)$ to be the smallest positive integer $m$ such that there exists a positive integer $k$ for which $k+i$ is not relatively prime to $m$ for every ...
6
votes
0answers
135 views

Is there a quicker way to generate integers which are hard to factor than multiplying two large primes?

An easy way to generate an integer which is hard to factor is to find two large primes and multiply them. As a bonus, you know the factors. I'm interested in whether it's possible to find integers ...
1
vote
2answers
25 views

Distribution of decimal repunit primes

The prime number theorem describes the distribution of prime numbers in positive integers. Is there a similar theorem describing the distribution of primes among positive integers of the form ...
0
votes
1answer
48 views

Time complexity of a simple factoring algorithm?

This has puzzled me for a little. I start off with a list of primes that is sufficiently large. For my number $n$, I do trial division of primes in ascending order until I reach a prime that divides ...
0
votes
1answer
79 views

Using The Riemann Zeta Functional Equation

Riemann was able to establish the following link between the Riemann zeta function and the weighted prime counting function $J(x)$. $$\ln(\zeta(s))=s\int_1^\infty J(x)x^{-s-1}dx$$ Using the Mellin ...
1
vote
0answers
43 views

Probability number is divisible by half the square of a prime?

Let $p$ be a prime. What is the probability that a number of the form $\left \lceil \frac{p^2}{2} \right \rceil$ divides a random positive integer $n$. I have a solution that involves the Riemann-Zeta ...
3
votes
1answer
28 views

Is there a way to estimate the number of positive integers less than or equal to $n$ that have a given prime $p$ as a least prime factor

The probability that an integer $p$ divides an integer $x$ is $\dfrac{1}{p}$. From this article on almost prime numbers, the number $\pi_k(n)$ of positive integers less than or equal to $n$ with at ...
7
votes
1answer
101 views

Distribution of the sum reciprocal of primes $\le 1$

$$\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\cdots \le 1 $$ This is an interesting infinite summation. This is very closely resembling my other problem with has to do with the distribution of ...
5
votes
1answer
96 views

Finding Gaussian Primes along Lines in $\mathbb Z[i]$

I am trying to prove the following statement: For all positive integers $a$ does there exists a positive integer $b$ such that $a^2 + b^2$ is prime? (If so, can we provide such a $b$?) Given the ...
0
votes
1answer
27 views

Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n

Given the number $n=35$.Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n I found this problem on internet and i am trying to find a solution ...
2
votes
3answers
53 views

Find all numbers that have 30 factors and have 30 as one of their factors.

Find all numbers that have 30 factors and have 30 as one of their factors. Thank you. Note: please show way if possible.
1
vote
2answers
84 views

Do prime numbers have prime factors?

(This is a somewhat trivial question). Do prime numbers have prime factors, i.e. itself? For example is 7 a prime factor of 7? The reason I ask this is because there is a statement in my lecture ...
1
vote
1answer
34 views

Find the smallest prime number that doesn't divide any 5-digit number whose digits are in strictly increasing order.

Find the smallest prime number that doesn't divide any 5-digit number whose digits are in strictly increasing order. I have posted an answer of my own below; any alternative solutions will also be ...
1
vote
1answer
61 views

Why does symmetry happen in reset-based random walks?

Studying the basic concepts about random walks / brownian motion, and based on the idea of a Möbius-based walk in Wolfram's website, I wanted to try my own version of it in Python to compare it with ...
0
votes
1answer
24 views

What is the summatory function of the number of (not necessarily distinct) prime factors?

In the Math World article on Merten's Constant, a related constant $B_2$ is mentioned which "appears in the summatory function of the number of (not necessarily distinct) prime factors." I am very ...
3
votes
2answers
57 views

How is the Twin Primes Constant useful? What value does it provide over Brun's Constant?

The Twin Primes Constant is: $$\prod_{p > 2 \text{ and a prime }}\left(1 - \frac{1}{(p-1)^2}\right) = 0.6601618158\ldots$$ It appears that in this case $p$ does not have to be a prime. But if ...
1
vote
4answers
92 views

How do I show that:if$p$ is prime $>5$ then $p^4-20p^2+19$ is always divisible by $180$.?

Is there someone who can show me How do i show that :If $p$ is a prime number greater than $5$ then : $$p^4-20p^2+19$$ is always divisible by $180$. Note : i think should factor $p^4-20p^2+19=$ ...
2
votes
0answers
38 views

Prime from mirror concatenation of first primes

The mirror concatenation of the first 1, 6 and 8 prime numbers with no primes being reversed is a prime ! i.e. 131175323571113 and 19171311753235711131719 are prime numbers! (beautiful primes!). After ...
1
vote
1answer
233 views

How to get this equation solved?

I came across this equation $$\sqrt a-\sqrt b=\sqrt 7-\sqrt 5$$ And you have to find the value of '$a$' and '$b$' when both of them are primes. The solution was $a=7, b=5$. Now, my question is, ...
2
votes
1answer
82 views

Proof that $2^n-1$ does not always generate primes when primes are plugged in for $n$?

Exactly what the name entails. The function $2^n-1$ I see largely tends to generate primes when $n$ is prime. However, a week ago I heard that this was horribly false. Please show me a disproof.