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

4
votes
0answers
235 views

Ideals in Gaussian integers

Let $R:=\mathbb{Z}[i]$. Prove that every nonzero prime ideal $\mathfrak{P}$ of $R$ belongs to one of the following families: 1) $\mathfrak{P}=(1+i)R$ 2) $\mathfrak{P}=(a+bi)R$ where ...
5
votes
2answers
276 views

Smallest prime of the form 41033333333…?

What is the smallest prime of the form 410333333333.... ? It should have more than 10 000 digits. [added from answer posted 2013 May 26 at 20:52 by Peter] I thought it would be clear, but it ...
10
votes
0answers
200 views

An infinitude of “congruence condition” primes?

Background: Several special classes of primes can be written as primes that satisfy some additional constraint $f(p)\equiv 0\pmod p$; for instance, Wilson primes are congruence primes with ...
2
votes
1answer
132 views

Unique decomposition of $c$ sums of products of $k$ prime numbers, allowing duplicates?

Suppose that there are $n$ different prime numbers. Define procedure a) as following ($k \leq n$ and $k$ fixed): procedure a) for each time, we select one number out of $n$ possible cases and multiply ...
0
votes
1answer
130 views

Showing existence of an element with order $p$

If a group $G$ has order $p^n$, where $p$ is prime and $n \geq 1$, does there exist some element $a\in G$ s.t. the order of $a$ is $p$? I happen to know that this is true by Cauchy's theorem, but ...
4
votes
1answer
107 views

binary-decimal primes

Converting an integer $N$ into binary and then reading the result as a base-10 number $N_2$, the prime $N=3$ gives $N_2=11$ (which is also prime) and $N=5$ gives $N_2=101$. Are $3$ and $5$ the only ...
3
votes
0answers
88 views

A challenging problem on prime uncertainty interval

I have a very challenging problem to solve, seeking for good advice; I have to make an intro in the first part and then comming to the problem. Theorem (1): In an interval between a prime $p$ and its ...
3
votes
1answer
53 views

Why does $(k-2)!-k \left\lfloor \frac{k!}{(k-1) k^2}\right\rfloor = 1,\;k\ge2\;\implies\;\text{isPrime}(k)$

Let $k$ be a integer such that $k\ge2$ Why does $$(k-2)!-k \left\lfloor \frac{k!}{(k-1) k^2}\right\rfloor = 1$$ only when $k$ is prime? Example: $$\pi(n) = \sum _{k=4}^n \left((k-2)!-k \left\lfloor ...
0
votes
3answers
109 views

$2^{q-1}\equiv 1\pmod{q}.$

The question is asking to show that $q$ must be prime given $$ 2^{q-1}\equiv 1\pmod{q}. $$
2
votes
0answers
55 views

Merthen's third theorem and uncertainty of prime hits

Conjecture(1) Merten's third theorem says: $$\lim_{L\to\infty}\ln L\prod_{p\le L}\left(1-\frac1p\right)=e^{-\gamma}$$ we have a wild discussion here around the table whether it is possible to ...
1
vote
1answer
54 views

Information on “stronger form” of Dirichlet's Theorem on Arithmetic Progressions

From Wikipedia: "Stronger forms of Dirichlet's theorem state that, for any arithmetic progression, the sum of the reciprocals of the prime numbers in the progression diverges." Can anyone direct me ...
3
votes
1answer
165 views

Question on primes.

Let $p(n)$ denote the number of primes less than $n$. Show that there are infinitely many $n$ for which $n$ is divisible by $p(n)$. Source : here
2
votes
2answers
200 views

What is the distribution of primes modulo $n$?

Let $n\geq 2$ and let $k$ be "considerably larger" than $n$ (like some large multiple of $n$). Then for each $i$ such that $0<i<n$ and $\gcd(i,n)=1$ let's define $$c_i=\left|\{p_j\;|\; p_j\equiv ...
2
votes
0answers
109 views

Are there infinitely many primes $p_k$ such that $(p_k-1)!+p_k$ is a also prime?

I am wondering whether there are infinitely many primes $p_k$ such that $(p_k-1)!+p_k$ is also prime. Given that $p_k \equiv 2 \pmod 3$. For a very large prime, I can assume Stirling's ...
11
votes
2answers
773 views

How would proving or disproving the Twin Prime Conjecture affect proving or disproving the Riemann Hypothesis if at all?

How would proving or disproving the Twin Prime Conjecture affect proving or disproving the Riemann Hypothesis? What are the connections between both conjectures if any?
1
vote
4answers
181 views

Mathematical Induction prime help

I recently obtained "What is Mathematics?" by Richard Courant and I am having trouble understanding what is happening with the Prime Number Unique Factor Composition Proof (found on Page 23). The ...
0
votes
1answer
185 views

Number of combinations

You are given K prime numbers, bigger than 6, find the number of different number that can be made of those prime numbers(using 1 number, 2 numbers ..., k numbers). Obviously you need to get the ...
1
vote
3answers
47 views

Proving $\prod _{k=j}^n \frac{p_{k+1}}{p_k} = \frac{p_{n+1}}{p_j}\!\!,\;\;1\le j\!<\!n$

Let $p_n$ denote the $n$th prime number. How could one prove that: $$\prod \limits_ {k=j}^n \frac{p_{k+1}}{p_k} = \frac{p_{n+1}}{p_j}\!\!,\;\;1\le j\!<\!n$$ Examples: ...
7
votes
3answers
184 views

Primality of the numbers in the form of $2n^2-1$

I have a question about primality of integers in the form of $2n^2-1$. I can prove that for the certain type of n such integers are always composite. For example, if $n=7k+2$ or $n=7k+5$, the whole ...
4
votes
5answers
313 views

Proving that either $2^n-1 $ or $ 2^n+1$ is not prime

Not sure what approach to take with this: Prove that at least $2^n-1 $ or $ 2^n+1$ is composite $\forall$ $n>2$
3
votes
1answer
80 views

Proving that primes can't have two different decompositions

My previous questions have been on a very similar topics but I am having trouble with understanding this: I understand that $p_1$ or $q_1$ must be greater than the other but I have no idea what is ...
1
vote
1answer
95 views

ordered pairs of distinct primes

This is an olympiad question, I don't know how to solve. Please tell me the logic/algorithms/steps I should follow to solve the question. Find the number of ordered pairs of distinct positive primes ...
0
votes
1answer
85 views

Prime divisibility in a prime square bandtwidth

I am seeking your support for proving (or fail) formally the following homework: Let $p_j\in\Bbb P$ a prime, then any $q\in\Bbb N$ within the interval $p_j<q<p_j^2$ is prime, if and only if ...
9
votes
1answer
88 views

Fermat primes and the equation $x^2+y^2 = 10^n x+y$

This is related to the question by Naroza which was ably answered by E. Wong. In a nutshell, it seeks to find more examples of the curiosities, $$12^2+33^2 = 1233$$ $$88^2+33^2 = 8833$$ or, in ...
3
votes
1answer
55 views

Totient-like function

I have number written as factors for instance: n = 2 * 3 * 3 * 5. What I have to do is find how many numbers between <1, n) are co-prime to n, which means GCD = 1. It can simply be done using ...
-1
votes
3answers
210 views

