All Questions
38 questions
66
votes
3
answers
6k
views
Chebyshev polynomials of the first kind and primality testing
Can you provide a proof or a counterexample for the claim given below ?
Inspired by Agrawal's conjecture in this paper and by Theorem 4 in this paper I have formulated the following claim :
Let $...
- 2,661
65
votes
6
answers
14k
views
What is the simplest proof that the density of primes goes to zero?
By density of primes, I mean the proportion of integers between $1$ and $x$ which are prime. The prime number theorem says that this is asymptotically $1/\log(x)$.
I want something much weaker, namely ...
- 4,164
32
votes
3
answers
8k
views
Ideas in the elementary proof of the prime number theorem (Selberg / Erdős)
I'm reading the elementary proof of prime number theorem (Selberg / Erdős, around 1949).
One key step is to prove that, with $\vartheta(x) = \sum_{p\leq x} \log p$,
$$(1) \qquad\qquad \vartheta(x) \...
- 587
20
votes
3
answers
3k
views
What is the simplest proof that the density of coprime pairs does not go to zero?
By density of coprime pairs, I mean the proportion of pairs integers between $1$ and $x$ which are coprime.
This is known to be asymptotically $1/\zeta(2)$.
I want something much weaker, namely that ...
- 19k
17
votes
2
answers
1k
views
Are [Wieferich] primes the only solutions to the equation $2^{k-1} \equiv 1 \pmod{k^2}$?
While studying a certain Diophantine equation in the squarefree integer $k \ge 2$, I believe I have proven the necessary restriction
$$2^{k-1} \equiv 1\!\!\pmod{k^2}. \qquad(\star)$$
Based on what ...
- 1,055
17
votes
0
answers
891
views
An elementary proof that, for every fixed $n \in \mathbf N^+$, there are infinitely many primes $\equiv -1 \bmod n$
This morning, I made a comment to a comment to a question of Ayman Moussa, only to point out that, among many others, there is an elementary proof of Dirichlet's theorem on the existence of infinitely ...
- 10.5k
14
votes
1
answer
1k
views
Nonstandard proofs of the fundamental theorem of arithmetic
Thirty or so years ago, someone showed me a clever proof of the Fundamental Theorem of Arithmetic that did not make use of the lemma "If $p\mid ab$ then $p\mid a$ or $p\mid b$". I'm unable ...
- 19.7k
13
votes
2
answers
2k
views
Is Gauss's generalization of Wilson's theorem non-superficially related to the classification of moduli for which primitive roots exist?
Wilson's theorem (actually proven by Lagrange) from elementary number theory states that: If $n\ge 2$ is an integer, then
$$
(n-1)! \equiv
\begin{cases}
\hfill -1 \pmod {n} &\text{ if } n \...
- 2,075
13
votes
3
answers
1k
views
At what point would an elementary generalization of Bertrand's Postulate be interesting?
I know that in 1952 Jitsuro Nagura was able to show that there is always a prime between $k$ and $\frac{6k}{5}$ for $k > 24$.
At what point would an improvement on Nagura's result be interesting? ...
- 1,049
12
votes
1
answer
391
views
A set of prime numbers
Consider a non-empty set $S$ of primes, with the property that, for every finite subset $S'\subset S$, all the primes dividing $\left(\prod_{k\in S'}k\right)+1$ are in $S$.
For instance, it can ...
- 1,096
11
votes
2
answers
911
views
Primality test for specific class of Proth numbers
Can you provide a proof or a counterexample for the following claim :
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)$
Let $N=k\cdot 2^n+1$ such ...
- 2,661
10
votes
0
answers
633
views
Primality testing using Chebyshev polynomials
Can you provide a proof or a counterexample for the claim given below?
Inspired by an alternative definition of the Frobenius primality test which is given in this paper I have formulated the ...
- 2,661
7
votes
1
answer
462
views
Primality test for $N=2^a3^b+1$
Can you prove or disprove the following claim:
Let $N=2^a3^b+1$ , $a>0 , b>0$ . If there exists an integer $c$ such that $$c^{(N-1)/3}-c^{(N-1)/6} \equiv -1 \pmod{N}$$ then $N$ is a prime.
You ...
- 2,661
7
votes
2
answers
636
views
How to use the Prime Number Theorem in order to prove Selberg's Formula?
I`m reading Melvin B. Nathanson's "Elementary Methods in Number Theory"
and I can't think of a way of deducing Selberg's formula (9.3) from the prime number theorem.
This is one of the tasks ...
- 129
6
votes
1
answer
826
views
Going beyond the Sylvester and Schur theorem with regard to $x,x+1,\dots,x+n-1$
I was recent reading through Paul Erdos's classic elementary proof of Sylvester-Schur. It occurred me that there is a simple argument that when $x$ is sufficiently large and if $p_i$ represents the $...
- 1,049
6
votes
0
answers
381
views
A possible variant of Zagier's one-sentence proof for Fermat's sum of two squares theorem?
Is it possible to modify Zagier's one-sentence proof of Fermat's sum of two squares theorem (see here) to prove certain non-trivial cases of Jacobi's four-square theorem (see here)?
Let $p$ be a prime ...
- 81
5
votes
1
answer
375
views
What was the first elementary proof that $\pi(x)=o(x)$?
Denote by $\pi(x)$ the number of primes $\leq x$. I'm interested in knowing who came up with the first elementary proof that $\pi(x)=o(x)$.
I know that Chebyshev demonstrated elementarily before ...
- 1,019
5
votes
1
answer
332
views
Conjectured primality test for specific class of $N=k \cdot 6^n+1$
Can you provide a proof or a counterexample for the claim given below?
Inspired by Theorem 5 in this paper I have formulated the following claim:
Let $N=k \cdot 6^n+1$ , $k<6^n$ and $\operatorname{...
- 2,661
5
votes
0
answers
586
views
Primality test for specific class of generalized Fermat numbers
Can you provide a proof or a counterexample for the following claim :
Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ .
Let $F_{p,n}= (2p)^{2^n}+1 $ where $p$ is a prime number ...
- 2,661
4
votes
1
answer
441
views
Two conjectural infinite series for $\pi$
I am looking for a proofs of the following two claims:
Claim 1.
$$\frac{2\pi}{\sqrt{3}}=\displaystyle\sum_{n=1}^{\infty}\frac{(-1)^{\Omega_1(n)}}{n}$$ where $\Omega_1(n)$ is the number of prime ...
- 2,661
4
votes
1
answer
321
views
Primality test for $N=2^mp^n +1$
This question is related to my previous question.
Can you prove or disprove the following claim:
Let $N=2^mp^n+1$ , $m>0 , n>0$ and $p$ is an odd prime . If there exists an integer $a$ such ...
- 2,661
4
votes
1
answer
182
views
Primality test for specific class of $N=8k \cdot 3^n-1$
This question is related to my previous question.
Can you prove or disprove the following claim:
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)$
...
- 2,661
3
votes
1
answer
383
views
Primality test for specific class of $N=k \cdot b^n-1$
This question is successor of Compositeness test for specific class of $N=k \cdot b^n-1$ .
Can you provide a proof or a counterexample to the following claim :
Let $P_m(x)=2^{-m}\cdot \left(\left(...
- 2,661
3
votes
0
answers
1k
views
Formula for $\pi$ involving exponents of Mersenne primes
Can someone provide a proof for the following claim?
$$\pi=\dfrac{S_0S_2}{M_3M_5} \cdot\left(\displaystyle\prod_{p \equiv 1 \pmod{4} } \frac{p}{p-1}\right) \cdot \left(\displaystyle\prod_{p \equiv 3 \...
- 2,661
3
votes
0
answers
372
views
How to prove there is infinite prime numbers of form $5n+3$ without Dirichlet theorem? [closed]
Is there a nice elementary way to prove there is infinite prime numbers of form $5n+3$ (also for $5n+2$) with $n\in \mathbb{N}$?
I know how to do it for primes of form $pn+1$ for any prime $p\geq 3$ ...
- 139
3
votes
0
answers
266
views
Conjectured primality test for numbers of the form $N=4 \cdot 3^n-1$
This is a repost of this question.
Can you provide proof or counterexample for the claim given below?
Inspired by Lucas-Lehmer primality test I have formulated the following claim:
Let $P_m(x)=2^{-m}\...
- 2,661
2
votes
2
answers
707
views
Are simplified elementary proofs if valid interesting to the professional mathematical community [closed]
For the last 10+ years, as a math amateur, I worked nightly on understanding the distribution of primes and the classic results in the history of Fermat's Last Theorem.
I have made numerous mistakes ...
- 1,049
2
votes
1
answer
839
views
Primality test for generalized Fermat numbers
This question is successor of Primality test for specific class of generalized Fermat numbers .
Can you provide a proof or a counterexample for the claim given below?
Inspired by Lucas–Lehmer–Riesel ...
- 2,661
2
votes
1
answer
365
views
Primality test for specific class of $N=8kp^n-1$
My following question is related to my question here
Can you provide a proof or a counterexample for the following claim :
Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\...
- 2,661
2
votes
0
answers
306
views
Conjectured initial values of Inkeri's primality test for Fermat numbers
This is a repost of this question .
Can you provide a proof or a counterexample to the claim given below ?
First , we shall give a definition of the Inkeri's primality test for Fermat numbers :
...
- 2,661
1
vote
1
answer
362
views
Primality test for numbers of the form $4k+3$
Can you prove or disprove the following claim:
Let $n$ be a natural number of the form $4k+3$ , and let $c$ be the smallest odd prime such that $\binom{c}{n}=-1$ , where $\binom{}{}$ denotes a Jacobi ...
- 2,661
1
vote
1
answer
252
views
Another question on strengthening the Sylvester-Schur Theorem
I've found an argument that if valid suggests that there is always a prime $p > n$ that divides ${{x+n} \choose n}$ when $x > \pi(n)$.
As a math amateur, I am always doubtful about my results ...
- 1,049
1
vote
0
answers
127
views
Some property of the greatest prime factor
Let $n$ be a positive integer $\geq 2$ et denote by $ P^{+}(n)$ the greatest prime factor of $n$ my question is as follows:
If $a$ and $b$ are two numbers, is there any method to express or to bound $...
- 1,257
1
vote
0
answers
118
views
A primality criterion for specific class of $N=4kp^n+1$
Can you provide a proof for the following claim:
Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4}\right)^m\right)$ .
Let $N= 4kp^n+1 $ such that $p$ is a prime number greater ...
- 2,661
1
vote
0
answers
93
views
Primality test for specific class of $N=12k \cdot 5^n-1$
Can you provide a proof for the following claim:
Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4}\right)^m\right)$ .
Let $N= 12k \cdot 5^{n} - 1 $ where $n\ge3$ , $12k <5^n$ ...
- 2,661
0
votes
1
answer
374
views
Are there infinitely many $k$ for which $\frac{\sigma(k)}{k}=n^p$ and $p$ is an odd prime? [closed]
I would like to know if there are infinitely many $k$ for which $$\sigma(k)/k=n^p$$ such that $m=k{n}^{p-1}$ with $m,n>0$ and $p$ is an odd prime?
Note: $\sigma(\frac{m}{{n}^{p-1}})$ is the sum of ...
- 414
0
votes
0
answers
123
views
Testing the primality of Mersenne and Fermat numbers using third order recurrence relation
Can you prove or disprove the claims given below?
Inspired by generalization of Lucas-Lehmer test I have formulated the following claims:
Claim 1 Let $M_p=2^p-1$ where $p$ is an odd prime number , ...
- 2,661
-3
votes
1
answer
381
views
Is it true that there are infinite palindromic primes that when squared give palindromic number? [closed]
Can you prove that there are infinite palindromic primes that when squared give a palindromic number?
