All Questions
Tagged with elementary-proofs nt.number-theory
92 questions
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
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
6
votes
0
answers
380
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
6
votes
1
answer
346
views
Integrality of a quotient of Fermat numbers
I try to prove that for every positive integers $m\ge n$, the following product is an integer:
$$\prod_{k=0}^{n-1}\frac{2^{2^m}-2^{2^k}}{2^{2^n}-2^{2^k}}.$$
But no luck.
- 3,998
7
votes
0
answers
274
views
Simple/Elementary derivation of Ramanujan's continued fraction for Hurwitz $\zeta(3,x+1)$
I came across this MSE post discussing a certain continued fraction for $\zeta(3)$ (more specifically, the Hurwitz zeta function $\zeta(s,z)$ at $s=3$) due to Ramanujan. I asked the original poster ...
- 831
4
votes
0
answers
235
views
A combinatorial proof for equality of two $q$-series
Consider the following two $q$-series
\begin{align*}
f(q):&=\sum_{k=1}^{\infty} \frac{(-1)^{k-1}(1 + q^k)\,q^{\binom{k + 1}2}}{(1 - q^k)^2} \qquad \text{and} \\
g(q):&=\frac1{\prod_{j=1}^{\...
- 43.2k
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 ...
- 18.8k
1
vote
1
answer
117
views
Product/quotient of factorials beget dyadic powers
I am writing up some notes and the following occurred to me and I would like to see if there are a variety of ways to prove it. Just for reference, the identity pops out of equality between constant ...
- 43.2k
21
votes
4
answers
4k
views
What is the difference between elementary and non-elementary proofs of the Prime Number Theorem?
There is an easy proof of the PNT, just in a few lines, in the book by Julian Havil, "Gamma", pages 201-202. Specifically, Von Mangoldt's formula, which is very easy to derive:
$$
\psi(x) = ...
- 221
8
votes
3
answers
488
views
Equation $wxyz(w+x+y+z)=1$ in $\mathbb{Q}_+^4$
In this thread on Math.SE, Noam D. Elkies give the following parametric family of solutions in $\mathbb{Q_+}^3$ of the equation $xyz(x+y+z)=1$ (found by Euler) :
$$
x = \frac{6 t^3 (t^4-2)^2} {(4 t^4 +...
- 655
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
4
votes
0
answers
140
views
Factorization in the ring of integers of a particular biquadratic number field, and questions about norms
Consider the number field $K={\mathbb Q}[\sqrt{2},\sqrt{3}]$ and its ring of integers ${\mathcal O}_K$. I have been doing some calculations with this number field as a toy example, to see what can be ...
- 25.8k
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
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
1
vote
0
answers
94
views
How to estimate the highest power of 2 in the partial sum of 2-adic $\log(-1)$ (i.e. $\sum_{i=1}^n\frac{2^i}{i}$)?
The estimate I wanna get is $$v_2(\sum_{i=1}^n\frac{2^i}{i})\geq\min_{t\geq n+1}\{t-v_2(t)\}\tag{*}$$
where $v_2$ is the 2-adic valuation, that is the highest power of 2 defined on $\mathbb{Q}$.
Set $$...
user178596
2
votes
1
answer
154
views
Stability estimates on quotients of the form $ \frac{\prod_{j=1}^n a_j}{\prod_{j=1}^n b_j} $
Suppose that $a_j,b_j \in \mathbb C$ are complex numbers, $j=1,\dots,n$, with the property that $|a_j|,|b_j| \geq c > d >0$ where $c,d$ are positive real numbers. I'm interested in the stability ...
- 173
1
vote
1
answer
183
views
A binomial convolution of Catalan numbers vs "utterly odd numbers"
An integer is called utterly odd if the terminal string of $1$’s in its binary representation has odd length. A number $2^{k+1}m+(2^k-1)$ where $m\geq0$ (every non-negative integer has this form) is ...
- 43.2k
1
vote
1
answer
519
views
A new perspective on Lehmer's totient problem
Lehmer's totient problem asks if there are any composite integers $n$ with $\phi(n) \ | \ n-1$.
It is known that any such $n$ must be odd. It must also be a charmichael number.
Assume $n=4m+3$ then $\...
- 319
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
14
votes
2
answers
1k
views
Euclid-style proof of Dirichlet’s theorem on primes in certain arithmetic progression
The well-known theorem of Dirichlet on primes in arithmetic progression states that given coprime natural numbers $a\le q$, there are infinitely many prime numbers congruent to $a\pmod q$. The ...
- 1,453
0
votes
0
answers
183
views
A certain Pell Equation
Recently I came up with a positive solution $((x,y)\neq (\pm 1;0))$ to this diophantine equation
$$
x^2-\left(w^2(2^{n-2}p)^2+2^n(2^{n-2}p)\right)y^2=1,\qquad n\geq 2,
$$
where all variables are in $ ...
- 785
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
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
2
votes
1
answer
256
views
Sign changes of a sequence
Let $f$ be an arithmetical function. Suppose that $f(n)>0$ if $n$ is in an integer set $A$ and that $f(n)<0$ for another integer set $B.$ Is there a result from number theory or an elementary ...
- 1,257
3
votes
1
answer
154
views
Arithmetical function comparable to sine function [closed]
I was wondering if there exists or can we construct (using known arithmetic functions) an arithmetical function that has the same behaviour of the function sine or comparable to it (I mean that ...
- 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
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
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
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
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
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
3
votes
0
answers
660
views
While solving the 1988 IMO problem 6, I have questions about new solutions without using Vieta Jumping [closed]
I think most of you may know the well-known problem:
"Let $x$ and $y$ be positive integers such that $xy + 1$ divides $x^{2} + y^{2}$. Show that $\frac {x^{2} + y^{2}}{xy + 1}$ is the perfect ...
- 39
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
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
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
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
1
vote
3
answers
248
views
Perfect squares between certain divisors of a number
Let $n$ be a positive integer. We will call a divisor $d(<\sqrt{n})$ of $n$ special if there exists no perfect squares between $d$ and $\frac{n}{d}$. Prove that $n$ can have at-most one special ...
- 19
-2
votes
1
answer
168
views
Diophantine equation $10^n-a^3-b^3=c^2$
Consider the Diophantine equation:
$10^n-a^3-b^3=c^2$, for $a$, $b$, $c$, and $n$ positive.
Has this equation infinitely many solutions?
0
votes
0
answers
165
views
Some questions in a paper by E. H. Neville (1949) about Farey series?
I am reading the paper
MR0029924: Neville, E. H. The structure of Farey series. Proc. London Math. Soc. (2) 51, (1949). 132–144. (Reviewer: W. H. Simons)
and by now two questions raised for me;
...
- 841
1
vote
0
answers
112
views
The $p$-adic valuation of powers of consecutive integers
Let $n > 0, K > 0$ integers and, for $i \in \{1,...,n\}$, let $k_i$ and $l_i$ be integers such that $k_i + l_i = K$. Assume that for some $i,j \in \{1,...,n\}$ we have $k_i \neq k_j$.
Claim: ...
- 365
4
votes
2
answers
593
views
Squares in Lucas sequences
Good night, everyone!
According to a celebrated result by J. H. Cohn, the only perfect squares in the Fibonacci sequence are $F_{0}=0$, $F_{1}=F_{2}=1$, and $F_{12}=144$. It is also known that the ...
- 87
3
votes
0
answers
265
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
7
votes
2
answers
451
views
A set, product of any two elements minus one is a perfect square
The first problem of IMO 1986 asks the following:
Prove that, one can find two distinct $a,b$ in the set $\{2,5,13,d\}$ such that $ab-1$ is not a perfect square.
Note that, this proves, for the ...
- 1,096
11
votes
1
answer
619
views
Diophantine equation $3^a+1=3^b+5^c$
This is not a research problem, but challenging enough that I've decided to post it in here:
Determine all triples $(a,b,c)$ of non-negative integers, satisfying
$$
1+3^a = 3^b+5^c.
$$
- 1,096
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
6
votes
2
answers
1k
views
Products and sum of cubes in Fibonacci
Consider the familiar sequence of Fibonacci numbers: $F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$.
Although it is rather easy to furnish an algebraic verification of the below identity, I wish to see a ...
- 43.2k
13
votes
1
answer
1k
views
Is there an elementary proof that there are infinitely many primes that are *not* completely split in an abelian extension?
I'm currently in the middle of teaching the adelic algebraic proofs of global class field theory. One of the intermediate lemmas that one shows is the following:
Lemma: if L/K is an abelian ...
- 4,279
6
votes
2
answers
788
views
How often does the Mertens function vanish?
It is well known that the Mertens function
$$M(x)=\sum _{n\leq x}\mu(n)$$
has infinitely many zeros, and this seems to be a short proof.
Are there known results about how often the Mertens function ...
- 587
8
votes
4
answers
788
views
Different derivations of the value of $\prod_{0\leq j<k<n}(\eta^k-\eta^j)$
Let $\eta=e^{\frac{2\pi i}n}$, an $n$-th root of unity. For pedagogical reasons and inspiration, I ask to see different proofs (be it elementary, sophisticated, theoretical, etc) for the following ...
- 43.2k
4
votes
2
answers
449
views
Prove that there exists a nonempty subset $ I$ of $ \{1,2,...,n\}$ such that $ \sum_{i\in I}{\frac {1}{b_i}}$ is an integer
Let $ a_1,a_2,...,a_n$ and $ b_1,b_2,...,b_n$ be positive integers such that any integer $ x$ satisfies at least one congruence $ x\equiv a_i\pmod {b_i}$ for some $ i$. Prove that there exists a ...
- 179