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
3answers
491 views

Are the first 1,000 prime numbers enough to build every Goldbach number up to 9 digits long?

I'm writing a basic computer program in which one of my requirements is to find the smallest pair of prime numbers that make up a Goldbach number (up to 9 digits long, non-inclusive). The user ...
4
votes
1answer
168 views

Primes of the form $\lfloor x^k\rfloor$

I'm looking for a result (embarrassingly enough, a somewhat famous result) which shows the infinitude in some sense I don't recall of primes of the form $$ \lfloor x^k\rfloor $$ for $k$ fixed and ...
4
votes
4answers
184 views

Another Congruence Proof

I've been asked to attempt a proof of the following congruence. It is found in a section of my textbook with Wilson's theorem and Fermat's Little theorem. I've pondered the problem for a while and ...
4
votes
2answers
467 views

Proving ${p-1 \choose k}\equiv (-1)^{k}\pmod{p}: p \in \mathbb{P}$ [duplicate]

Possible Duplicate: Prove $\binom{p-1}{k} \equiv (-1)^k\pmod p$ The question is as follows: Let $p$ be prime. Show that ${p \choose k}\bmod{p}=0$, for $0 \lt k \lt p,\space ...
2
votes
2answers
769 views

Product of all prime numbers upto some prime $p$

Let $p$ be a prime number. Denote by $P$ the set of all primes which are not greater than $p$. Is there a well known estimation of the product of all prime numbers in $P$ (i.e. $\prod_{q\in P}q$)?
2
votes
4answers
203 views

A good introduction to Prime Numbers

I'm looking for a good introduction to Primes Numbers, their properties, and some of the better known theorems concerning them. I would prefer references assume knowledge of undergraduate level real ...
7
votes
1answer
227 views

Is every natural number a prefix of a prime number? [duplicate]

Possible Duplicate: Proof that there are infinitely many prime numbers starting with a given digit string Let n be the representation of a natural number in a non-unary base. Is it a prefix ...
3
votes
2answers
130 views

Primes of the form $n\pm k$

Given some arbitrary natural number $n$, can we always find a $k$ such that $n+k$ and $n-k$ are both prime? Has there been any work on finding an upper bound for $k$?
0
votes
1answer
1k views
5
votes
2answers
497 views

Find the remainder when $ 12!^{14!} +1 $ is divided by $13$

Find the remainder when $ 12!^{14!} +1 $ is divided by $13$ I faced this problem in one of my recent exam. It is reminiscent of Wilson's theorem. So, I was convinced that $12! \equiv -1 \pmod {13} $ ...
2
votes
1answer
171 views

A prime conjecture

