Prime numbers are natural numbers greater than 1 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
70 views

Reasoning about $z^n = x^m + y^m$

Let $z,n,x,y,m$ be positive integers with $z \ge 5$ and $m \ge 3$ and $m$ odd. Does it follow that: $z$ cannot be prime if $p \ge 5$ and $p | z$, then either $p > m$ or $p|m$ Here is my ...
0
votes
1answer
27 views

About $x(\ln(x\ln(x))-1)<p_x<x\ln(x\ln(x)), x>5$ and better results

I need some tips about this: It has been proved that (1) $$x(\ln(x\ln(x))-1)<p_x<x\ln(x\ln(x)),\quad x>5$$ Is there a better results? Thanks!
2
votes
3answers
78 views

About $\pi(x)<li(x)-\frac{1}{3}\frac{\sqrt{x}}{\log(x)}\log(\log(\log(x)))$

Today I found that in 1914, Littlewood proved that (1) there are arbitrarily large values of $x$ for which $$\pi(x)<li(x)-\frac{1}{3}\frac{\sqrt{x}}{\log(x)}\log(\log(\log(x)))$$ First: Is ...
0
votes
1answer
49 views

Has this partial result about Legendre's Conjecture been proved?

I'd like to know if it has been proved this "partial result" about the Legendre's Conjecture: (1) There are infinitely many $n$ such that there's a prime in $(n^2, (n+1)^2)$ Thanks!
1
vote
0answers
69 views

Can this approach to showing no positive integer solutions to $p^n = x^3 + y^3$ be generalized?

The following problem is a $2000$ Hungarian Olympiad question. Find all primes $p$ such that: $$p^n = x^3 + y^3$$ The answer is that there are only $2$ solutions: $2^1 = 1^3 + 1^3$ $3^2 = 2^3 + 1^...
20
votes
4answers
4k views

Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?

This question relates to a discussion on another message board. Euclid's proof of the infinitude of primes is an indirect proof (a.k.a. proof by contradiction, reductio ad absurdum, modus tollens). My ...
3
votes
1answer
75 views

Number Theory : Primes not in Twin Primes

I was working through some basic number theory questions , when I came across : Show that there are infinitely many primes that are not one of the primes in a pair of twin primes How can I go ...
2
votes
4answers
268 views

Primitive root modulo $p=8t + 3$

Suppose that p is a prime of the form $8t +3$ and that $q=(p-1)/2$ is also a prime. Show that 2 is a primitive root modulo p. We must show that $ 2^{(p-1)} \equiv1 \ (mod \ p) $ for this we use the ...
2
votes
1answer
93 views

Prove that $\pi(n^2)-\pi(\frac{n^2+2n}{2})>0$

