Articles of multiplicative function

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 […]

What is known about these arithmetical functions?

Let $n=\prod_p p^{c_p}$, $N\in \mathbb N$ and $$ \alpha_N(n)=\prod_p p^{c_p \bmod N}. $$ The function $\alpha_N$ is multiplicative since $\alpha_N(n)\alpha_N(m)=\alpha_N(nm)$ for co-prime $n$ and $m$ and completely multiplicative for a subset of $\mathbb N$. Further let $$\log \alpha_N(n)= A_N(n)=\sum_p (c_p \bmod N) \log p. $$ It also reminds me to a sum of an adapted […]

Very elementary proof of that Euler's totient function is multiplicative

Well, I know two or three proofs of this fact $$\gcd(m,n)=1\implies \varphi(mn)=\varphi(m)\varphi(n)$$ where $\varphi$ is the totient function. My problem is this: I’d like to explain this to some gifted children. The children are gifted enough to understand some basic facts, like the reason why $\varphi(n)$ is even ($k$ and $n$ are coprime $\iff$ $n-k$ […]