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.
0
votes
1answer
73 views
Primes without Power of 2 [duplicate]
Let $x,y,k$ be nonnegative integers, with $k$ not being a power of $2$. We also know the proof for the following statement: The number $x^k+y^k$ is not prime.
I need help on the second part:
...
-3
votes
1answer
116 views
Questions about prime numbers
Let $x,y,k$ be nonnegative integers, with $k$ not being a power of $2$.
Prove that $x^k+y^k$ is not prime.
Conclude that if $2^n + 1$ is prime and $n$ is not a power of $2$, then $n$ is prime.
2
votes
0answers
38 views
Primes of the form $\dfrac{n^2-n+4}{2}$ satisfy Hardy-Littlewood analogue?
Let $n,a,b$ be positive integers with $a<b$. Consider primes of the form $f(n)=\dfrac{n^2-n+4}{2}$. Let $C(a,b)$ denote the amount of primes of the form $f(n)$ between (and including) $f(a)$ and ...
6
votes
1answer
320 views
Primes of form $x^2+x\pm k$
Perhaps someone could venture an explanation (maybe with some unproven assumptions) that makes heuristic sense of relation (1),(2) and examples below? Thanks for any insights.
Let $\pi(n) = $ number ...
2
votes
1answer
50 views
What error bound would an epsilon closer to the Riemann hypothesis give?
$s=1$ line gives: $$\psi(x) = x(1+o(1))$$
classical zero free region gives: $$\psi(x) = x + O(x e^{-c \sqrt{\log x}})$$ for some positive constant $\delta$
RH gives: $$\psi(x) = x + ...
1
vote
1answer
52 views
Show that Fermat number $F_n$ and its index $n$ are coprime.
I want to show that $\gcd(F_n,n)=1$, where $F_n=2^{2^n}+1$. How to prove this?
I can show that that $\gcd(F_n, F_m)=1$ for any natural $n$ and $m$, and that $F_{n+1}=(F_n)^2-2F_n+2=F_0\dots ...
4
votes
0answers
98 views
Prime numbers, analysis of polylogarithms
Can any interesting results concering prime numbers be obtained using the analytic properties of the polylogarithm, similar to how analytic methods are used on the zeta function to obtain results ...
5
votes
1answer
113 views
Sequence involving primes of form $n^2 + n+1$
Looking at prime numbers $p_i $ of the form $n^2+n+1$ and the derived expression
$$1 - \prod_{i=1}^{j}\frac{(p_i-1)}{p_i}$$
it seems (I do not claim it and do not see why it should be true) that ...
3
votes
1answer
62 views
Question involving prime numbers, *brothers* numbers.
I thought about the following problem, probably it already appears in mathematical literature.
Definition 1:
Operator $\unrhd$, is binary operation, defined for natural numbers as follows:
To every ...
2
votes
2answers
67 views
Proof of lack of pure prime producing polynomials.
Now I have heard this (correct me if I am wrong) that for every polynomial, there is some positive integer for which it is composite. What is the most elementary proof of this.
2
votes
2answers
144 views
Prove that if $a$, $b$, and $n$ are positive integers such that $a^n|b^n$ then $a|b$
This is how I did it, but not sure if it is a correct proof.
Assume that $a^n | b^n$. Then $(a^n, b^n) = a^n$.
So,
$$b^n = a^n(p_1p_2p_3...p_k)^n$$
$$b^n = (ap_1p_2p_3...p_k)^n$$
$$b = ...
2
votes
1answer
76 views
How does sieve that Chen used to prove Chen's theorem work?
In the Number Theory for Computing, Song Y. Yan states that Chen used "complicated arguments based on sieve method", when proving what is now called Chen's theorem.
How does this sieve work? Does it ...
0
votes
2answers
61 views
Congruences and Primes
Show that if p is an odd prime, with p = 3 (mod 4), then
$$
(\mathbb{Z}_{p}^{*})^4 = (\mathbb{Z}_{p}^{*})^2
$$
More generally, show that if n is an odd positive integer, where p = 3 (mod 4) for each ...
2
votes
5answers
71 views
Prove that if $n$ is a composite and $p \gt \sqrt[3]n$, then $n/p$ is a prime.
Also, $p$ is the least prime factor of $n$. I'm trying to do this by way of contradiction.
Since $n$ is a composite, $n = pq$, for some $q \in \Bbb Z$. So, we have $p | n$, $q|n$ and $q = \frac ...
1
vote
1answer
44 views
Are there infinitely many primes of the form $n^k+l_0$ for fixed $l_0$ when $(n,k)$ runs through the $\mathbb N\times ({{\mathbb N}\setminus\{1\}}$)?
I do not know if this what I am going to ask is immediate consequence of something known but if not it may have an easy answer which I do not see, so any help would be great. Let us define sequence ...
0
votes
1answer
103 views
Prove that if $n$ is a composite, then $2^n-1$ is composite. [duplicate]
Not sure if I'm doing this correctly but this is what I've done:
Assume that $n$ is composite and suppose $2^n-1$ is a prime for $n \gt 2$.
Then, $2^n-1 = 2k$ for some $k \in \Bbb Z $, $\forall n$. ...
1
vote
2answers
69 views
Indices - Numbers as a product of prime numbers
I've checked the internet which only provides basic $x^2 \times x^3 = x^5$ information and have concluded that I need resort to a Q & A website. The basics of indices are fine for me, but it's ...
3
votes
2answers
220 views
When is the number 11111…1 a prime number?
For which $n$ is the sum:
$$\sum_{k=0}^{n}10^k$$
a prime number? Are they finite?
2
votes
1answer
84 views
Primes of form $n^{n+1} - (n+1)^n$
I was playing with some numbers today and saw (with a bit of joy) that $3^4 - 4^3$ is the $(3 + 4)$th prime number, which is sort of neat. Then naturally I asked the question, what kind of number $n$ ...
2
votes
1answer
55 views
How many solutions to prime = $2 b^2 c^2 + 2 c^2 a^2 + 2 a^2 b^2 - a^4 - b^4 - c^4$
Let $a,b,c$ be integers, no sign restriction.
Let $p$ be a given prime.
How to find the number of solutions to $p = 2 b^2 c^2 + 2 c^2 a^2 + 2 a^2 b^2 - a^4 - b^4 - c^4$ ?
Note, from Heron's ...
3
votes
3answers
119 views
How many solutions to prime = $a^3+b^3+c^3 - 3abc$
Let $a,b,c$ be integers.
Let $p$ be a given prime.
How to find the number of solutions to $p = a^3+b^3+c^3 - 3abc$ ?
Another question is ; let $w$ be a positive integer. Let $f(w)$ be the number of ...
1
vote
2answers
71 views
How many solutions to prime = $(d^2-2ad+b^2-2ab+2a^2)(d^2-2cd+2c^2-2bc+b^2)$?
Let $a,b,c,d$ be integers $>-1$.
Let $p$ be a given prime.
How to find the number of solutions to $p = (d^2-2ad+b^2-2ab+2a^2)(d^2-2cd+2c^2-2bc+b^2)$ ?
I assumed that this polynomial above does not ...
0
votes
1answer
63 views
Primes $n=\overline{10101\cdots01}$ with $k$ ones.
Find all primes $n=\overline{10101\cdots01}$ with $k$ ones.
The number is in standard base 10.
0
votes
1answer
17 views
What is the pair $(n,k)$ called where $n$ is an integer and $k$ is the ordered factorization index?
I’m developing a number class (as in Object-Oriented Programming) and am wondering what to call it. At its core, it represents an integer, but in a way in which not all integers are unique. What it ...
0
votes
1answer
58 views
Using Prime numbers to map n integers uniquely to an integer x and allowing an easy reverse mapping
Say I have m integers:
$i_{0}, i_{1}, ..., i_{x}, ..., i_{m} where -L < i_{x} < M$ where L and M are known integers
is it possible to come up with a function that uses Primes that maps
...
0
votes
1answer
57 views
Inequality with floor function (involving sum of the first $n-1$ primes)
Can we somehow prove that this holds: $p_n>$$\lfloor$$ 2(\sum_{i=1}^{n-1}p_i)\over n-1$$+1\rfloor$, for $n\geq5$, and $p_i$ is the i-th prime number?
1
vote
1answer
56 views
Residue Classes
I am trying to show that:
$$\sum\limits_{\beta \in \mathbb{Z}_p^*}{\beta^{-1}}=\sum\limits_{\beta \in \mathbb{Z}_p^*}{\beta}=0$$
Where p is an odd prime.
I really dont know where to start, but my ...
4
votes
1answer
139 views
are two consecutive numbers relatively prime?
I have a question.
I have been given this proof: "For any $n$ in the integers where $n>2$, show there are at least $2$ elements in $U(n)$ that satisfy $x^2=1$."
I have gone through and actually ...
1
vote
1answer
37 views
what is the property of this numbers
A multiple of $3$ gives
$0,3,6,9,12,15,18,21,24,27$
which rearrange the last bit of each number gives $0,1,2,3,4,5,6,7,8,9$ once.
The same can be said of $7$ and $9$ as well which gives
...
1
vote
1answer
43 views
Counting primes of the form $S_1(a_n)$ vs primes of the form $S_2(b_n)$
Let $n$ be an integer $>1$. Let $S_1(a_n)$ be a symmetric irreducible integer polynomial in the variables $a_1,a_2,...a_n$. Let $S_2(b_n)$ be a symmetric irreducible integer polynomial in the ...
1
vote
0answers
29 views
If $p$ is a prime, then prove that $(p−1)!+1$ is a power of $p$ if and only if $p = 2$, $3$, or $5$. [duplicate]
Possible Duplicate:
When is $(p - 1)! + 1$ a power of $p$?
If $p$ is a prime, then prove that $(p−1)!+1$ is a power of $p$ if and only if $p = 2$, $3$, or $5$.
I could not find an ...
3
votes
1answer
68 views
Why isn't the naive PRIMES algorithm in P?
The naive algorithm tries dividing $n$ by $2 \dots n-1$ to see if it divides without a remainder. Each division can be done in $O(n)$-time and there are $O(n)$ divisions to be made. What's wrong with ...
0
votes
2answers
66 views
Standard Basis of the Finite Field of Prime Numbers
A little info regarding this field:
Addition and multiplication in $Z^n_p$ behave as usual but with the remainder taken upon division by $p$.
Ex: $Z_3$ will only consist of the three integers ...
1
vote
5answers
180 views
Basic number theory proofs
Deduce that there is a prime gap of length $\geq n$ for all $n \in \mathbb{N}$
Show that if $2^n - 1$ is prime, then $n$ is prime.
Show that if $n$ is prime, then $2^n - 1$ is not divisible ...
3
votes
1answer
64 views
Prime number based calendar: how to calculate intermediate values?
I'm trying to define a new [silly] calendar, because there aren't enough of them yet.
My calendar, so far, is specified:
epoch (orthodox) is the moment the leading edges of the dinosaur-killing ...
10
votes
1answer
101 views
For each $n$, does there exist a prime $p$ and integer $k$ such that $p^k - 1$ has exactly $n$ prime divisors?
Let $n \geq 1$ be some integer. Can we always find a prime power $p^k$ such that $p^k - 1$ has exactly $n$ distinct prime divisors?
For example:
$n = 1$ example: $2^2 - 1 = 3$
$n = 2$ example: $5^2 ...
8
votes
2answers
82 views
$R$ with an upper bound for degrees of irreducibles in $R[x]$
One very convenient property of $\mathbb{R}$ as a ring is that there is an upper bound for the degree of irreducible polynomials in $\mathbb{R}[x]$, as
If $f\in\mathbb{R}[x]$ has degree larger ...
-1
votes
1answer
56 views
primes of type norm($a+b\sqrt{-c}$) = primes of type $1$ $mod$ $c 2^{n-1}$?
Let $a,b,c,n$ be strictly positive integers where $c$ is a prime and such that the normed ring $a+b\sqrt{-c}$ is a UFD.
I noticed the primes of norm($a+b\sqrt{-1}$) are $1 \bmod 4$. Also the ...
0
votes
1answer
44 views
primes of the form $a^2+b^2=x^2-xy+y^2$?
Let $a,b,x,y$ be strict positive integers.
Im intrested in primes $p$ such that $p=a^2+b^2=x^2-xy+y^2$.
What is the analogue PNT for these type of primes ? I think these primes are all the primes $p ...
2
votes
3answers
75 views
Primes and a polynomial
This should be easy but at this moment I have no useful idea on how to solve it and the problem is:
Show that there exist an infinite number of prime numbers that are not expressible as $p=n^2+2$.
0
votes
2answers
156 views
Many kinds of Infinitely many
Here is the sequence of the primes p =1 mod 6 (and thus p =1 mod 3) such that
$(p^{2}+p+1)/ 3$ is not prime :
37 61 67 79 109 139 151 163 181 193 211 229 277 283 307 313 331 337 349 367 373 379 397 ...
1
vote
1answer
51 views
elementary divisibility argument
I am trying to argue that for distinct primes $p,q,r$ we have that
$$
\gcd (pq + qr+ pr ,pqr ) = 1 = g
$$
and I am wondering whether people find the following argument convincing :
Consider the ...
0
votes
0answers
39 views
Something related to Polignac conjecture
I would like that all of you interested in number theory and specially, in prime numbers, to take a look at this quite elementary approach on the problem related to the conjecture of Polignac, which ...
0
votes
1answer
101 views
Are sequences useful?
Here is a sequence; experimental mathematics :
$2, 2, 2, 11, 11, 254908033,...$ we could define as :
Least primes such that
$((p+1)(nextprime(p)+1))-1$ is prime and
...
0
votes
2answers
119 views
Fermat Numbers as a product
We are discussing Fermat numbers in class, and one of the claims brought up is as follows:
"For any integer $n \ge 1$, the $n$th Fermat number is $F(n)$ = $2 + \prod_{i=0}^{n-1}F(i)$."
I have not ...
1
vote
2answers
44 views
Explaining how $n = 2^r$ for $n$ prime
I found this claim in my textbook while reading the section on prime numbers today:
"If $n$ is a positive integer such that $2^n + 1$ is prime, then $n = 2^r$ for some integer $r \ge 0$."
Where did ...
0
votes
0answers
75 views
Will this work as a $\pi_{4n\pm 1}$ prime counting function?
I forgot where it was, but I remember someone saying that you need $\phi(4)$, which is two, of Dirichlet's $L$ functions to get a prime counting function for primes of the form $4n\pm 1$ less than ...
0
votes
0answers
89 views
Divergence of the Derivative of the Prime Counting Function
On the one hand, the Prime Counting Function $\pi_0(x)$ maybe be written
$$
\pi_0(x) = \operatorname{R}(x^1) - \sum_{\rho}\operatorname{R}(x^{\rho}) \tag{1}
$$
with $ \operatorname{R}(z) = ...
1
vote
0answers
41 views
Any work on properties of $N + \bar \phi (N)$?
I am looking for pointers to any existing materials about the properties of this quantity.
For Euler's cototient, if a number $N$ is written as $2^a \cdot b$ with b odd then the cototient is $$\bar ...
3
votes
2answers
340 views
How to find number of prime numbers between two integers
I have two integers, $x$ and $y$ so that $x \lt y$. How many prime numbers are there between $x$ and $y$ (exclusive). Is there a formula or algorithm to compute?
