Intereting Posts

What is the time complexity of Euclid's Algorithm (Upper bound,Lower Bound and Average)?
Convolution product on the linear dual of the polynomial algebra
What is the rank of the matrix consisting of all permutations of one vector?
$\epsilon{\rm -}\delta$ proof of the discontinuity of Dirichlet's function
On a decreasing sequence of compact subsets of a Hausdorff topological space
Why is the 'change-of-basis matrix' called such?
The centralizer of an element x in free group is cyclic
Finding $f$ such that $ \int f = \sum f$
Induction without a base case
Proof of the following fact: $f$ is integrable, $U(f,\mathcal{P})-L(f,\mathcal{P})<\varepsilon$ for any $\varepsilon>0$
Carmichael number factoring
If $|A| > \frac{|G|}{2} $ then $AA = G $
Exchange order of “almost all” quantifiers
How to reproduce the Mathematica solution for $\int(\cos x)^{\frac23}dx$?
advantage of first-order logic over second-order logic

Let $n \in \mathbb{Z}$ with $n > 0$. Let $F(n) = \sum_{d \mid n} \lambda(d)$. Prove that $$F(n) = \begin{cases}1, \quad \text{if }n \text{ is a perfect square}\\ 0, \quad \text{otherwise} \end{cases} $$

By the Fundamental Theorem of Arithmetic, all $d$’s admit a prime factorization $d=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ for primes $p_i$ and nonnegative integers $a_i$. So $\lambda(d)=\lambda(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k})$. Now the idea is that all the divisors will cancel in pairs of $1$ and $-1$ when $n$ is a perfect square, except the divisor $1$, and so the sum will total $1$. How do I prove this rigorously? If I just choose a generic divisor and write it’s prime factorization I don’t find anything I can generalize. Can you help?

- Building on work from previous MSE question 2306650 (Re: Odd Perfect Numbers)
- prove or disprove that every positive integer is the sum of a perfect square and a prime number or 1
- Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$
- Order of an Element Modulo $n$ Divides $\phi(n)$
- Diophantine Equations : Solving $a^2+ b^2=2c^2$
- How to find positive integer solution of bilinear transformation?

- Applications of Perfect Numbers
- Last digits, numbers
- Prove that for every positive integer, this polynomial is divisible by 24.
- Let $p$, $q$ be prime numbers such that $n^{3pq} – n$ is a multiple of $3pq$ for all positive integers $n$. Find the least possible value of $p + q$.
- Discriminant of a binary quadratic form and Jacobi symbol
- About the property of $m$: if $n < m$ is co-prime to $m$, then $n$ is prime
- Easiest and most complex proof of $\gcd (a,b) \times \operatorname{lcm} (a,b) =ab.$
- An infinitude of “congruence condition” primes?
- Properties of the euler totient function
- Summation involving totient function: $\sum_{d\mid n} \varphi(d)=n$

You can prove it using “multiplicative” property and it’s simple but I just solved it without it and I believe that it’s much more beautiful.

Consider $$n=p_{1}^{a_1} p_2^{a_2} … p_k^{a_k}$$

So $\Omega(n)=\sum a_i$ and $\lambda(n)=(-1)^{\Omega(n)}$

Now $$\sum_{d|n}\lambda(d)=\sum_{d|n}(-1)^{\Omega(d)}$$

So it’s suffices to calculate $D$; the difference of the number of divisor with even $\Omega$ and odd $\Omega.$

Now consider $f(x)=(1+x+x^2+…+x^{a_1})(1+x+x^2+…+x^{a_2})…(1+x+x^2+…+x^{a_k}) $

The coefficient of $x^r$ in above expansion is equal to the number of solutions of this equation:

$$x_1+x_2+…+x_k=r $$

$$0 \le x_i \le a_i$$

which is the number of divisors of $n$ with $\Omega$ equals to $r$.

Hence, $f(-1)=D.$

But $f(-1)$ is $0$ if at least one of $a_i$ is odd and $f(-1)=1$ if $n$ is a perfect square. $Q.E.D$

As a second solution:

It’s easy to check $\lambda=1_{Sq}*\mu $

$[$ Actually the summation has only one term.$]$

Now convolve both sides with the $1$ function [which is inverse of $\mu$]

$$ \lambda * 1=1_{Sq}*\mu*1=1_{Sq} $$

.

- Trouble understanding Sum of Subspaces
- Topology ad Geometry of $\mathbb{C}^n/\mathbb{Z}_k$
- Choosing an advanced group theory text: concerns
- If A is an infinite set and B is at most countable set, prove that A and $A \cup B$ have the same cardinality
- In $\ell^1$ but not in $\ell^2$?
- Expected max load with $n$ balls in $n$ bins?
- Calculate skewness and kurtosis fast
- What is a covector and what is it used for?
- Show that $\left(1+\frac{1}{n}\right)^{n}\geq \sum_{k=0}^n\left(\frac{1}{k!}\prod_{i=0}^{k-1}\left(1-\frac{i}{n}\right)\right)$
- Finding 2 poisoned bottles of wine out of a 1000
- General rule for the integral of $\frac1{x^n}$
- Traces of powers of a matrix $A$ over an algebra are zero implies $A$ nilpotent.
- Show that $\pi =4-\sum_{n=1}^{\infty }\frac{(n)!(n-1)!}{(2n+1)!}2^{n+1}$
- $ \Bbb Q = \Bbb Q $
- Difference between root, zero and solution.