0
votes
0answers
91 views

Arithmetic progression and average of two prime numbers

Let $A=(a_n : n \in \mathbb{N})$ be the sequence given by: $$ \ a_n = a_1 + (n - 1)d,\quad a_1,\ d,\ n \in \mathbb N,\quad d\gt a_1,\quad \gcd(a_1,\ d)=1. $$ For all terms of $A$ greater than $\ ...
5
votes
2answers
58 views

How to find an upper bound for $f(n)=\sum_{k=1}^{n}\frac{1}{d^{9}(k)}$?

How to find an upper bound for $$f(n)=\sum_{k=1}^{n}\frac{1}{d^{9}(k)}$$ where $d(n)$ is the divisor function?
0
votes
1answer
34 views

What am I doing wrong with Möbius inversion?

Let $p(n)$ be $1$ if $n$ is a prime, and $0$ otherwise. Recall the prime divisor function. $$w(n)=\sum_{d\mid n}p(d)$$ By the Möbius inversion formula, we have $$p(n)=\sum_{d\mid n}w(d)\mu ...
1
vote
1answer
214 views

Is there a formula for Merten's function $M(x)=\sum_{n\leq x}\mu (n)$? [closed]

Is there formula for sum of the Möbius function, $$M(x)=\sum_{n\leq x}\mu (n)?$$
1
vote
2answers
26 views

How to show $\sum_{n\leq x}d(n)=\sum_{ab\leq x}1$?

How to show this equation below is true. $$\sum_{n\leq x}d(n)=\sum_{ab\leq x}1$$ $d(n)$ is the divisior function. It seems easy but i just can't see it.
3
votes
2answers
52 views

$\pi(x)\leq \frac x{f(x)}$ for some unbounded function $f(x)$

Let $\pi(x)$ denote the number of primes $\le x$. Can one prove $$\pi(x)\leq \frac x{f(x)}$$ for some function $f(x)(x\gt0)$, and $f(x)$ is unbounded? Please do not refer to prime number ...
3
votes
2answers
69 views

Number of algebraic integer divisors of an algebraic integer

Let $\alpha$ be an algebraic integer of degree $d$. Let $\tau(\alpha)$ be the number algebraic integers $\beta$ of degree $d$ such that $\alpha/\beta \in \mathbb{Z}$. What is a good upper bound on ...
2
votes
1answer
42 views

In how many ways can a number be factorized over the field $\mathbb{Z}_p$ into two numbers?

For example, over the field $\mathbb{Z}_5$, we can factor number 4 into two numbers in three different ways, i.e. 4=4$\times$1, 4=2$\times$2, and 4=3$\times$3. I am looking for a general formula of ...
3
votes
0answers
53 views

Application of Dirichlet Theorem in AP to elementary number theory problems.

I have learnt this theorem in my class, however, "elementary" examples are very limited. (focusing more on analytic machinery) Are there any interesting applications to elementary number theory that ...
1
vote
1answer
37 views

Changing order of summation with Mobius function

