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
1answer
108 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) ...
3
votes
3answers
99 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
51 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!
2
votes
5answers
61 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: ...
5
votes
1answer
204 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 ...
1
vote
1answer
43 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 ...
1
vote
2answers
56 views

Polynomials mod prime $p$

The problem is $5m^2+m+4 \equiv 0\pmod 7$. I am supposed to first convert it to a quadratic whose first coefficient is $1$. But the polynomial cannot be factored, so I am unsure as to how to do ...
0
votes
1answer
57 views

Erdős Prime Sieve Conjecture

I think this is/was an Erdős conjecture. I can't find it, or see how to prove it. We know all primes but a finite number can be expressed as $6k\pm1$. If we have a finite set of moduli using ...
2
votes
2answers
69 views

Determine if $n$ is prime?

If $n < 10^6$ and no integer between $1$ and $10^4$ divides $n$. Is n prime? Here is my attempt: Assume $n$ is prime. Then using trial division, $n$ must be divisible by an integer between $1$ ...
2
votes
0answers
17 views

Solution to a set of number theoretic constraints

I'm trying to prove a graph theoretic lemma for my research; I need to construct graph homomorphisms between some delicately defined graphs. I believe I can do this if (and maybe only if) I can find ...
4
votes
1answer
47 views

Quadratic bound for prime numbers

I once found the following problem meant to be solved at high-school level (some olympiad-level exercise, I guess), and I have never been able to prove it using elementary methods. Does anybody know a ...
0
votes
1answer
26 views

Convergence behavior of $\sum_p \frac{1}{p \log p}$ and generalization.

The harmonic series $$\sum_{n\in\mathbb N} \frac{1}{n}$$ is well known to be divergent. Using Cauchy condensation test one immediately sees that even $$\sum_{n\in\mathbb N} \frac{1}{n\log n}$$ is ...
2
votes
2answers
43 views

If p and q are prime which elements are in the subgroup? (GRE question)

I was just doing some practice problems in my abstract algebra book trying to get a warm up this morning, but I found a GRE problem in the problem set and I don't know how to solve it. I've tried to ...
-4
votes
0answers
35 views

Number Theory questions [duplicate]

