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

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 ...
7
votes
2answers
165 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
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 ...
1
vote
1answer
26 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
22 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
64 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
45 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
26 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
86 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
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$ ...
6
votes
2answers
257 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, ...
-3
votes
3answers
343 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 ...
5
votes
3answers
214 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
51 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
89 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
45 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 ...
4
votes
2answers
55 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
60 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
60 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
29 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
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$. ...
0
votes
1answer
40 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
54 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
21 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
42 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
30 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
88 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
82 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 ...
1
vote
3answers
128 views

Solve $x^p + y^p = p^z$ when $p$ is prime

Find the solutions in positive integers of $x^p + y^p = p^z$, where $p$ is a prime number. Particular case $p=2$: For $z=0$ there are no solutions. For $z=1$ the only solution is $x=y=1$. For ...
-1
votes
1answer
50 views

find a formula for $S(n)$ [closed]

Let $S(n) =\sum\tau(d)\sigma^2(d)$, where the sum is taken over all divisors $d$ of $n$. How to find a formula for $S(n)$ in terms of the prime factorization of $n$?
0
votes
0answers
24 views

Estimating the number of integers in a sequence of consecutive integers that are relatively prime to a given primorial

Let $x,y$ be positive integers and $p$ a prime. Is there a standard way to estimate the number of integers $z$ where $x \le z < x+y$ and $\gcd(z,p\#)=1$ For example, for $x=1000, y=30, p=7$, ...
0
votes
0answers
55 views

Why is $0$ the $0^\text{th}$ prime?

I found this question on $\prod_{n\to \infty}(1-1/p_n)$, played a little at Wolfram's Alpha and found the following: The series expansion of a related indefinite integral $\int \log (1-1/p_n)dn$ gave ...
5
votes
7answers
322 views

If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
0
votes
1answer
55 views

Prove that a is a primitive root mod p if and only if -a has order (p-1)/2

Consider a prime p $\in\mathbb{N}$ of the form 4t+3, with t $\in\mathbb{N}$. Prove that a$\in\mathbb{Z}$ is a primitive root mod p if and only if -a has order $\frac{(p-1)}{2}$. I showed most of the ...
1
vote
1answer
38 views

Is there numerical evidence supporting the predicted density of the primes of the form $x^2+1$?

A famous conjecture (due I think to Hardy and Littlewood) states that if $P(x)$ denotes the number of primes of the form $n^2+1$ less than or equal to $x$, then $$P(x)\sim \frac{C\sqrt x}{\log x}$$ ...
1
vote
2answers
47 views

Show that the sum of the products in pairs of the number 1,2,3…p-1 is divisible by p, where p is prime

If $p ≥ 5$ is prime, show that the sum of the products in pairs of the numbers $1, 2, . . . , p−1$ is divisble by p. We do not count $1×1$, and $1 × 2$ precludes $2 × 1$.
3
votes
2answers
70 views

Number theory question about primes

I have a really interesting (and hard) number theory task: Prove, that every $p$ prime has a multiple(not $0$), which is smaller than $\frac{p^4}{4}$, and it can be written down as the sum of five ...
0
votes
1answer
31 views

Proof about prime numbers [duplicate]

Show that if $n$ is composite then there exists a prime $p \leq n^\frac{1}{2}$ such that $p\mid n$. I would like to use contradiction to prove this claim but I'm not sure about how I should ...
0
votes
1answer
65 views

all elements of ($Z$/p$Z$)* are cubes

Let $p$ be a prime An element $a \in$ ($Z$/p$Z$)* is called a cube if there exists $b \in$ ($Z$/p$Z$)* such that $a = b^3$ How to show that all elements of ($Z$/p$Z$)* are cubes ? And if $p \equiv ...
1
vote
2answers
66 views

Form of a prime dividing a certain difference of two prime powers.

Let $p$ and $q$ be odd primes. If $q|(a^p-1)$ then, either $q|(a-1)$ or $q=(2rp+1)$ for some integer $r$.
0
votes
1answer
72 views

Product of Distinct Primitive roots

Let $p$ be an odd prime. Show that the product of the distinct primitive roots, $\mod{p}$, is $\equiv$ $1$ or $-1$ $\pmod{p}$. I think this can be done by viewing the primitive roots as a elements of ...
1
vote
2answers
77 views

Prove if, $2^n - 1$ is prime, then $n$ is prime. [duplicate]

Prove, when $n$ is a positive integer, if $2^n - 1$ is prime, then $n$ is prime. I did read some sort of proving on the web, but I could not understand it... Any help? And if possible, could the ...
0
votes
0answers
19 views

Help with Dixon's factorization algorithm?

I've been trying to implement Dixon's factorization method in python, and I'm a bit confused. I know that you need to give some bound $B$ and some number $N$ and search for numbers between ...
1
vote
0answers
56 views

Prime twins and $1 \mod 30$ confusion

Jie Wu improved Brun's theorem and showed that the number of prime twins up to $n$ satisfies for sufficiently large $n$ : $$\pi_2(n) < 4.5 \frac{n}{ln(n)^2} $$ However this confused me while ...
1
vote
1answer
26 views

Proof that Mersenne numbers with a composite exponent are also composite

I'm following the book The Haskell Road to Logic, Maths, and Programming, and I am unsure of one of my proofs for one of the exercises. It is to be proven that a number of the form $M_n = 2^n -1$ is ...
0
votes
1answer
18 views

How many pickups $K$ should I do to have a $p$% of probability of picking up a divisor of $n$ (if exists) in the interval $[2..\lfloor n/2\rfloor]$?

I am trying to understand if it makes sense an algorithm to decide if a given number $n$ is possibly prime or not by using the divisor function bound defined by professor Jeffrey Lagarias as: ...