Quantum uncertainty can explain the Riemann Hypothesis?

In the recent paper "Riemann Hypothesis as an Uncertainty Relation" (http://arxiv.org/abs/1304.2435) the author claims that the presence of zeros out of the critical line may lead to the violation of ...
6
votes
1answer
205 views

Topology on Integers such that set of all Primes is open

In my topology homework we are asked to describe a topology on the Integers such that: set of all Primes is open. for each $x\in\mathbb Z$, the set $\{x\}$ is not open. $\forall x,y \in\mathbb Z$ ...
0
votes
4answers
130 views

Is a set of prime numbers open in Furstenberg's topology?

I was reading Furstenberg's Proof of Infinitude of Primes and I wonder if a set of prime numbers is open in this topology. Thanks!
1
vote
2answers
215 views

Is every prime number less than twice the previous prime number?

And if so, how do you prove it? (for example 7 is less than 2 times 5, 11 less than 2 times 7, and so on).
5
votes
2answers
162 views

Analogy between prime numbers and singleton sets?

While trying -- in vain -- to write an alternative answer for another question (If $\cup \mathcal{F}=A$ then $A \in \mathcal{F}$. Prove that $A$ has exactly one element.), I discovered the following ...
3
votes
3answers
109 views

is $(x+1)^4-x^4$ non-prime for all natural positive integers $x$

Looking at difference between two neighbouring positive integers raised to the power 4, I found that all differences for integer neighbours up to $(999,1000)$ are non-prime. Does this goes for all ...
5
votes
1answer
465 views

Super prime numbers

I was reading about super prime numbers in Wikipedia, nothing looks Unusual until i read this line. every integer greater than 96 may be represented as a sum of distinct super-prime numbers. i ...
2
votes
1answer
111 views

Proving that Bombieri's Theorem implies Linnik's theorem

I'm stuck on a line in the proof of Bombieri implies Linnik, where Bombieri: For primitive $\chi$ mod $q$ with $q \leq T$ we define $$N(\alpha, T; \chi)=\#\{\rho=\beta+i\gamma \;:\; ...
0
votes
1answer
67 views

Why does $3+ (-1)\left(\left\lfloor\sum_{k=1}^{|\{x\in P,\;x\le n\}|} \frac{P_k}{1-P_k}\right\rfloor\right) = \pi(n),\quad n\ge1223$?

Let $P$ denote $\text{primes}$, and $\pi(x)$ denote $|P| \le x$. Here's my first question: Why does $$3+ (-1)\left(\left\lfloor\sum_{k=1}^{|\{x\in P,\;x\le n\}|} ...
2
votes
1answer
663 views

Conjecture on cycle length and primes

That thanks for Peter Košinár's answer,I change the conjecture a lot. For positive odd $a$, let $b = A179382((a+1)/2)$,let $b_1 = znorder(Mod(10,a))$,If $b = (a-1)/(2^c)$ and $b_1 = (a-1)/c_1$ for ...
2
votes
1answer
100 views

Prime numbers; how to do this?

You can write every number as the product of some prime numbers, for example $33 = 11 \cdot 3$. However, how can you do this when you're dealing with a prime number? If you write $29 = 29 \cdot 1$ you ...
-1
votes
2answers
331 views

How to quickly check if a number is prime? [closed]

Let say I've found a very very very long prime number. I know it's prime but I need to have a proof. Is there any fast way how to check if a number is really prime? Let say I've found the longest ...
26
votes
4answers
632 views

About the property of $m$: if $n < m$ is co-prime to $m$, then $n$ is prime [duplicate]

The number $30$ has a curious property: All numbers co-prime to it, which are between $1$ and $30$ (non-inclusive) are all prime numbers! I tried searching(limited search, of course) for numbers ...
3
votes
2answers
130 views

Proving that there are infinitely many prime numbers of the form $4k+3$

Anyone wanna help me solve this one? Been at it for a little bit but haven't really gotten anywhere..
1
vote
1answer
56 views

Power analogies to primes

As we all know, a natural number $n$ is prime if and only if there do not exist natural numbers $x, y$ exclusively between $1$ and $n$ such that $xy = n$. Is there any generally recognized analogy ...
3
votes
1answer
114 views

Only 3 $n$ where $q=\left\lfloor (2 p_n+p_{n+2}) (p_{n}+p_{n+1}+p_{n+2})\over p_{n}\right\rfloor,\;\text{isPrime}(q)$?

Consider: $$q=\left\lfloor (2 p_n+p_{n+2}) (p_{n}+p_{n+1}+p_{n+2})\over p_{n}\right\rfloor,\;\text{isPrime}(q)$$ where $p_n$ denotes the $n$th prime. Other than: $$n=6\quad\text{or}\quad ...
4
votes
3answers
113 views

Right triangles with integer sides

Most of you know these triples: $3: 4 :5$ $5: 12 :13$ $8: 15 :17$ $7: 24 :25$ $9: 40 :41$ More generally we can construct such triangles such as $$2x:x^2-1:x^2+1$$ My question is why one of ...
4
votes
3answers
260 views

How do you prove that the mean of the co-primes of a number is half the number?

Say $n = 6$, The set of co-primes is $\{1, 5\}$, $\text{mean} = 3$ For $n = 9$, the set of co-primes is $\{1, 2, 4, 5, 7, 8 \}, \text{mean} = 4.5$ Question: Prove that the mean of co-primes of ...
3
votes
0answers
87 views

Prime numbers problem - discrete math [duplicate]

Show that natural numbers of the form $n^2+1$ are not divisible by primes of the form $p=4k-1$. I can't really find a place to start. Thank you very much in advance, Yaron.
14
votes
3answers
396 views

$\sum\limits_{\text{prime }p} 2^{-p}$ is an irrational number

I need help to prove the following result. $\displaystyle\sum_{\text{prime }p} 2^{-p}$ is an irrational number.
6
votes
1answer
129 views

What's the asymptotic distribution of $p^n$ (powers of primes)?

We know by the prime number theorem that $\lim_{n\to\infty}\frac{\pi(n)}{n\,/\ln n} = 1$ An even better approximation is $\lim_{n\to\infty}\frac{\pi(n)}{\int_2^n\frac{1}{\ln t}\mathrm{d}t} = 1$. Is ...
5
votes
0answers
278 views

The divergence of the series of reciprocals of primes (proof check):

I just wanted to check my attempt at a proof for the divergence of: $$\sum_{n=1}^{\infty} \frac{1}{p_n} \tag{ $\star$ }$$ We begin with assuming that $(\star)$ converges. If $(\star)$ ...
2
votes
3answers
65 views

Does there exist a k such that the kth prime is balanced in order k-1?

A balanced prime of order n is a prime number that is equal to the arithmetic mean of the nearest n primes above and below. For example, 5 is a balanced prime in order 1 because it is the average of ...
9
votes
1answer
312 views

interpolating the primorial $p_{n}\#$

The primorial $p_{n}\#$ is given by the product $p_n\# = \prod_{k=1}^n p_k$ (where $p_{k}$ is the $k$th prime) -- is there a natural (a la the gamma function $\Gamma(z)$) way of interpolating it for ...
6
votes
2answers
229 views

Do we know if there are more primes with even leading digits or odd leading digits?

I was just wondering, out of curiosity, do we know if there are more primes with even leading digits or odd leading digits? For example, primes with even leading digits would be $23$ or $29$ and ...