Questions tagged [prime-numbers]
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.
8,047 questions
1
vote
0answers
15 views
Prime counting function $\phi(x)-c(x)$ vs. $x/\ln(x)$
So $\pi(x)$ is the prime counting function. That is to say, it counts the number of primes below a given integer $x$. This function is very important in number theory. I was wondering how well the ...
1
vote
1answer
24 views
How does this method work to find prime numbers?
I'm curious about this pattern that I saw while adding many powers of two together, and then taking the prime factorisation of each result, and I'm curious as to why this occurs.
Here is the pattern:
...
2
votes
1answer
45 views
For every $x\in\mathbb{N}$ write $2x=2\prod_{i=1}^{n}p_i$ with $p_i=6k_i+1$ primes
I want to prove the following:
$$\forall x\in\mathbb{N}\ \exists\text{ a prime }p\equiv1 \pmod 6 \text{ s.t. }p|(2x)^2+3;$$$\ \text{i.e. } (2x)^2\equiv-3 \pmod p$ for some $p\equiv1 \pmod 6$ has to ...
0
votes
2answers
11 views
Are mersenne primes of exponent being a mersenne primes always prime?
A mersenne number is a number on the form (2^n)-1 . For it to be prime, the number n must be prime.
My question is that if n it's another mersenne prime, will 2^n-1 be always prime?
It seems so, to ...
0
votes
0answers
36 views
Compositeness tests for numbers of the form $k \cdot b^n \pm c$
Can you provide proofs or counterexamples for the following claims?
Claim 1
Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ .
Let $M= k \cdot b^{n}-c $ where $k,b,n,c$ are ...
1
vote
1answer
34 views
Can the set of odd primes be decomposed into $\Bbb{P} = A + B, $ for some $A,B \subset \Bbb{Z}$?
Can there ever exist infinite sets of integers $A, B$ such that $A + B = \{ a + b: a \in A, b \in B\} = \Bbb{P}$? Where $\Bbb{P}$ is the set of odd primes? You can include $0$ and / or $\pm$ odd ...
2
votes
2answers
38 views
“Although it is necessary for $n$ to be prime in order for $R_n$ to be prime” as logic statement
This is a statement about Repunits from this paper.
How can I write this as an if/then statement?
Knowledge about Repunits isn't required. The question is basically: what does "although it is ...
2
votes
1answer
29 views
Can you determine small primes from larger primes?
Suppose you are given the primes in the range $[n,n^2]$. Is there a known way to effectively reconstruct the primes less than $n$? Ideally, something that takes less calculation than figuring them out ...
0
votes
2answers
44 views
Prove (in)equivalency: (1) $\exists$ non-zero $z\in\mathbb{Z}/n\mathbb{Z}$ such that $z^{t}=0$ for some $t$, (2) $\exists$ prime $p$ such that $p^2|n$
I need to prove the equivalency/inequivalency of two statements:
(1) There exists a $z \in \mathbb{Z}/n\mathbb{Z}$, $z\neq{0}$, with $z^{t} = 0$ for some $t \in \mathbb{N}$
(2) There exists a prime ...
0
votes
0answers
28 views
Pythagorean and the number 17 [on hold]
I was looking for some properties of the prime numbers, and I found some curiosities of the number 17 in that site.
One of them is this
17 was called by the Pythagoreans - opposition, obstruction,...
-4
votes
1answer
42 views
Prime numbers that are sums of Prime numbers themselves [on hold]
what is the minimum prime number that is the sum of exactly two odd prime numbers?
i.e I want to find a counter example to:
$$p_i+p_j \in \mathbb P \operatorname{iff} i=1 \lor j=1$$
0
votes
1answer
103 views
+50
Compositeness tests for generalized repunit numbers
Can you provide proofs or counterexamples for the following two claims:
First claim
Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ .
Let $M_p(a)= \frac{a^p-1}{a-1} $ where $a$ ...
0
votes
0answers
36 views
Does Goldbach conjecture imply the twin prime conjecture ?
Under the Goldbach conjecture, define a primality radius of a large enough composite positive integer $ n $ to be a positive integer $ r $ such that both $ n-r $ and $n+r $ are primes. Assume $k $...
-1
votes
1answer
65 views
Finding the n-th prime number [on hold]
We want to uniquely map hash values to prime numbers. One way to achieve this is storing the first $l$ prime numbers into an ordered list $L$ with size $|L| =l$. When the hash value $h$ calculated, ...
6
votes
1answer
79 views
Prime divisor in positive integers sequences
I would like to know if anyone has an ideea if the following statement is true.
For any sequence of consecutive positive integerers $(n_0, n_0+1,..., n_0+k).$ Where $n_0 \ge 1, k\ge 0,$ but $k\ge 1$ ...
1
vote
1answer
54 views
Certain Complex Integral
I was trying to generalize the Riemann's prime number formula for $\pi(x)$ to a general algebraic field $K$, and came across the integral:
$$f(x)=\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty}\frac{d}{...
1
vote
2answers
27 views
Partial part of fermat's little theorem [on hold]
Am I fool? I cannot understanding the partial part of the proof.
$\{1,2,...,p-1\}\equiv \{a,2a,...,(p-1)a\}\ (mod\ p)$
Why above statement is true? How I remove a??
0
votes
0answers
17 views
How to efficiently find the number of coprime pairs such that none of the pair elements belong to the same group?
I have 'n' number of positive integers. I want to find the number of coprime pairs such that none of the pair elements belong to the same group.
For example, if my number sequence is ...
2
votes
0answers
30 views
Prove that any polynomial with integer coefficients must have a composite number in its image. [duplicate]
Let $f \in \mathbb{Z}[x]$ be a polynomial of degree at least $1$. Prove that there is $n \in \mathbb{Z} $ such that the corresponding polynomial function $f(n)$ is not a prime.
I think that the ...
1
vote
0answers
41 views
Generating prime factors of a certain congruence?
I'm aware that prime factors of $n^2+1$ take the form $4k+1$. It's also well known that factors dividing $\frac{a^p \pm 1}{a \pm 1}$ will be congruent to $2kp+1$. Fibonacci and some other recurrence ...
2
votes
1answer
32 views
Primes congruent to $k \pmod p$ between $p$ and $p^2$?
Is it true that for any prime $p$, there are primes $< p^2$ which are congruent to every $k<p$?
For example,
$$
\begin{align}
11 &\equiv 1 \pmod 5 \\
7 &\equiv 2 \pmod 5 \\
13 &\...
6
votes
1answer
140 views
Particular base-10 digit patterns in Collatz
Note: I will use the abbreviation RCF for the Reduced Collatz Function.
The arrangement of certain specific digits produce a particular pattern on the next iteration of the Reduced Collatz Function. ...
3
votes
2answers
54 views
Primes of the form $p_1p_2\dotsm p_k+1$ [on hold]
Let $p_1,p_2,...,p_k$ be the first $k$ primes and $k>1$. Does there exist a prime $p_{k+1}$ such that $p_{k+1} = p_1p_2...p_k + 1$?
4
votes
3answers
47 views
Proof that Cardinality of Primes is Cardinality of Natural Numbers
I need to prove that the cardinality of the set of prime numbers is the same as the cardinality of the set of natural numbers. This is the proof I came up with:
$\mathbb{P}\subseteq \mathbb{N}\...
0
votes
1answer
23 views
Prove set of primes is equal to set of natural numbers
I was studying for an upcoming test in college and was looking at an old test. I'm struggling to understand how to prove this problem and was hoping someone could help me out.
Prove that |P| = |N| ...
1
vote
0answers
29 views
How many primes are there on the form $100\cdots 0 1$? [duplicate]
For example 11 and 101 are primes, but apart from them, can we determine how many primes on the form $100\cdots 00 1$ there exist (in decimal number system)?
-1
votes
1answer
46 views
Prove that Nth prime number is bigger or equal than 3n [closed]
Let $P_{n}$ be the nth prime number. Prove that $\forall n \in N, n \ge 12: P_{n} > 3n$. Tried to use induction here but couldn't get any reasonable relation between $P_{n}$ and $P_{n+1}$.
11
votes
5answers
166 views
Is it true that $n!$ divides $p^n(p+1)(p^2+p+1)\cdots(p^{n-1}+\cdots+1)$?
Let $p$ be a prime number (though I suspect that this might be true for composite ones as well). Define
$$f(p,n)=\frac{p^n(p+1)(p^2+p+1)\cdots(p^{n-1}+\cdots+1)}{n!}$$
where $n$ is a positive integer. ...
0
votes
0answers
12 views
Big-O approximation of probability that the GCD of two large integers is not $\beta$-smooth
For a given $\beta$ and $n$, define $f(\beta)$ as the limit, as $n$ goes to infinity, of the probability that $\gcd(u,v)$ has a prime divisor larger than $\beta$, computed for uniformly random ...
1
vote
1answer
33 views
RSA signature verification with a different modulus
I got a question on RSA signature verification. To verify, we calculate $y^e$ mod n (where y = $x^d$ mod n being the signature) to get x and compare with the original message.
Is it possible to ...
9
votes
2answers
171 views
Can $pk+1$ divide $(p-k)^2$?
Let $p>3$ be a prime, $0<k<p$. Then is it possible that $pk+1\mid(p-k)^2$?
For $k=1$, since $(p-1)^2\equiv(-2)^2\equiv4\pmod{p+1}$, and $p>3$, this is not possible.
And if $pk+1\mid(p-k)^...
1
vote
1answer
59 views
Question regarding $C(n)$ and $B(n)$ in Hanson's proof that $\prod\limits_{p^a \le n} p < 3^n$
In Denis Hanson's proof, he defines two terms:
(1) $B(n)$: which is the Least Common Multiple of $\{1,2,\dots,n\}$
$$B(n) = \prod\limits_{p^a \le n}p$$
(2) $C(n)$: an integer
$$C(n) = \dfrac{n!}{\...
2
votes
0answers
28 views
Is Dirichlet's theorem on arithmetic progressions true for ring of Gaussian integers?
Is Dirichlet's theorem on arithmetic progressions true for ring of Gaussian integers $\mathbb{Z}[i]$?
By Dirichlet's theorem I mean the fact that if some line $an+b$ ($a, b\in Q$ and $n\in\mathbb{Z}$ ...
5
votes
5answers
71 views
The relation between irreducible and primes
Am I right in thinking that the conventional definition of a prime integer (can only be written as itself times $1$ and has no other factors) is actually the definition for irreducible?
Is it true ...
2
votes
0answers
31 views
consecutive prime gaps and explicit bounds
I am aware of the theorem that $p_{n+1} - p_n \leq n^{0.535}$ which is true for all sufficiently large numbers due to Baker, but if i want to make the implicit for all sufficiently large number to ...
1
vote
1answer
80 views
Does the following inequality always hold true?
$$ 0\lt \frac{\sum_{i=n}^{n + P_n - 1} P_i}{P_n \cdot P _{P_n}} \leq 1 $$
Or is there a lower bound bigger than zero? Which I believe not to be the case.
Some basic examples are as follows:
$(1)$
...
6
votes
4answers
82 views
Find the values of $p$ and $q$
If $p^3+p=q^2+q$ where $p$ and $q$ are prime numbers,
Find all the solutions (p, q)
I tried to solve this exercise using that:
$p^2 = -1(\text{mod} \, q)$ and $q = -1(\text{mod} \, p)$;
So: $...
0
votes
1answer
55 views
Show that if $ p\mid n$ then $\phi(np)=p\phi(n)$
The question:
Let $n\in\Bbb N$ and let $p$ be a prime. Show that if $ p\mid n$ then
$\phi(np)=p\phi(n)$.
What I know is:
It is related to Euler's totient function $\phi$
$\phi$($n$)= # of $+$...
4
votes
3answers
151 views
Divisors of $\left(p^2+1\right)^2$ congruent to $1 \bmod p$, where $p$ is prime
Let $p>3$ be a prime number. How to prove that $\left(p^2+1\right)^2$ has no divisors congruent to $1 \bmod p$, except the trivial ones $1$, $p^2+1$, and $\left(p^2+1\right)^2$?
When $p=3$, you ...
1
vote
1answer
135 views
Can the exact number of twin primes $\leq n$ be proved using a “twin-prime zeta function”?
Let $\pi(n)$ denote the amount of primes $\leq n$ and let $\pi_2(n)$ the equivalent for twin primes. Properties of $\pi(n)$ can be proved using a well-known formula involving the zeros of the Riemann ...
4
votes
0answers
72 views
Are there infintely many primes generated by the recursion $c_{n+1} = \lceil \frac{3}{2} c_{n} \rceil$?
Inspired by a recent discussion (How to solve a ceiling expression or recurrence equation?) I stumbled on the question:
Are there infinitely many primes in power ceiling series?
If not there must ...
9
votes
2answers
241 views
Numbers of the form $m^2+2^n$
I would like to show that there are infinitely many primes $p$ such that every number is congruent to $m^2+2^n$ modulo $p$ for some positive integers $m,n$.
This is what I have tried so far: if 2 is ...
1
vote
2answers
45 views
Interesting numbers $n$ such that $x^n-1=(x^p-x+1)f(x)+pg(x)$
I'm dealing with the test of the International Mathematics Competition for University Students, 2011, and I've had a lot of difficulties, so I hope someone could help me to discuss the questions.
I'...
1
vote
0answers
20 views
Sequence of consecutive integers [duplicate]
I want to prove the following:
Let $m_0,...m_r$ be pairwise coprime integers . Show that there exists a sequence of consecutive integers $s, s+1,...,s+r$ such that $m_i\vert s+i, i =0,...,r$
I know ...
1
vote
4answers
45 views
Prove that $2^q+q^2$ is divisible by 3 where $q$ is a prime and $q\geq5$. [duplicate]
I'm looking to prove that $2^q+q^2$ is divisible by $3$ where $q$ is a prime such that $q\geq5$.
I know that primes greater than five will be congruent to either $1\ (\text{mod}\ 3)$ or $2\ (\text{...
1
vote
0answers
27 views
About $ \beta_a^b(n) = \sum_{i=2}^n (-a)^{\omega(i)} \space \omega(i)^b $ where $\omega$ is prime omega function.
Let $\omega(n)$ count the number of distinct prime factors of the integer $ n > 2$. This $\omega(n)$ is called the prime omega function.
Consider
$$ \beta_a^b(n) = \sum_{i=2}^n (-a)^{\omega(i)} \...
1
vote
2answers
31 views
Invertible elements $\mathbb{Z} / p^2 \mathbb{Z}$
Let $p$ be a prime. We are curious about the invertible elements of the quotient ring $\mathbb{Z} / p^2 \mathbb{Z}$. What we do know is that according to the Euler totient function there are $\phi (p^...
2
votes
0answers
43 views
Having trouble with Lemma 3 of Hanson's proof that $\prod\limits_{p^a \le n} p^a < 3^n$
I have been going through Hanson's proof (page 33-37) and I was following it up until Lemma 3.
There, Hanson does a magic trick which I am not clear on.
Here is the step:
$$\frac{(n/a_i)^{n/a_i}}{((...
1
vote
0answers
38 views
Efficient Reduction of $q\mod k2^n+1$?
In the Lucas Lehmer Primality Test, the following identity is used:
$q\equiv (q\mod 2^n)+\lfloor\frac{q}{2^n}\rfloor(\mod 2^n-1)$.
This allows the modulus operation to converge with only addition ...
3
votes
4answers
36 views
Divisibility in polynomial equations
Let $p$ be a prime number. Let $a, b$, and $c$ be integers that are divisible by p such that the equation $x^3 + ax^2 + bx + c = 0$ has at least two different integer roots. Prove that c is divisible ...
