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

the sum of the reciprocals of the primes

The sum of the reciprocals of the primes is $\sum \limits_{p}\frac{1}{p} \approx N \ln\ln(N)$ what about this sum where $p_{3}=3,p_{5}=5,p_{n}=\sum \limits^{N}_{j=5}\frac{1}{p_{j}} \sum ...
10
votes
1answer
244 views

Is this olympiad-like question about remainders an open problem?

Suppose that we are given two positive integers $x$ and $y$ such that $$x \mod p \leqslant y \mod p$$ for each prime number $p$. (Here, $x \mod p,\; y \mod p$ stand for the least non-negative ...
2
votes
5answers
65 views

Possible solutions of a diophantine equation: $p^2+pq+275p+10q=2008$

What are couples of prime integers that verify this diophantine equation: $$p^2+pq+275p+10q=2008?$$ I tried to solve this equation trough the rules of modular-arithmetic. I rewrite the equation as: ...
0
votes
2answers
45 views

Congruence for Stirling Number of first kind $s(n,k)$ when $n$ is prime

Let $s(n,k)$ be the Stirling numbers of first kind: $$\prod_{k=0}^{k=n-1}(x-k) =\sum_{k=0}^{k=n}s(n,k)x^k$$ $p$ is prime $\iff$ for all $k\in\{2,..,p-1\}$, $s(p,k)\equiv0\ mod\ p $ How ...
0
votes
1answer
60 views

Prove that for all $n\in \mathbb N$ $(n>1)$ the number $n^4+4^n$ is not prime. [duplicate]

Prove that for all $n\in\mathbb N$ $(n>1)$ the number $n^4+4^n$ is not prime. Can someone give me some pointers?
4
votes
0answers
33 views

Squarefree products of a class of primes

Numbers which are the sum of two squares are the product of a square and a collection of distinct primes which are 1 or 2 mod 4. Landau proved that there are $\sim kx/\sqrt{\log x}$ such numbers up ...
5
votes
3answers
72 views

Show that $\sum\limits_{p \leqslant x}1/p = \frac{\pi(x)}{x} + \int_2^x \frac{\pi(u)}{u^2} du.$

Show that $$\displaystyle\sum\limits_{p \leqslant x}1/p = \dfrac{\pi(x)}{x} + \int_2^x \dfrac{\pi(u)}{u^2} du.$$ In the equation above, $\pi(x)$ denotes the prime counting function. To get ...
0
votes
0answers
27 views

Prove that If $p$ is an odd prime, then any divisor of the Mersenne number $M_p = 2^p − 1$ is of the form $2kp + 1$

For example, $M_{11} = (2 · 1 · 11 + 1)(2 · 4 · 11 + 1)$ If $q$ is a prime divisor of $M_p$ then $\exists k \in Z$ such that $qk = 2^p-1$. Now $ord(2,q)$ is the smallest positive integer $a$ such ...
23
votes
2answers
1k views

What is the millionth decimal digit of the $ 10^{10^{10^{10}}} $-th prime?

What is the millionth decimal digit of the $10^{10^{10^{10}}}$th prime? (This prime, with more than $10^{10^{10}}$ decimal digits, is far larger than the largest "known" prime.) The answer should ...
0
votes
0answers
25 views

Motivation for $r$ in AKS Primality Test

I've been reading up on the AKS primality test, and I understand the big ideas and proofs as they are pretty elementary number theory. I am confused about how to value of $r$ is selected. In the ...
0
votes
1answer
40 views

Does there exist an integer $s$ such that every integer $> 1$ can be written as a sum of at most $s$ primes?

Does there exist an integer $s$ such that every integer $> 1$ can be written as a sum of at most $s$ primes ?
1
vote
1answer
33 views

If equation has integer solution it has solution for every prime p.

How to prove that if the equation in the form: $a_0 x_0^2 + a_1 x_1^2 + \dots + a_nx_n^2 = 0$ where $a_0, a_1, \dots , a_n \in \mathbb{Z}$, has an integer solution, then it has solution in ...
-2
votes
1answer
98 views

Is the p'th root of a prime number p times p always prime in $\mathbb{N}$? [closed]

I've been thinking about this problem for very long: Is the p'th root of a prime number p times p(if it is in $\mathbb{N}$) always prime in $\mathbb{N}$?
3
votes
3answers
100 views

Prove there exists $m > 2010$ such that $f(m)$ is not prime

Let $$f(x) = \sum_{i = 0}^n a_ix^i$$ be a polynomial with $a_i \in \mathbb Z, n > 0, a_n \neq 0$. Prove that there exists some natural number $m>2010$ such that $|f(m)|$ is not a prime number. ...
0
votes
1answer
27 views

A question in Number Theory - prove there exist m>2010 s.t f(m) is not prime [duplicate]

Let $$f(x)=\sum_{i=0}^n a_nx^n$$ be a polynomial with $$a_n \in Z,n>0,a_n\neq0$$ Prove that there exists some natural number $$m>2010$$ such that $$|f(m)|$$ is not a prime number. I tried to ...
0
votes
1answer
38 views

A question about primes, number theory [duplicate]

I tried to solve this question but without a success: Let $p$ be a prime number,and $p^2+2$ is also prime, prove that $p=3$. I tried to show $p^2+2$ as a product of numbers and then to show that ...
2
votes
1answer
26 views

Determine if n is a prime.

Let $n$ be a positive natural number. You know the following facts about $n$ . Firstly, $n<10^{6}$ . Moreover, not a single integer $k$ between $1$ and $10^{4}$ divides $n$ . Does it ...
0
votes
0answers
204 views

$\pi(z)-\omega(z-1)-\{-1,0,1\}= \pi(2z-1)- \pi(z)$ when $z(z-1)$ is divisible by all primes ${<}\sqrt{z}$

I have encountered the below problem: Given $z(z-1)$ divisible by all primes ${<}\sqrt{z}$ (and the prime factors of $z(z-1)$ are consecutive primes), prove (or disprove) ...
1
vote
0answers
37 views

Marking Integers Using a Wheel

Suppose I had a wheel of diameter one meter and I was charged with marking every meter along an infinite stretch of a beach. The strategy is to insert pegs into the wheel so that every point that is a ...
1
vote
1answer
26 views

Is it possible to estimate the number of primes between 0 and a 128 bit number?

I'm attempting to visualize an RSA public/private key pair, or a SHA2 hash. In order to reduce that massive number that is meaningful to humans I'm looking at this SHA2 visualization function to ...
0
votes
1answer
39 views

Is n a prime if $n\in\mathbb{N}$, $n<10^{6}$ and $1<k<n$, $k\nmid n$

Can I get hints on how I can explain this? Question Let $n$ be a positive natural number. You know the following facts about $n$. Firstly, $n<10^{6}$. Moreover, not a single integer $k$ between ...
1
vote
1answer
60 views

Show that $\limsup_{x \to \infty} \frac{\pi(x)}{x/ \log x} \geqslant 1. $

Show that $$\displaystyle\limsup_{x \to \infty} \dfrac{\pi(x)}{x/ \log x} \geqslant 1. $$ I've seen $\displaystyle\lim_{x \to \infty}$ operator, but I haven't seen $\displaystyle\limsup_{x \to ...
2
votes
0answers
190 views

Numbers $717, 71717, 7171717,\dots$ and primality

Prove or disprove that all numbers $717, 71717, 7171717,\dots$ are composite. This is related to this question. $\begin{array}\\ 717 &= \text{div by 3}\\ \color{blue}{71717} &= 29\cdot ...
6
votes
1answer
181 views

Conjectured Primality Test for $N=8\cdot 3^n-1$

Definition 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)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=8\cdot 3^n-1$ ...
4
votes
1answer
112 views

Sequence with Prime Numbers

I was looking a question in a calculus book which used the following steps to show that following sequence has a limit (called Euler's constant $\gamma$): $$t_n = \sum_{i=1}^n\left(\frac{1}{n}\right) ...
1
vote
2answers
51 views

When is $n\choose k$ a multiple of $n$

While working through a question, the solution states that in the finite field $\mathbb{F}_p$ for $p$ prime, we have $(u+v)^p=u^p + v^p$ and since $(u+v)^p={p\choose 0}u^pv^0+{p\choose ...
1
vote
2answers
75 views

Show that 2 is a prime in the ring $\mathbb{Z}\left[\frac{-1 + \sqrt{-3}}2\right]$

My progress: Let's take $a \in \mathbb{Z}\left[\frac{-1 + \sqrt{-3}}2\right]$ such that $a \mid 2$, and function $l(x) = x \bar x$. $a \mid 2$ $\Rightarrow$ $2 = ab$ $\Rightarrow$ $l(ab) = l(a)l(b) ...
4
votes
2answers
162 views

Find prime factorization in the ring $\mathbb{Z}\left[\frac{-1 + \sqrt{3}}{2}\right]$

Find prime factorization of the number $13$ in the ring $\mathbb{Z}\left[\frac{-1 + \sqrt{3}}{2}\right]$ My progress: Let $w = \frac{-1 + \sqrt{3}}{2}$ and let $N(z) = z \bar z$ be the norm ...
0
votes
0answers
27 views

the asymptotic approximation of a sum

$p_{n}$ and $p_{j}$ are two primes with $p_{n}<p_{j}$ where the $n$ and $j$ denotes the $n$th and the $j$th prime. I have this sum $$\sum \limits^{k=\frac{b-p^{2}_{n}p_{j}}{2p_{n}p_{j}} ...
9
votes
3answers
272 views

For what $t$ does $\lim\limits_{n \to \infty} \frac{1}{n^t} \sum\limits_{k=1}^n \text{prime}(k)$ converge?

The average of all primes is $$\lim\limits_{n \to \infty} \frac{1}{n} \sum_{k=1}^{n} \text{prime}(k) ,$$ which diverges. What is the smallest $r$ such that for $t>r$, $$\lim_{n \to \infty} ...
1
vote
1answer
46 views

Euler's Totient function $\forall n\ge3$, if $(n-\phi(n)) = \sqrt{n}\ $,$\ $then $(n-\phi(n)) \in \Bbb P$

Recently I opened a question about what it might be a new property of Euler's Totient function. I am still studying the Totient function and I found another interesting relationship, it is very ...
3
votes
1answer
38 views

Product Divisors of 2 integers

If $x$ is a positive integer, and $y$ is a positive integer, can the product of the divisors of $x$ equal the product of the divisors of $y$ for some arbitrary $x$ and $y$? (the product of the ...
9
votes
1answer
84 views

Solving a Diophantine equation: $p^n+144=m^2$

I found this Diophantine equation: $$p^n+144=m^2$$ where $m$ and $n$ are integers and $p$ is a prime number. I solved it but I want to know if there exist other proofs through the use of rules of ...
5
votes
1answer
208 views

Heuristic explanation for oscillatory behavior of first $n$ primes' multiples

Let $A$ be the set of all multiples of the first $n$ primes. The asymptotic density of $A$ should be given by $\mu=1-\prod_{i=1}^n(1-1/p_i)$. Letting $a_k$ be the $k$th element of $A$, the function ...
8
votes
3answers
1k views

How to show $p_n$ $\leq$ $2^{2^n}$?

Let $p_n$ be the $n_{th}$ prime (e.g. $p_1 = 2$; $p_2 = 3$; $p_3 = 5$). Show that $p_n \leq 2^{2^n}$ for all $n$. I don't see how I can approximate the value of $p_n$. Do I need something like ...
64
votes
10answers
3k views

Why 1 is not considered to be a prime number?

Why $1$ is not considered to be a prime number? Or why definition of prime numbers is given for integers greater than $1$?
6
votes
1answer
250 views

Does $19,199,1999,\dotsc$ contain infinitely many prime numbers?

Are there infinitely many primes of the form $F_n =2\times10^n-1$? That is, does this sequence, $$19,199,1999,\dotsc$$ contain infinitely many prime numbers? I think about Dirichlet's theorem on ...
0
votes
1answer
43 views

Number of solutions of the congruence $x^p \equiv x\pmod p$

How do I show that $x^p \equiv x\pmod p$ has precisely $p$ solutions? I can use Lagrange's theorem and Fermat's little theorem.
1
vote
0answers
19 views

Is there a standard notation for $(p_i-k)(p_{i-1}-k)(p_{i-2}-k)\cdots$ where $k$ is a small positive integer

For $k=0$, there is: $p_i\# = (p_i)(p_{i-1})(p_{i-2})\cdots(5)(3)(2)$ For $k=1$, there is: $\varphi(p_i\#) = (p_i-1)(p_{i-1}-1)(p_{i-2}-1)\cdots(5-1)(3-1)(2-1)$ Is there any other notation that ...
3
votes
2answers
89 views

Let $u_{n+3} = u_n + 2u_{n+1}$ . Show that $p$ divides $u_p$ for all $p$ prime number.

Let $(u_n)$ a sequence such that $u_0 = 3$, $u_1 = 0$, $u_2 = 4$ and $u_{n+3} = u_n + 2u_{n+1}$ Show that $p$ divides $u_p$ for all $p$ prime number. I'm really stuck on this exercise, ...
6
votes
1answer
43 views

Are there infinitely many Smarandache-Wellin primes and does anyone care?

Definition: The $n$th Smarandache-Wellin number in base $m$, denoted $S_n^m$ (or just $S_n$ for $m=10$), is the concatenation of the first $n$ base-$m$ primes. So, for example, we would have $S_4 = ...
27
votes
2answers
527 views

Prove that $\frac{a^n-1}{b^n-1}$ and $\frac{a^{n+1}-1}{b^{n+1}-1}$ can't both be prime.

Prove that $$\frac{a^n-1}{b^n-1} \ \text{and} \ \frac{a^{n+1}-1}{b^{n+1}-1}$$ cannot both be prime ($a>b>1,n\ge 2$). Clearly $(a^n-1,a^{n+1}-1)=a-1$ and $(b^n-1,b^{n+1}-1)=b-1$. ...
61
votes
4answers
4k views

$x$, $y$, $x+y$ and $x-y$ are prime numbers. What is their sum?

Here is the question: The $x$, $y$, $x−y$ and $x+y$ are all positive prime integers. What is the sum of all the four integers? Well, I just put some values and I got the answer. $x=5$, $y=2$, ...
5
votes
3answers
2k views

Is the cube root of a prime number rational?

The question is: if $P$ is prime, is $P^{1/3}$ rational? I have been able to prove that if $P$ is prime then the square root of $P$ isn't rational (by contradiction) how would I go about the cube ...
2
votes
2answers
43 views

Number Theory Primitive Roots Confusion

The following theorem is in my lecture notes: If p is a prime number, then there exist φ(p-1) distinct primitive roots modulo p. I am struggling to make sense of this. φ(m) is the number of ...
1
vote
3answers
199 views

Convergence of series involving the prime numbers

Given the serie $A=\sum\limits_{n=1}^{+\infty}\frac{p_n}{p_{n+1}}$ and $B=\sum\limits_{n=1}^{+\infty}\frac{p_{2n}}{p_{2n+1}}$, where $p_n$ is the sequence where the nth number are the nth prime ...
3
votes
3answers
105 views

Find all prime numbers of the form $n^2 + 4n$

Question: Find all the prime numbers of the form $n^2 + 4n$. List of the primes of this form and prove these are all such primes. My Answer I'm not really good at this but I made an attempt. $$n^2 ...
0
votes
2answers
54 views

Prove or disprove: There exists a prime p > 3 such that p + 2 and p + 4 are also prime

I'm having a lot of difficulties with this proof. Can someone please solve it and explain to me what's going on at each step? Thank you!
6
votes
2answers
258 views

RH would follow from $\displaystyle \frac{p_{n+1}}{p_{n+1}-1}<\frac{\log\log N_{n+1}}{\log\log N_n} $ for all $n>1$; what is my mistake?

Let $N_n=\prod_{k=1}^np_k$ be the primorial of order $n$,$\gamma$ be the Euler-Mascheroni constant and $\varphi$ denote the Euler phi function. Nicolas showed that if the Riemann Hypothesis is true, ...
1
vote
1answer
44 views

Congruence mod $p$

I need a proof for the following: Suppose that $p$ is an odd prime. If $(a, p) = 1$, then $x^2 = a \pmod p$ either has exactly $2$ solutions or has no solutions within $\textrm{crs}/p$. I can come ...