New answers tagged prime-numbers
16
votes
Approach to Fermat's Last Theorem using group theory
Your strategy cannot work. For any prime $p$ and large enough $m$, $(**)$ will fail for $G_m$, that is, there will be $g\in G_m$ such that $g+1$ in $G_m$. Through your argument in point 4, this ...
- 27.1k
4
votes
Is the product of primes from $n/2$ to $n$ always less than $2^n$?
Let $P_n:=\prod_{p\leq n}p$ denote the product of all primes no greater than $n$. Then
$$\log P_n=\sum_{p\leq n}\log p=:\theta(n),$$
where $\theta$ denotes the Chebyshev function. Then your product ...
- 65.1k
4
votes
Accepted
When is $1+2(p-3)!$ a power of $p?$
Let $p^k -1 =2(p-3)!$ and $ p = 2q+1$.
Since $p > 7$, so $ p \geq 11, q \geq 5$.
Case 1: If $q\geq 5$ is composite.
Show that $(p-1)^2 \mid 2(p-3)!$
Dividing throughout by $p-1$,
$$ p^{k-1} + p^{k-...
- 72.1k
1
vote
Accepted
A family of product formulas for $\pi$ using prime numbers
You can render a value for $f(n)$ whenever $n=2q$ is twice an odd prime, provided that you use signs in $p\pm1$ that conform with the Legendre symbol modulo $q$ and quadratic character of a prime ...
- 42.4k
4
votes
Should Euler be credited with Prime Number Theorem?
Consider $A(x) = \sum\limits_{p\le x} \frac{1}{p}$. Then the Abel summation formula gives $$\pi(x) = x A(x) -\int_2^x A(t) \, dt$$
At this point one can't use $A(x) \sim \log\log x$ to approximate the ...
- 19.4k
14
votes
Accepted
Should Euler be credited with Prime Number Theorem?
The statement $\sum_{p\le x} \frac1p \sim \log\log x$, which was proved by Mertens, is strictly weaker than the prime number theorem (in the sense that we can replace the set of primes by other sets ...
- 85.1k
1
vote
Accepted
Existence of prime numbers close to given integers
In the below paper, it is proved that there exists $n_0\in \mathbb N$ such that, for all $n>n_0$, $$n-p(n)<n^{0.525}.$$
Baker, R.C., Harman, G. and Pintz, J. (2001), The Difference Between ...
- 79.8k
5
votes
Accepted
Is it possible to prove that iterating this hailstone-resembling algorithm will always end in $1$?
There are divergent sequences that will never reach $1$, for example starting from $78558$.
These can be constructed from Sierpiński numbers - integers $N$ such that $N2^n+1$ is composite for all $n\...
- 17.3k
1
vote
Is it possible to prove that iterating this hailstone-resembling algorithm will always end in $1$?
Is it possible to prove that iterating this hailstone-resembling algorithm will always end in $1$?
Even if it is possible, it is very hard. Indeed, let $m$ be any natural number. The sequence ...
- 95.6k
2
votes
Generating random prime numbers using the $6x\pm 1$ identity
Related is the problem of identifying whether a collection of bits has the proper form $6k\pm1$.
Clearly the units bit must be $1$ since the number must be odd. Now to check the residue modulo $3$, ...
- 42.4k
2
votes
Accepted
Generating random prime numbers using the $6x\pm 1$ identity
Let $r$ be a random number with $K-1$ bits (so $0 \le r \le 2^{K-1} - 1)$ and $s$ = either $(-1)^b$ where $b$ is a 1-bit random number.
Let $q = 6r + s$ be a potentially prime number. Then $-1 \le q \...
- 16.2k
2
votes
Let $p_n$ denotes the $n$-th prime. There are at least $p_n- 1$ primes between $p_n$ and $\prod_{k=1}^n p_k$·
One can finish this elementarily. Note that $\prod_{r=1}^n p_r = p_n\#$.
Claim $1$: $\pi(p_n\#) \geq \pi(p_n^2)$ for $n \geq 3$.
Proof: Recall that for $n\geq 2$, $p_n\# -1$ has prime divisors none ...
- 3,796
1
vote
If prime $p=a_n10^n+a_{n-1}10^{n-1}+\ldots+a_110+a_0$ then $f(x)=a_nx^n+\ldots+a_0$ is irreducible in $\mathbb{Z}[x]$
Can someone help me figure out why the hint is true?
The hint given is "Show that $f(x)$ takes on infinitely many prime values". Well, this is an open problem called Bunyakovsky conjecture. ...
- 17.3k
1
vote
Understanding a bound on number of primes congruent with $a$ mod $q$
Let $\mathbb{P}$ be the set of primes. For the first expression, use Abel's summation formula and integration by parts $$\pi\left(x,q,a\right)=\sum_{2\le n\le x}\log n\cdot\mathbb{1}_{\left\{ p\in\...
- 99
-1
votes
Let $p_n$ denotes the $n$-th prime. There are at least $p_n- 1$ primes between $p_n$ and $\prod_{k=1}^n p_k$·
Maybe a simpler solution would be to use so called "Bertrand Theorem" that is that there is at least one prime between $n$ and $2n$. That is, check the inequality for $n=2$" and then ...
- 127
1
vote
Let $p_n$ denotes the $n$-th prime. There are at least $p_n- 1$ primes between $p_n$ and $\prod_{k=1}^n p_k$·
Note that for $n=1,2$ the statement fails, so we only consider $n\ge3$. We can check manually that it holds for $n=3$ and assume from now on that $n\ge4$. By utilizing the bound (see a short and ...
- 99
0
votes
broader meaning of twin prime constant?
If $a_2 - a_1 = 2$ you are essentially counting some prime twins in a given interval.
Consider $i > \sqrt n $
If $i = a_1 \mod p$ for all $p< \sqrt n$ with $a_1 \neq 0$ then $i$ is a prime.
Then
...
- 16.6k
2
votes
Understanding a bound on number of primes congruent with $a$ mod $q$
By the definition of $\theta,$ as $t$ increases the expression for $\theta(t,q,a)$ jumps up by the amount $\log t$ each time when $t$ crosses another prime that satisfies the congruence condition. ...
- 2,460
1
vote
Accepted
Reasoning about reduced residue systems as a generalization from prime gaps
Let $n<x$ be any natural numbers. Then the ordered list of natural numbers relatively prime to $p_n$ is $(1,2,\dots)$ with the multiples of $p_n$ removed. Thus the $c_{n,i}$'s divisible by $p_x$ ...
- 95.6k
2
votes
When and how does a rational prime (not ideal!) reduce in a given number field?
The answer to your question is indeed not easy and is subject to still ongoing research, compare for example http://faculty.fairfield.edu/pbaginski/Papers/FactoringAlgIntegersMonthly.pdf
The reason is,...
1
vote
Sum of residues $\sum_{s=1}^{n-1} r_s$
Claim: $$n \text{ prime} \iff S’ := \sum_{a=1}^{n-1} \sum_{b=1}^{n-1} ab \bmod n = \frac{n(n-1)^2}{2} $$
Proof: $\implies$
$$S’= \sum_{a=1}^{n-1} \sum_{b=1}^{n-1} ab \bmod n \overset{(1.1)}{=} \sum_{...
- 3,796
3
votes
Accepted
Sum of residues $\sum_{s=1}^{n-1} r_s$
For simpler algebra, let
$$d = \gcd(m, n), \;\; m = m^\prime d, \;\; n = n^\prime d, \;\; \gcd(m^\prime, n^\prime) = 1$$
We have for $0 \le s \le n - 1$ that
$$sm = \left\lfloor\frac{sm}{n}\right\...
- 50.5k
1
vote
Are there any primes that satisfy the third iteration of this process?
The smallest sprime$_3$ is
\begin{align*}
31571389&=15785689+15785699+1\\
&=(7892831+7892849+1)+(7892849+7892873+1)+1
\end{align*}
where
\begin{align*}
7892831&=3946403+3946421+1\\
7892849&...
- 85.1k
1
vote
Accepted
$\Delta U = U - U$ elementwise = $2R$ for every UFD $R$ and its group of units $U$. Or there is some formula...
Does this mean as well that $\Delta U \simeq \prod_{i\in I} \Delta U_i'$ as sets?
Yes. It helps to think about elements of $U \simeq \prod_{i\in I} U_i'$ as vectors of length $|I|$ with ordinary ...
- 10.9k
2
votes
Accepted
Gamma is multiplicative with Zeta - Is there an additive version?
Yes $$I(s)=2\sum_{n\in \Bbb N} \int_{J=(0,n^{-s/2})} e^{\frac{\log^2({n^{s/2}})}{\log t}}~dt$$
and $$ f(s)=\sum_{n\in \Bbb N} \log n~K_1(s\log n)$$
where $K_1$ is the modified Bessel function.
Here's ...
- 104
0
votes
The square roots of different primes are linearly independent over the field of rationals
I would like to record another solution, close to the one given by Bill Dubuque. The goal is to show that
$$\hbox{dim}_{\bf Q} {\bf Q}[\sqrt{r_1},..., \sqrt{r_n}] = 2^n$$
if no $r_i$ or products of ...
- 6,010
3
votes
Product formula for $\dfrac{4}{\pi}$
Experimental data suggests that the product converges, but to a value less than $4/\pi$. I computed the product for the first $1.8 \times 10^9$ primes. The results are as follows:
Upto $2 \times 10^...
- 21.5k
2
votes
Understanding partial summation with primes numbers
Here is my attempt and I obtain the same result as you (modulo the sign): by putting
$$ S(y) := \sum_{p<y} \frac{a_p}{p} = -\log(y) + \mathcal{O}(1),$$
we have
\begin{align*}
\sum_{p<\sqrt{x}} \...
- 341
1
vote
Accepted
Carmichael Numbers sample test data
Note that
$(6k+1)(12k+1)(18k+1)$
is never prime. You want to check if each of the factors is prime.
Here’s some PARI/GP code to generate a Carmichael number of the desired form larger than a given ...
- 32.4k
1
vote
How random is the modulus of a large semiprime number?
You’ve already observed that the semi prime will be odd, and you can use this to shave off one bit. You can do the same trick with the first few primes (I think the first 233 primes) where you store ...
- 32.4k
3
votes
Product formula for $\dfrac{4}{\pi}$
As something of a ground rule, we might require the factors to be listed in order of increasing value of the prime, so that the different residues $\bmod 5$ are mixed together and thus cancel out, by &...
- 42.4k
0
votes
Bounds for the Prime Zeta function
By partial summation we have $$\sum_{p\leq x}\frac{1}{p^{s}}=\sum_{n\leq x}\frac{1_{p}}{n^{s}}=\frac{\pi\left(x\right)}{x^{s}}+s\int_{1}^{x}\pi\left(t\right)t^{-s-1}dt$$ so $$\sum_{p\in\mathbb{P}}\...
- 32.8k
1
vote
Finding Twin primes Such That Their Sum + 1 is Also Prime
I can't provide a necessary condition for OP's query, but I can provide a sufficient one. If $(p,p+2)$ are twin primes, then $2p+3$ will be prime if $(2p+1,2p+3)$ are also twin primes. This might seem ...
- 7,523
3
votes
What is the expected size of primes sampled uniformly at random from the set of first $2^n$ primes?
Let $x$ be the $2^n$th prime. Then the expectation in question is precisely
$$
\frac1{2^n} \sum_{p\le x} \log_2 p = \frac1{2^n\log 2} \sum_{p\le x} \log p.
$$
By the prime number theorem, the latter ...
- 85.1k
1
vote
How many coprimes to $n$ are also prime?
From the above comments it seems like OP wants a closed form answer. There are no known exact and useful closed formula for $\pi(x)$ and $\omega(x)$. So you will not have a formula that gives you the ...
- 21.5k
2
votes
How many coprimes to $n$ are also prime?
If $\pi (x)$ be the prime counting function and $\omega (x)$ be the prime omega function (that counts the number of distinct prime factors) then what you want is $\pi (n) - \omega (n)$ - this is ...
- 97
0
votes
If $a, b, c, d$ are natural numbers, such that, $ab = cd$, prove that $a^2 + b^2 + c^2 + d^2$ is a composite number.
Consider, $a^2+b^2+c^2+d^2$
by using completing the square method we get
$(a+b)^2+(c-d)^2 =(a-b)^2+(c+d)^2$
Where $ab=cd$ , $a>b$ & $c>d$
Fermat's two square theorem : Every prime of the ...
- 67
Top 50 recent answers are included