Articles of multiplicative function

Showing $\sum_{d\mid n} \mu(d)\tau(n/d)=1$ and $\sum_{d\mid n} \mu(d)\tau(d)=(-1)^r$

Need some help on this question from Victor Shoup Let $\tau(n)$ be the number of positive divisors of $n$. Show that: $\sum_{d\mid n} \mu(d)\tau(n/d)=1$; $\sum_{d\mid n} \mu(d)\tau(d)=(-1)^r$, where $n=p_1^{e_1}\cdots p_r^{e_r}$ is the prime factorization of $n$. I have tried both of them but cant find any solution!We have to use Mobius Function properties to prove […]

Euler's totient function of 18 – phi(18)

I am trying to find the phi(18). Using an online calculator, it says it is 6 but im getting four. The method I am using is by breaking 18 down into primes and then multiplying the phi(primes) $$=\varphi (18)$$ $$=\varphi (3) \cdot \varphi(3) \cdot \varphi(2)$$ $$= 2 \cdot 2 \cdot 1$$ $$= 4$$

Proof that the euler totient function is multiplicative, correctness?

I’ve tried proving that $\varphi(mn) = \varphi(m)\varphi(n)$ (if $gcd(mn)=1$). The proof I try to setup doesn’t look like the proof I find in textbooks, where am I going wrong? Proof: We try to show that the number of relative primes to $mn$ in $\{1, 2, \ldots , mn-1\}$ is equal to the number of relative […]

How to reformulate a multiplicative formula (with two primes, perhaps like totient-function)?

In the work on another question in MSE I have a formula $f(n)$ whose pattern depending on $n \in \Bbb N$ I want decode into an algebraical formula (see a short rationale of $f(n) at the end). Beginning with the most simple $n$ – namely that which consist of pairs of primes $p,q$ with $n=pq$ […]

Identity in Number Theory Paper

In this paper by Jerry Hu, he defines the function $$f_{s,k,i}\left(u\right)=\prod_{p\mid u} \left(1-\frac{\sum_{m=i}^{k-1}{s \choose m}\left(p-1\right)^{k-1-m}}{\sum_{m=0}^{k-1}{s \choose m}\left(p-1\right)^{k-1-m}}\right)$$ for use in the main theorem. In Lemma 4 (pages 3 & 4), it is claimed that $$\frac{f_{s,k,i}\left(u_{i}\right)}{f_{s,k,i+1}\left(u_{i}\right)}=\sum_{d\mid u_{i}}\frac{\mu\left(d\right){s \choose i}^{\omega\left(d\right)}}{\alpha_{s,k,i}\left(d\right)}$$ for $i=1,2,\ldots k-2$, where $\mu$ is the Möbius function, $\omega\left(d\right)$ is the number of distinct prime factors […]

Bounding this arithmetic sum

I am interesting in bounding the arithmetic sum $$ \sum_{n \leq x} \frac{\mu(n)^2}{\varphi(n)}$$ (The motivation is that this is a sum that comes up a lot in sieving primes, in particular in the Selberg sieve.) It is not too hard to show that this is $\geq \sum_{n \leq x} \frac{1}{n} \approx \log x$, and in […]

For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$

For any positive integer $n$, show that $\sum_{d|n}\sigma(d) = \sum_{d|n}(n/d)\tau(d)$ My try : Left hand side : $\begin{align} \sum_{d|p^k}\sigma (d) &= \sigma(p^0) + \sigma(p^1) + \sigma(p^2) + \cdots + \sigma(p^k) \\ &= \dfrac{p^{0+1}-1}{p-1} + \dfrac{p^{1+1}-1}{p-1} + \cdots + \dfrac{p^{k+1}-1}{p-1} \\&= \dfrac{1}{p-1}\left( (p + p^2 + \cdots + p^{k+1}) – (k+1)\right) \\&= \dfrac{1}{p-1}\left(\dfrac{p(p^{k+1}-1)}{p-1}- (k+1)\right) \\ \end{align}$ […]

A unsolved puzzle from Number Theory/ Functional inequalities

The function $g:[0,1]\to[0,1]$ is continuously differentiable and increasing. Also, $g(0)=0$ and $g(1)=1$. Continuity and differentiability of higher orders can be assumed if necessary. The proposition on hand is the following: If for all integers $t>0$ and for all $r\in(0,1)$, $g(r^{t+1})>g(r)\cdot g(r^t)$, then for all $p,q\in(0,1)$, $g(pq)\geq g(p)g(q)$.

To estimate $\sum_{m=1}^n \Big(d\big(m^2\big)\Big)^2$

How may we estimate $$\sum_{m=1}^n \Big(d\big(m^2\big)\Big)^2$$ where for every positive integer $m$ , $d(m)$ denotes the number of positive divisors of $m$ ?

Optimal multiplying method

Karatsuba gave the optimal way for multiplying two polynomials of degree 1. He reduced the number of multiplications from 4 to 3. Let the imput for $f$ be the degree of a polynomial and the output the number of multiplications needed to multiply two such polynomials. Thus $$f(1) = 3$$ And by iterating $$ f(2^n […]