Let $n_k$ for $k=1,2,...,i$ be a finite sequence of positive integers, with $i>1$ and $n_1=0$. If there is a prime p such that for every positive integer m, one or more integers in {${(m+n_k)|1\leq ...
12
votes
1answer
501 views

The Goldbach Conjecture and Hardy-Littlewood Asymptotic

A source I am reading refers to the Goldbach conjecture (that every even number is the sum of two primes), and then immediately follows with the "Hardy-Littlewood conjecture" that $\sum ...
6
votes
1answer
120 views

Limit of ratios of numbers with $m$ factors and primes

This is my first question. Let $a_1, a_2,\ldots, a_k$ be natural numbers $\leq n$ with $m$ prime factors. Let $p_1, p_2, \ldots, p_r$ be the prime numbers $\leq n$. Let $$C_{m,n} = ...
8
votes
0answers
196 views

How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?

Is there an easy way to compute the following question: How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes? The only thing that ...
11
votes
2answers
278 views

The Fermat prime 257 and binomial sum $\sum_{n=0}^\infty \frac{(-1)^n}{\binom {8n}{4n}}$?

We have, $\begin{aligned} \sum_{n=0}^\infty \frac{(-1)^n}{\binom n{n/2}} &= \frac{4}{27}(9-\pi\sqrt{3}\,)\\[2.5mm] \sum_{n=0}^\infty \frac{(-1)^n}{\binom {2n}n} &= \frac{4}{5} - ...
3
votes
1answer
92 views

Exclusive prime factors

Let $S$ be an finite or infinite subset of the primes. Let $f(x)=1$ if $x$ has no factors in $S$. If not, $f(x)=0$. Is there a way to calculate the limit $\displaystyle\sum_{n=1}^{x} f(n)/x$, as $x$ ...
6
votes
1answer
298 views

Does this $\zeta(s)$ identity have a name?

I have generalized the product from this thread: Let $s=2n+1$ for $n\ge1$, $$\zeta (s)=\frac{\zeta (2 s)}{\zeta (2)} \prod _{n=1}^{\infty } \frac{\sum _{i=0}^{s-1}(-p_n){}^i}{(p_{n}-1)p_{n}^{s-2}}$$ ...
4
votes
0answers
406 views

sum of $n^{th}$ powers of prime factors of $x$

Starting with a positive integer $x$, find the sum of the $n^{th}$ powers of the prime factors of $x$, including multiplicities. Then find the sum of the $n^{th}$ prime factors of the result etc. ...
1
vote
1answer
65 views

Every number $2^N > 4$ can be expressed by the sum of 2 primes?

For example the first cases are: $2^3= 8 = 3+5$ $2^4= 16 = 3+13$ and so on ...
1
vote
1answer
47 views

Generating a number of a specific order

Here is what I have: select $p$ such that $p - 1$ has a large prime factor $t$: $p - 1 = tu$, where $u$ is a random number $n = p^2 q$, where $q$ is prime pick random $g < n$ and compute $g_p = ...
3
votes
1answer
360 views

Theorems about Mersenne numbers

The wiki page on Mersenne Primes gives 8 theorems about Mersenne primes. My question relates to number 4. and 7.: 4.If $p$ is an odd prime, then any prime $q$ that divides $2^p-1$ must be ...
1
vote
2answers
99 views

Primality test of quadratic polynomials

There are some quadratic polynomials like $n^2+1$ that there exist infinitely many integers $n$ such that their value is either prime or the product of two primes (if I am right!). I wanted to know if ...
3
votes
2answers
223 views

Find $X$, $a$ : ALL prime factors of $(X^a - 1)/(X - 1) < X$

where $X$ is an odd prime, and $a$ is an odd integer. For example, let $X = 37$, $a = 3$, we get $$\frac{37^3-1}{36} = 3 \times 7 \times 67.$$ When factoring numbers such as this, I've noticed that ...
2
votes
2answers
329 views

Is $n = k \cdot p^2 + 1$ necessarily prime if $2^k \not\equiv 1 \pmod{n}$ and $2^{n-1} \equiv 1 \pmod{n}$?

$p$ is an odd prime and $k$ is a positive integer. Let $n=k \cdot p^2+1$. If $2^k \not\equiv 1 \pmod n$ and $2^{n-1} \equiv 1 \pmod n$, is $n$ prime? If it is, why?
3
votes
1answer
146 views

Using Jacobi symbol: Is $(\frac{54}{77})=1$ solvable?

I can't understand what to do in the following example of congruence. I need to decide if this congruence is solvable, and if so, to find all the solutions:$x^2 \equiv 54(77)$. I need to decide ...
3
votes
0answers
166 views

Which starting conditions for the Fibonacci sequence, gives most primes

I found the following question (at http://aperiodical.com/2012/05/matt-parkers-twitter-puzzle-25-may/): If you start the Fibonacci sequence 2,1 instead of 1,1 do you get more or fewer primes? ...
2
votes
2answers
368 views

$(m, m+2)$ is twin prime, iff $4((m-1)! + 1) \equiv -m \pmod {m(m+2)}$

The Wiki page on Twin Primes says The pair $(m, m+2)$ is twin prime, iff $4((m-1)! + 1) \equiv -m \pmod {m(m+2)}$. This is obviously connected to Wilson's Theorem. Can anybody provide a proof ...
3
votes
3answers
473 views

Describing the primes $p$ for which the Legendre symbol $(\frac{-6}{p})=1$

I would love your help with describing the primes $p$ for which the Legendre symbol $(\frac{-6}{p})=1$. From the properties of the Legendre symbol I know that ...
0
votes
2answers
319 views

Prove that the order of an element in the group N is the lcm(order of the element in N's factors p and q)

How would you prove that $$\operatorname{ord}_N(\alpha) = \operatorname{lcm}(\operatorname{ord}_p(\alpha),\operatorname{ord}_q(\alpha))$$ where $N=pq$ ($p$ and $q$ are distinct primes) and $\alpha ...
8
votes
2answers
160 views

A problem about a sequence and prime factorization

A long time ago I solved the following theorem Let $p_1,p_2,\ldots,p_k$ be distinct primes. Let $\{a_i\}^\infty_{i=1}$ be the increasing sequence of positive integers whose prime factorization ...
1
vote
1answer
177 views

What are the generators for $\mathbb{Z}_p^*$ with p a safe prime?

lets consider $\mathbb{Z}_p^*$ with $p = 2 \cdot q + 1$ a safe prime ($p$ and $q$ have to be prime). Then $\varphi\left(p\right) = 2 \cdot q$ is the order of $\mathbb{Z}_p^*$, and ...
4
votes
1answer
426 views

Is there a simple way to prove Bertrand's postulate from the prime number theorem?

Is there a simple way to prove Bertrand's postulate from the prime number theorem? The prime number theorem immediately implies Bertrand's postulate for sufficiently large $n$, but it fails to ...
2
votes
1answer
549 views

How to find the factors of numbers around 1e7?

I don't have a maths background but I'm solving problems on the awesome Project Euler .net in JavaScript as programming practice. I don't want to link directly to the question or post it verbatim ...
6
votes
3answers
2k views

What is the most efficient algorithm to find the closest prime less than a given number $n$

Problem Given a number n, $2 \leq n \leq 2^{63}$. $n$ could be prime itself. Find the a prime $p$ that is closet to $n$. Using the fact that for all prime $p$, $p > 2$, $p$ is odd and $p$ is of ...
2
votes
2answers
150 views

Minimum set of US coins to count each prime number less than 100

Say I wanted to be able to carry enough coins in my pocket such that at any time, I could count out exact change totaling any of the prime numbers less than 100. How would I determine the minimum set ...
7
votes
2answers
315 views

Question regarding Von-Mangoldt function.

Let $\psi(x) := \sum_{n\leq x} \Lambda(n)$ where $\Lambda(n)$ is the Von-Mangoldt function. I want to show that if $$ \lim_{x \rightarrow \infty} \frac{\psi(x)}{x} =1 $$ then also $$\lim_{x\rightarrow ...
5
votes
5answers
797 views

Is it possible to get 1/3 without dividing by 3?

So I need to divide a rectangle into 3 equals parts, but without fractions. It's one of those old "You have two jars of two sizes and need to get an exact amount of some other size" type problems, ...
14
votes
1answer
458 views

Is it possible to assign a value to the sum of primes?

It is possible, by means of zeta function regularization and the Ramanujan summation method, to assign a finite value to the sum of the natural numbers (here $n \to \infty $) : $$ 1 + 2 + 3 + 4 + ...
5
votes
4answers
341 views

Does this polynomial evaluate to prime number whenever $x$ is a natural number?

I am trying to prove or disprove following statment: $x^2-31x+257$ evaluates to a prime number whenever $x$ is a natural number. First of all, I realized that we can't factorize this ...
9
votes
3answers
1k views

Cyclic numbers are characterized by the reciprocals of full reptend primes?

The number $142,857$ is widely known as a cyclic number, meaning consecutive multiples are cyclic permutations, i.e. $1 × 142,857 = 142,857$ $2 × 142,857 = 285,714$ $3 × 142,857 = ...
0
votes
1answer
158 views

Value $\Phi_n(1)$ of the cyclotomic polynomial at x=1 [duplicate]

Possible Duplicate: Value of cyclotomic polynomial evaluated at 1 I have to show $\Phi_n(1)=1$ for $n\neq p^k$ with $p$ is prime. (I already proved to easy part $\Phi_n(1)=p$ for $n=p^k$) ...
0
votes
2answers
259 views

Name for prime numbers with only prime digits?

I'm wondering, is there a name for a prime number where all digits are also prime? Some examples: 37, 53, 3253, 5573, 23753. I've been calling them 'double primes', but I doubt that's the correct ...
4
votes
2answers
286 views

Counting Functions or Asymptotic Densities for Subsets of k-almost Primes

This question is an extension of this question. There the asymptotic density of k-almost primes was asked. By subsets I mean the following: Let $\lambda$ be a partition of $k$ and $P_{\lambda}=\{ ...
3
votes
1answer
192 views

Check for prime

I know there are a lot of questions on this board about finding prime numbers, and I've gone through a bunch of them. I even came across this interesting site about primes: ...
2
votes
2answers
346 views

Question on (Semi) Prime Counting Functions

I'm looking for a function counting all numbers, let's call them power semi-primes for the moment, of the form $a^nb^m\leq t$. $a,b$ are primes and might be equal. Edit: $n$ and $m$ are fixed. I ...
0
votes
1answer
630 views

Euler's sieve and wheel factorization

http://burntjet.co.uk/maths/primes/sieves.php#eq_sieve_div I have read that Sieve of Eratosthenes algorithm can be speeded up with wheel factorization. Can similar be done with Euler's sieve (while ...
2
votes
1answer
303 views

Primitive roots and the Chinese remainder theorem

I'm going over some past papers and have been able to show that if $p$, $q$ are distinct odd primes and $\gcd (a, pq)=1$ then $a^{\operatorname{lcm}(p-1,q-1)} \equiv 1 \pmod {pq}$ the next part says ...
9
votes
5answers
3k views

Why do we consider prime numbers important, and what are their applications other than number theory in pure math?

Why do we consider prime numbers important, and what are their applications other than number theory in pure math? I know that Number theory is devoted to studying prime numbers, but there must be ...
14
votes
3answers
509 views

Are the logarithms in number theory natural?

I find the frequent emergence of logarithms and even nested logarithms in number theory, especially the prime number counting business, somewhat unsettling. What is the reason for them? Has it maybe ...
4
votes
1answer
491 views

Non-linear Recursion

I'm trying to prove (or disprove and improve if possible) that the sequence $a_{n+1}=\frac{a_n^2+1}{2}$, where $a_0$ is an odd number greater than 1 contains an infinite number of primes. However, I ...