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

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

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

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)$ 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}$ […]

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)$.

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$ ?

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

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

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

Intereting Posts

Showing $\sum_{i = 1}^n\frac1{i(i+1)} = 1-\frac1{n+1}$ without induction?
Filling an array(Putnam)
Weak-to-weak continuous operator which is not norm-continuous
Difficulty in evaluating a limit: $\lim_{x \to \infty} \frac{e^x}{\left(1+\frac{1}{x}\right)^{x^2}}$
Rank of a cohomology group, Betti numbers.
Proving that every isometry of $\mathbb{R}^n$ is of the form of a composition of at most $n+1$ reflections
The diophantine equation $a^{a+2b}=b^{b+2a}$
Ways for a continuous function to not be smooth
Liouville function and perfect square
Is there any uncountably infinite set that does not generate the reals?
Divisibility by sum of digits
Connected metric spaces with at least 2 points are uncountable.
Minimizing sequence
What are the left and right ideals of matrix ring? How about the two sided ideals?
The king comes from a family of 2 children. What is the probability that the other child is his sister?