Let $a$ be an integer and $n$ a positive integer. Prove or provide a counter example to each of the following statements. (a) If $a$ ≡ ± 1(mod p) for all primes $p$ dividing $n$, then $a^2$ ≡ 1(mod ...
4
votes
1answer
112 views

Elementary proof for $\sqrt{p_{n+1}} \notin \mathbb{Q}(\sqrt{p_1}, \sqrt{p_2}, \ldots, \sqrt{p_n})$ where $p_i$ are different prime numbers.

Take $p_1, p_2, \ldots, p_n, p_{n+1}$ be $n+1$ prime numbers in $\mathbb{P} \subseteq \mathbb{N}$. $\sqrt{p_{n+1}} \notin \mathbb{Q}(\sqrt{p_1}, \sqrt{p_2}, \ldots, \sqrt{p_n})$ seems to be quite ...
1
vote
1answer
49 views

Is $p\in\big\{x,…,2x\big\}$ lower-bounding $p\in\big\{x^2,…,(x+1)^2\big\}$?

Is it overreaching or erroneous to consider that possibility? (Alas, I'm not a mathematician, and don't have rigorous language to talk about this.) What I want to say is: Given any even span of ...
0
votes
1answer
20 views

$\sum_{n=2}^{\infty}[\log{(\log{(p_{n+1})})} - \log{(\log{(p_n)})}] - \frac{1}{p_{n+1}} = C$?

With $p_n$ prime, does the constant, $C$, exist and have a name? $$\sum_{n=1}^{\infty}[\log{(\log{(p_{n+1})})} - \log{(\log{(p_n)})}] - \frac{1}{p_n} = C$$ If not,how about a constant and function ...
-3
votes
2answers
42 views

Proof of infinite primes [on hold]

Recently , I was going through some Euclid's Lemma and I read Euclid's Proof for infinite Prime . When I read it , I found it amazing. But then thinking of How to prove it in other ways .I came to ...
7
votes
2answers
161 views

What percentage of numbers is divisible by the set of twin primes?

What percentage of numbers is divisible by the set of twin primes $\{3,5,7,11,13,17,19,29,31\dots\}$ as $N\rightarrow \infty?$ Clarification Taking the first twin prime and creating a set out of its ...
9
votes
1answer
77 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 ...
1
vote
1answer
23 views

Is there exist $n_p\in\mathbb{N}$ such that $p+1\equiv 0 \mod (4n_p-p)$ for prime $p(\ge 5)$?

I am looking a proof for, Existence of a positive integer $n_p$ such that $$p+1\equiv 0 \mod (4n_p-p) $$ for each prime $p\ge 5.$ But I have no idea to get an attempt to this problem in general. ...
0
votes
1answer
21 views

Consecutive terms which are all prime numbers but are also in AP

Let $a_1,a_2,a_3,\cdots$ be in AP with a common difference which is not a multiple of $3$.The maximum number of consecutive terms which are in AP and are also prime numbers is? I thought the answer ...
3
votes
0answers
63 views

How prove $\sigma(4^p-1)<(2^{p+1}-1)^2$

If $p$ is an odd prime numbers, show that $$\sigma(4^p-1)<(2^{p+1}-1)^2$$ where $\sigma(n)$ stands for the sum of divisors. I thought of using the formula for $\sigma(n)$: If ...
1
vote
0answers
40 views

Comparative prime number theory with a small tweak

Fix $a, k \in \mathbb{N}$ relatively prime. For $x \in \mathbb{R}$ recall the function $$ \pi(x; k, a) = \sum_{\substack{p \leq x \\ p \equiv a \pmod{k}} } 1 $$ where $p$ denotes the primes. ...
2
votes
1answer
21 views

Logarithm of the n'th prime.

Let $P_n$ denote the n'th prime number. How could we conclude the following from the prime number theorem? $$ \log(P_n)=\log n + \log\log n + o(1) $$ Maybe by showing that $P_n=An\log n $ for a ...
4
votes
3answers
82 views

Find $55! \bmod 61$

I am asked to find the smallest positive $x$ such that $x \equiv 55! \pmod{61}$. This invokes Wilson's theorem where $(p-1)! \equiv -1 \pmod p$. This means $60! \equiv -1 \pmod{61}$. But where to ...
4
votes
1answer
48 views

$A$ is a sum of two postive integer squares?

if $x,y,z,w$ be postive integer,and such $x^2+y^2$ is prime number,and $A=\dfrac{w^2+z^2}{x^2+y^2}\in N^{+}$ show that $A$ is a sum of two postive integer squares? maybe ...
6
votes
1answer
170 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$ ...
6
votes
2answers
249 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, ...
-2
votes
3answers
311 views

Goldbach's conjecture is wrong?! [closed]

I apologize for this very unprofessional post, but I have a lot of obligations and just I did not found the time to nicely format "my theory".I've been thinking about Goldbach hypothesis and maybe I ...
-1
votes
0answers
603 views

$ (x+y) \geq (p_n +2) $?

I recently worked on a previous idea of mine (a prime number inequality, which I had posted in this community but didn't know Latex then and couldn't discuss it's proof). I was wondering how powerful ...
5
votes
3answers
190 views

How do we identify twin primes .

as known , each prime number greater than 3 is of the form $6k-1$ or $6k+1$ . twin primes are all sort of two adjacent primes of difference $= 2$ as: $$(11,13) ,(17,19),\ldots,(6k-1,6k+1)$$ -Is ...
1
vote
3answers
49 views

How can i solve this diophantine equation:$x^2-(6p-4q)x+3pq=0$?

I found this diophantine equation $$x^2-(6p-4q)x+3pq=0$$ (p and q both prime numbers) and i posted my answer but i want to know if there are other methods to find the solutions of this equation. What ...
2
votes
1answer
83 views

A generalization of Goldbach's conjecture?

In a previous question I asked about a counterexample for an observation I did about the Goldbach's comet: it seems that there is always common prime shared between the Goldbach's prime pairs of the ...
1
vote
0answers
40 views

Is there a standard notation for the sequence of sorted exponents in the prime power factorization of a number?

Given some $n \in \mathbb{N}$, is there a name or notation for any/all of the following? The set of all factors $F(n)$ of $n$ (including 1 and $n$). The ascending sequence of non-unique prime ...
3
votes
2answers
52 views

Solving the diophantine equation $p^2+n-3=6^n+n^6$

What are the pairs ($p,n$) of non-negative integers where $p$ is a prime number, such that $$p^2+n-3=6^n+n^6$$ How can I solve this diophantine equation?
2
votes
2answers
56 views

Coprime numbers - Need help with proof

Let $a \in \mathbb{Z}$ be an odd number. Prove that the numbers $$a^{2^n} + 2^{2^n}, a^{2^m} + 2^{2^m}$$ are relatively prime (coprime) for all $m.n\in\mathbb{Z}^+$ $(m\neq n)$. Any tipps?
4
votes
1answer
58 views

How many values of $k$ satisfy $\left (\frac{k}{p}\right )=\left (\frac{k+1}{p}\right)=1$ where p is a odd prime?

The values of $k$ must be between $1$ and $p-1$ this means : $$k\in\left\{1,2,\cdots,p-1\right\}$$ The question: Given an odd prime $p$ What is the number of elements ...
2
votes
1answer
27 views

A question about step in the proof of Selberg's formula

Recently I've found the following paper, discussing and proving Selberg's symmetry formula: http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Balady.pdf My question concerns proofs of ...
27
votes
2answers
519 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$. ...
0
votes
1answer
37 views

change the order of the digits of a prime number

What is prime numbers called, that if you arbitrary change the order of its digits, you will only get another prime number. For example 79 (79 is prime number as well 97) or 199 (199, 919, 991 is ...
2
votes
2answers
52 views

If $n$ is a positive integer such that $2^n+n^2$ is a prime number , then is it true that $6|n-3$ ?

If $n$ is a positive integer such that $2^n+n^2$ is a prime number , then is it true that $6|n-3$ ? Trivially $n$ cannot be even , so this leaves us only with the possibilities $n \equiv1,3,5( \mod 6) ...
0
votes
1answer
19 views

Relation between LCM of terms of sequence with sum of sequence

Is there any relation between LCM of some arbitrary sequence and sum of elements of sequence ? How to find the LCM if only sequence sum is given in short time ?
0
votes
0answers
26 views

How to get a prime $p$ such that $kp$ for any $k \in \mathbb{Z}$ does not equal to $ar - b$ where $r,b$ given and $a \in \mathbb{Z}$

Suppose that $R$ is a finite set of positive natural numbers given. Let $r \in R$. $b$ is the product of numbers in $R$. We want to select a prime $p$ such that for every $r$, $ar - b \neq kp$ where ...
2
votes
1answer
72 views

How does $\sum p(k)$ grow asymptotically where $p(k)$ is the smallest prime factor of $k$?

Define $p(k)$ to be the smallest prime $p$ dividing $k$. Define $A(n)=\sum_{k=2}^n p(k)$. How does $A(n)$ grow asymptotically? I am wondering how exactly the naive algorithm for finding all primes ...
3
votes
1answer
40 views

Prove about prime numbers obtained from certain sums of squares of an integer $n$

I would like to ask for a prove about an observation I did regarding the sums of squares and prime numbers (in another question here), or a counterexample of it. My capabilities to do this kind of ...
10
votes
1answer
75 views

Is there a natural number for which all the sums and differences of its factor pairs are prime?

The 8 factor pairs of e.g. 462 are $((1, 462), (2, 231), (3, 154), (6, 77), (7, 66), (11, 42), (14, 33), (21, 22))$. Of the 16 non-negative integers which are the sums and differences of these pairs ...
0
votes
1answer
23 views

Vanishing property of logarithmic derivative of zeta function

I was trying to derive the explicit formula for the integrated Chebyshev $\psi$ function, $\psi_1$ defined as \begin{equation}\psi_1(x)=\int_1^x\psi(y)dy\end{equation} But I have stumbled upon one ...
-2
votes
2answers
83 views

How to check if $2$ is a square $\mod 3$?

I don't think I can use the Legendre or Jacobi symbol here because $2$ is an even prime. I'm not sure I've learned methods to deal with $2$ even though I know how to use quadratic reciprocity, it only ...
1
vote
2answers
64 views

Number of distinct prime divisors of an integer $n$ is $O(\log n/\log\log n)$

I strongly believe that the claim is true; but I'm neither a mathematician nor speaking French and hope that somebody can confirm it, since related questions (here, here and here) either don't have an ...