Let $\mu(d)$ be the Mobius function, and $\mu_r(d)$ be the modified Mobius function which satisfies $\mu_r(d)=0$ if $d$ has strictly more than $r$ distinct prime factors. Let $\psi_r(n)=\sum_{d\mid ...
4
votes
2answers
69 views

Squares modulo 2^n

How many squares are there modulo $2^n$? If we would deal with $p^n$, where p an odd prime, then we could use Hensel's Lemma, which clearly doesn't work with $2^n$.
1
vote
1answer
47 views

Rational vs irrational

If two points on a number line is shown, are rational numbers between the two points is more or irrational number is more ? I have tried using probability , my collegue who was like my teacher also ...
0
votes
1answer
33 views

Equation with a sum for the prime-counting function involving the Mobius function

I have come across the statement that $$ \sum_{n\leq x}\sum_{d\mid(n,P_z)}\mu(d) = \sum_{d\mid P_z}\mu(d) \left[\frac{x}{d}\right], $$ where $P_z=\prod_{p\leq z}p$ where $p$ is prime, $\mu(d)$ is the ...
5
votes
2answers
292 views

Applications of generating functions to number theory

I am familiar (at least at a cursory level) with the extensive role generating functions play in the theory of partitions. What are some other prominent applications of generating functions to number ...
1
vote
1answer
53 views

Euler totient function sum of divisors. Theorem 2.2 Apostol

Prove that : $If $ $ n\ge{1} $ $ \sum_{d|n}\phi(d)=N $ $ N \in{\mathbb Z} $ Let S denote the set {1,2,...,n}. We distribute the integers of S into disjoint sets as follows. For each divisor d ...
5
votes
1answer
57 views

Sum of a certain series related to the primes

It is well known that $$\sum_{n > 0}\frac{1}{n}$$ diverges, but $$\sum_{n > 0}\frac{1}{n^2} = \frac{\pi^2}{6}$$ converges. Similarly, $$\sum_{p}\frac{1}{p}$$ diverges, but $$\sum_{p} ...
3
votes
0answers
51 views

Question about the first step in Mann's original proof of the Schnirelmann-Landau Conjecture

I was reading Henry Mann's proof for the Schnirelmann-Landau Conjecture from 1942 which can be found in JSTOR here Today, the Schnirelmann-Landau Conjecture is known as Mann's Theorem: $$d(C) \ge ...
2
votes
1answer
46 views

Trying to understand an assumption in the proof of Mann's Theorem

I am trying to follow the reasoning in the proof of Mann's Theorem: $$d(C) \ge \min(d(A)+d(B),1)$$ I am clear that we can assume that: $d(A) + d(B) \le 1$ We only need to prove that for every $n \ge ...
2
votes
1answer
22 views

Reasoning about Schnirelmann Density: Proving that $d(C) \ge d(A) + d(B)$

I am taking this argument from Gelfond & Linnik's Elementary Methods in the Analytic Theory of Numbers. They state if for every $n \ge 1$, there exists $m \in [1,n]$ where $C(n) - C(n-m) \ge ...
1
vote
1answer
20 views

Question about Schnirelmann Density and Sumset: if $d(A) \ge \frac{1}{2}$ and $d(B) > 0$, wouldn't $d(A+B)=1$

I've been thinking about the Schnirelmann Density and I think that I may still be confused about SumSet and Density. It seems to me that if $d(A) \ge \frac{1}{2}$ and $d(B) > 0$, then $d(A+{B}) = ...
3
votes
1answer
70 views

Schnirelmann Density: if $d(A) + d(B) \ge 1$, does it follow that $d(A+B)=1$

I am still trying to get my head around the basic properties of Schnirelmann Density. If I'm reading PlanetMath.org correctly, it states that if $d(A) + d(B) \ge 1$, then $d(A+B)=1$ Here's the exact ...
2
votes
1answer
33 views

Question about the properties of Shnirelman density

In elementary methods in analytic number theory by Gelfond and Linnik, the claim is made that if $d(A) + d(B) > 1$, then we can find $A',B'$ where $A' \subseteq A$ and $B' \subseteq B$ such that ...
4
votes
1answer
75 views

Prove that $2^x < \prod_{p\le x} p < (13/4)^x$ for sufficiently large x

Prove that $2^x < \prod_{p\le x} p < (13/4)^x$ for sufficiently large x. Here $p$ is prime. So if we take logs we need to show for sufficiently large x, $x\log 2 < \sum_{p\le x}\log p < ...
0
votes
0answers
40 views

Looking for help understanding the proof behind Schnirelmann Theorem: $d(A+B) \ge d(A) + d(B) - d(A)d(B)$

I am trying to understand the proof by Gelfond & Linnik that: $$d(A+B) \ge d(A) + d(B) - d(A)d(B)$$ Here's what I understand: Let $A$, $B$ be infinite sequences of integers starting with $0$ ...
5
votes
1answer
146 views

How to prove this inequality $\pi(x) > \log x - 1$ involving the prime counting function?

Problem Prove that $\pi(x) > \log x - 1$. Progress Based on a hint and very elementary methods, I got that $$ \prod_{p \leq x} (1-p^{-1})^{-1} \leq \prod_{k=2}^{\pi(x)+1} (1-k^{-1})^{-1}. $$ The ...
1
vote
1answer
55 views

Additive properties of sequences: trying to understand Schnirelmann density

I have started reading Gelford & Linnik's elementary methods in analytic number theory (1965). They define a sequence $A$ of integers as: $$0, a_1, a_2,a_3,\dots$$ where $$0 < a_1 < a_2 ...
3
votes
2answers
128 views

Proving all sufficiently large integers can be written in the form $a^2+pq$.

This is one of those numerous questions I ask myself, and to which I seem unable to answer: Can every integer greater then $657$ be written in the form $a^2+pq$, with $a\in\mathbb Z$ and $p,q$ ...
3
votes
3answers
120 views

What does the integer span of one irrational, and one (possibly irrational) real number look like in $\mathbb{R}$?

My title was rejected a few times, here is what it was initially: If you take two real numbers- one irrational and one possibly irrational - how close does their $\mathbb{Z}$ span come to any ...
1
vote
0answers
36 views

Compute $\phi^{-1}(k)$, $\phi$ Euler's totient function? [duplicate]

Given a positive integer $k$, I'd like to be able to compute the set of positive integers $m$ such that $m$ is prime to precisely $k$ positive integers less than $m$. In other words, I'd like to ...
0
votes
1answer
52 views

Where are the resources on the prime number theorem?

I am looking for resources which explain the prime number theorem to 18 year old students. I am not seeking a proof of the result but something which will have an impact and motivate a student to ...
0
votes
0answers
70 views

Count of numbers with the given prime factors in a range [duplicate]

Given two primes: $p$ and $q$, $p \neq q$ and $n \in N$ find count of numbers $u$, so that $u \leq n$ and $u = p^k q^l$; $k, l \in N$. If we'd given with just one prime $p$ this count would be ...
2
votes
2answers
160 views

Arithmetical functions summation

Problem (7.4.15) of Burton's Elementary Number Theory has been request that prove the following equalities. In this book isn't expressed Dirichlet multiplication and Riemann's zeta function before ...
0
votes
0answers
136 views

How to prove that homometric sets lead to same result in this problem? (any justifications?)

First let me define Difference multiset for a set of integers $$P=\{p_1,p_2, \dots,p_K\} ,\quad p_i \in\{1,2,\dots,N\},\quad p_i\ne p_j $$ as below: $$ D = \{p_i-p_j \mod N ,\quad i \ne j\} $$ I ...
5
votes
0answers
218 views

Maximum length of sequence of non-coprimes of $N$ - least upper bound for Jacobsthal's function

I am looking at the length of the longest sequences of adjacent integers that are not coprime to $N$ for very large $N$. Let $F_N$ be the set of integers less than $N$ which are not coprime with $N$: ...
1
vote
1answer
131 views

Challenging the Chebychev function / prime number theorem?

The prime number theorem accords with the following equation for the first Chebychev function that: $$\lim_{x\rightarrow\infty}\frac{\vartheta(x)}{x}=1 \qquad (1)$$ According to Muñoz García, E. and ...
0
votes
0answers
46 views

How to introduce an integer function into $\zeta$ function instead of $n$

I have a problem that I am struggling with since long and probably it is simple but I can not get through. So your help would be very welcome. Known that Riemann $\zeta$ function is defined as sum ...
5
votes
0answers
114 views

Best upper bound on the number of divisors of $n$ that are larger than $N$.

I am looking for the best upper bound on $$\sum_{\substack{d | n\\ d \geq N}} 1.$$ I know that $$ d(n) = \sum_{\substack{d | n}} 1 \leq e^{O(\frac{\log n}{\log \log n})}. $$ For my application, I ...
2
votes
1answer
62 views

Lemma from arithmetic functions

Let $f$ arithmetic and $$H(f)=\lim_{x\rightarrow \infty}\frac{1}{x\log x}\sum_{n\leq x}f(n)\log n,$$ Then $H(f)$ exists if and only if $M(f)$ exists, and $M(f)=H(f)$ Where $$M(f)=\lim_{x\rightarrow ...
3
votes
1answer
161 views

Proving equivalences between prime counting functions.

If we have that: $$\theta(x)=\sum_{p\leq x}\log p,$$ and $$\psi(x)=\sum_{n\leq x}\Lambda(n)$$ Where $\Lambda(n)=\log p $ if $n=p^m$ and $\Lambda(n)=0$ in another case. How can I prove that : 1) ...
9
votes
1answer
260 views

Sum of square root of primes

I was playing around with prime numbers and a question came into my mind: Let $S(n)$ denote the sum of square roots of primes from $2$ to the $n$th prime number. Are there infinitely many numbers $n$ ...
16
votes
5answers
984 views

Intervals that are free of primes

How can I prove that exists intervals as large as I want that are free of primes? I mean, $\forall \ k \in \mathbb{N}, \exists \ k$ consecutive positive integers none of which is a prime.
1
vote
1answer
197 views

For what primes $p$ does the series $1!+2!+3!+4!+ \cdots $ converge $p$-adically?

this is a question from a book I'm struggling with, please could you provide a clear proof For what primes p does the series $1!+2!+3!+4!+ \cdots $ converge $p$-adically? kind thanks
0
votes
1answer
63 views

For which primes p does the series $\sum_{i=0}^\infty (\frac{10}{11})^i$ converge p-adically

For which primes p does the series $\sum_{i=0}^\infty (\frac{10}{11})^i$ converge p-adically and, when it does, to what limit?
0
votes
0answers
229 views

Show that the field of p-adic numbers is complete

this is a question from a book I'm struggling with, please could you provide a clear proof Show that the field of p-adic numbers is complete i.e. that a sequence of p-adic numbers converges if and ...
0
votes
1answer
78 views

Polynomial that permutes residue classes

Prove that for any integers $d, e > 1$, the polynomial $f$ with integer coefficients permutes the residue classes modulo $p^d$ if and only if it permutes the residue classes modulo $p^e$ where $p$ ...
3
votes
1answer
565 views

Change of order of summation.

I feel like an idiot for asking this, so bear my stupidity. I have the sum $\sum_{n\leq N} \sum_{p | n ; \ p \ prime} 1$, and I want to change the order of summation of these two sums I think it ...
2
votes
1answer
134 views

Sum of exponents equivalent to card(composites less than or equal to x)?

Consider a cousin of the Chebyshev function: $$t(x) = \sum \alpha_i $$ such that $$ p_i^{\alpha_i }= x, \ p_i \leq x$$ I speculated that $ t(x) \sim C(x)$, the composites $\leq(x)$ If $t(x) = ...
1
vote
3answers
291 views

How to prove $\sum_{d|n} {\tau}^3(d)=\left(\sum_{d|n}{\tau}(d)\right)^2$

$\sum_{d|n} {\tau}^3(d)=\left(\sum_{d|n}{\tau}(d)\right)^2$, where $\tau(d)$ designates the number of positive divisors of d. Now I only know that both sides are multiplicative functions, could ...
9
votes
4answers
317 views

Representing a number as a sum of at most $k$ squares

Fix an integer $k >0 $ and would like to know the maximum number of different ways that a number $n$ can be expressed as a sum of $k$ squares, i.e. the number of integer solutions to $$ n = x_1^2 + ...