I'd like to know if there's a better way to prove that: $$\pi\left(n^2\right)-\pi\left(\frac{n^2+2n}{2}\right)>0$$ than using "There's always a prime in $(m-m^{23/42},m)$" by Iwaniec-Pintz: (I ...
0
votes
1answer
32 views

Why $\sum_{k=1}^\infty \left\lfloor\frac{n}{p^k}\right\rfloor≤\frac{n}{p-1}$?

I need some help: can someone tell me why $$\sum_{k=1}^\infty \left\lfloor\frac{n}{p^k}\right\rfloor≤\frac{n}{p-1}$$ I found this inequality in Wikipedia, and I want to know if it's true, thanks!
1
vote
1answer
42 views

Determine whether $\sum_{t=2}^n\frac{\log t}{\Omega(t)}\sim n\log n$

Determine whether $$\sum_{t=2}^n\dfrac{\log t}{\Omega(t)}\sim n\log n$$ Let $r=n^{1/\Omega(n)}$, where $n$ is a positive integer and $\Omega(n)$ is the total number of prime factors of $n$. If $r$ is ...
5
votes
2answers
228 views

prove that $f_n = 37111111…111$ is never prime [duplicate]

Let $$f_n = 37111111...111$$ with n 1's. Prove that $$f_n$$ will never be prime for $$n\ge1.$$ I tried to look $$f_n$$ in mod(p), assuming $$f_n$$ is prime, for the sake of contradiction. I also ...
2
votes
2answers
124 views

Proving $\prod_{i=1}^np_i+1$ is not a perfect square

Let $m=\displaystyle{\prod_{i=1}^np_n}$ be the product of the first $n$ primes $(n>1)$. prove that $m+1$ cannot be a perfect square. I think that the opposite it correct: $m+1$ is not a complete ...
1
vote
2answers
902 views

Possible Proof for Goldbach's Strong Conjecture? [closed]

Goldbach's Conjecture states: Every even integer greater than 2 can be expressed as the sum of two primes. Possible proof: All prime numbers are odd numbers with the exception of 2. If a ...
4
votes
1answer
177 views

Why doesn't Mertens's second theorem prove the Prime Number Theorem?

Mertens's second theorem states that $$\sum_{p \le x} \frac 1p = \log \log x+O(1).$$ Defining $p_x=p_{\lfloor x \rfloor}$ for all real $x \ge 1$, we can replace the sum by the integral $$\int_1^x \...
0
votes
1answer
172 views

Is there a polynomial that generates only primes or semi-primes?

I know that no non-constant polynomial function $P(n)$ with integer coefficients exists that evaluates to a prime for every integer value of $n$. My question is - does there exist a non-constant ...
2
votes
1answer
76 views

Understanding the proof behind $\pi(x) \ge \frac{\log 2}{2}\frac{x}{\log x}$

I am trying to understand the argument behind the proof that: Given: $$\pi(2n) \ge \log 2\frac{2n}{\log 2n}-1$$ Then for $x \ge 2$: $$\pi(x) \ge \frac{\log 2}{2}\frac{x}{\log x}$$ Here's the ...
2
votes
1answer
46 views

Does the standard argument behind Bertrand's Postulate show that $\pi(2x)-\pi(x) > \frac{2n\log 2}{3\log 2n} -\sqrt{2n} - 1$

The standard argument for Bertrand's Postulate gives: $$\left(\prod\limits_{2n \ge p > n} p\right)\left(2^{\frac{4n}{3}}\right)\left((2n)^{\sqrt{2n}}\right) > { {2n} \choose {n} } = \left(\prod\...
2
votes
2answers
51 views

Find all numbers of form $10^k+1$ divisible by $49$

Basically, I've tried to take mods, and it hasn't been very successful. Also, if it helps, I noticed that the sequence can be recursively written as $a_{n+1}=10a_n-9$, starting with $a_1=11$.
1
vote
4answers
353 views

How can prime numbers be found mentally?

At a careers fair I was given a test to see how good I am at mental maths, And I was given multiple questions, asking whether a number was a prime. Example question: Which of these numbers isn't a ...
2
votes
0answers
42 views

Proof of an inequality about primes

I'm very new to number theory and looking for a proof of the following inequality: $$c' \log^{\text{#} \mathbb{P}}{R} \leq \sum \limits_{\substack{n \leq R\\p|n \implies p \in \Bbb P}} 1 \leq c \log^{...
-1
votes
1answer
83 views

The set of prime numbers whose first digit are 1

Why cannot I use Dirichlet's theorem on primes in arithmetic progressions to compute the density of the set of prime whose first digit is 1? Thank you very much :)
2
votes
5answers
120 views

Prove that if $3\mid n^2 $ then $3\mid n $. [duplicate]

$n \in \mathbb{N}$ Prove that if $3\mid n^2 $ then $3\mid n $ I want to prove this in a accepted formal way, I thought about the fact that every integer can be written as multiplication of prime ...
1
vote
0answers
53 views

Bunyakovsky conjecture for cyclotomic polynomials

This article on Wikipedia: http://en.wikipedia.org/wiki/Bunyakovsky_conjecture says: In fact, it can be shown that if for all natural number $ n $, there exists a natural number $ x > 1 $ such ...
1
vote
0answers
43 views

Is there a better way to search a string so that I don't get false positives?

I've been using this equation to find primes of a specified range, in this example the range is 10 to 10000. Go ahead and try it out, your monitor will not catch fire. The problem I'm now having is I'...
0
votes
2answers
116 views

Where does 2525 and 252525 come from in RSA cryptosystem example?

This is an example from Discrete Mathematics and its Applications I understand how to encrypt, the first step is to turn the letters into their numerical equivalents(same thing we had to do for ...
5
votes
2answers
124 views

What is sum of totatives of n(natural numbers $ \lt n$ coprime to $n$ )?

Same question as in title: What is sum of natural numbers that are coprime to $n$ and are $ \lt n$ ? I know how to count number of them using Euler's function, but how to calculate sum?
1
vote
1answer
73 views

Aut($C_p) = C_{p-1}$when $p$ is prime, why?

Aut($C_p) = C_{p-1}$ when $p$ is prime, why? I don't see why this result follows, I'm sure it's obvious though. I appreciate that Aut($C_p)$ will be of order p-1
-4
votes
2answers
807 views

How to find all the Quadratic residues modulo $p$

I want to implement Sieve improvement for Fermat's factorization method. For that I need your help answering: How to find all the Quadratic residues modulo $p$? $$\{x ~\vert~ x^2 \equiv q \pmod{p}\}$...
0
votes
2answers
122 views

Prove that if $ n > 2 $ then between $n$ and $n!$ is at least one prime. [duplicate]

Prove that if $ n > 2 $ then between $n$ and $n!$ is at least one prime. Ok I can see that it's obviously true, but what to use to prove it?
3
votes
1answer
174 views

What is the value of $\sum_{p\le x} 1/p^2$?

My question is, what is the value of $$\sum_{p\le x} \frac{1}{p^2}?$$ More generally, what is the value of $$\sum_{p\le x} \frac{1}{p^n}?$$ How can we find it? For $\sum_{p\le x} 1/p$ the idea was ...
1
vote
1answer
128 views

Curve profile for the logarithm-integral sum term of Riemann explicit formula?

I am considering the following term from the Riemann explicit formula (see here >>>): $$\sum_{\rho(\Im>0)}{\mathrm{li}(x^\rho)}$$ with $\rho$ non-trivial zeros of $\zeta$-function. I have a plot ...
1
vote
1answer
117 views

How to calculate the $i$-th element in the sequence of prime numbers?

The sequence of prime numbers is the set of prime numbers in their natural order (that is, $2, 3, 5, 7, 11, 13, 17,...$). The German wikipedia entry on sequences states the following: Given $i$, ...
5
votes
1answer
197 views

Explicit formulas for primitive roots?

For a Fermat prime or an "upper" Sophie Germain prime a primitive root is explicitly known. Are there further results when the factorization of p-1 is known? Is it unlikely that we ever get explicit ...
0
votes
2answers
162 views

Prove that every number between two numbersis composite

I have this problem, and I have no idea how to go about it: Let $p_1,p_2, \ldots, p_{n+1}$ be the first $n+1$ primes, in order. Prove that every number in between $p_1 \cdot p_2 \cdot p_3 \ldots p_n+...
0
votes
1answer
85 views

primes congruent to 5 mod 6 and 1 mod p

I believe that for every prime $p\geq 5$ there exists at least one prime $q$ that is both congruent to 1 mod $p$ and congruent to 5 mod 6. It's well known that there are an infinite number of primes ...
14
votes
0answers
131 views

What other prime numbers have been ruled out as counterexamples to the Feit-Thompson conjecture?

Given distinct primes $p$ and $q$, $$\frac{p^q - 1}{p - 1}$$ is never a divisor of $$\frac{q^p - 1}{q - 1}.$$ Or so we believe. If $p = 2$, then it's clear that no odd prime $q$ can make a ...
0
votes
1answer
59 views

How to find all the Quadratic residue of $x$?

How can I efficiently find all the Quadratic residue of some prime number $x$? $$\{y ~\vert~ x^2 \equiv y \pmod{p}\}$$ In wiki they speak about some thing called ...
17
votes
1answer
471 views

Short intervals with all numbers having the same number of prime factors

How to prove that for some $k, n_0$, for all $n \ge n_0$ it is never the case that all integers in $\{n, n+1, \dots, n + \lfloor (\log{n})^k \rfloor\}$ have exactly the same number of prime factors ...
1
vote
1answer
78 views

Sets with prime subset sums

1. Given $M$ is it possible to pick a set of $T>M$ distinct numbers $a_i\in\Bbb Z$ such that sum of any $M+1$ or more of them will always be a prime and sum of any $M$ or less of them is always ...
10
votes
1answer
186 views

Are there infinitely many pairs of primes where one divides one more than the square of the other?

I have the following question on number theory that is eating my head. Are there infinitely many primes $p,q$ such that $p | (q^2 + 1)$ and $q | (p^2 + 1)$? I can see $13,5$ and $2,5$ has the ...
0
votes
1answer
33 views

$q \equiv 2 (\mod 3)$ be a prime , then does there exist non-zero integers $a,b,c$ such that $a^2+ab+b^2=qc^2$ ?

Let $q$ be a prime such that $q \equiv 2 (\mod 3)$ , then is it true that $a^2+ab+b^2=qc^2$ has no solution in non-zero integers $a,b,c$ ?
0
votes
1answer
56 views

Solving x^4=a mod p, given a is a quadratic residue

Given prime number $p\equiv 1 \pmod 4$. Prove if $a∈F_p^×$ is a quadratic residue then the congruence $$x^4 ≡ a \pmod p$$ has either no solutions or four solutions. Give examples of each case.
4
votes
2answers
144 views

Proving $\frac{p_{n+1}^2-p_{n+1}^{-C}}{p_{n+1}^2-1}>\frac{f(n) p_n \log p_n }{p_{n+1} \log p_{n+1}},$ where $f(n)\to1$, for some constant $C>1$

Are there two constants $C_1$, $C_2>1$ such that for large enough $n$ $$\frac{p_{n+1}^2-p_{n+1}^{-C_1}}{p_{n+1}^2-1}>\frac{2 C_2 p_{n+1} \log p_{n+1}-1}{2 C_2 p_{n} \log p_{n}-1} \left(\frac{p_n ...
7
votes
1answer
88 views

When is $p^n(p^n-1)$ divisible by $2n$

Let $n\in\mathbb{N}$. Then, when is $p^n(p^n-1)$ divisible by $2n$ for all $p$ prime? I know the following: $n$ must be $1$ or even. (in the odd case, $p=2$ gives a counterexample). If $n=2^k$ for ...
8
votes
1answer
237 views

Proving that there are at least $n$ primes between $n$ and $n^2$ for $n \ge 6$

I was thinking about Paul Erdos's proof for Bertrand's Postulate and I wondered if the basic argument could be used to show that there are more than $n$ primes between $n$ and $n^2$. Is this approach ...
2
votes
3answers
185 views

How to prove the following recursive sequence produce relatively prime numbers

Sequence an is defined recursively: $a_1 = 2$ $a_{n + 1} = {a_n}^2 - a_n + 1$ Prove that $a_i$ and $a_j$, $i \neq j$ are relatively prime. Hint: Prove that $a_{n + 1} = a_1 a_2 \ldots a_n + 1$ and ...
0
votes
1answer
195 views

Largest superprime number

Call a number n a superprime if every consecutive block of digits in n is also a prime. For example, the number 3727 contains the blocks 37 and 727, which are prime, but it also contains the blocks 72 ...
0
votes
1answer
40 views

Show number of integers $m$ with $1\leq m\leq n$, divisible by $p^h$ is equal to $\left[\frac{n}{p^h}\right]$

Let $n\in\mathbb{N}$, $p$ a prime number. Show that for each $h\in\mathbb{N}$, the number of integers $m$, with $1\leq m\leq n$, divisible by $p^h$ is equal to $\left[\frac{n}{p^h}\right]$, where $\...
-1
votes
2answers
405 views

Proof that if x is prime, then x+7 is composite. [closed]

Proof that if x is prime, then x+7 is composite. I do not know how to prove it. Can anyone help me to solve it? Thx