Let $ (a_{n})_{n\ge 1}$ be a sequence of positive integers satisfying $ (a_{m},a_{n}) = a_{(m,n)}$ (for all $ m,n\in N^ +$). Prove that for any $ n\in N^ + ,\prod_{d|n}{a_{d}^{\mu (\frac {n}{d})}}$ is an integer. where $ d|n$ denotes $ d$ take all positive divisors of $ n.$ Function $ \mu (n)$ is defined as follows: if $ n$ can be divided by square of certain prime number, then $ \mu (1) = 1;\mu (n) = 0$; if $ n$ can be expressed as product of $ k$ different prime numbers, then $ \mu (n) = ( - 1)^k.$
Problem
Source: Chinese TST 2009 6th P3
Tags: induction, number theory, prime numbers, relatively prime, prime factorization, greatest common divisor, Mobius function
04.04.2009 18:26
I think this problem is a consequence of an Iran TST's problem : exist an integer sequence $ {b_d}$ such that : $ a_n = \prod_{d|n}b_d$ and this problem follows from Mobius inverse function . More than ,we can find $ b_n$ in closed form as follow : Let $ E_n$ be product of $ a_{\frac {n}{d}}$ with d is a square free divisor of n and has an even numbers of prime factors and $ O_n$ be the product of $ a_{\frac {n}{d}}$ with d is a square free divisor of n and has an odd numbers of prime factors then $ b_n = \frac {E_n}{O_n}$
15.01.2010 05:48
here is my solution ,i think it is more simple than the offical one.
Attachments:

25.01.2010 11:30
Dear sholly, You prove that RHS of (*) $ \geq$0. And since we are done. I don't understand. You can explain for me. Thank you.
26.12.2014 16:37
We first prove that the sequence $ a_{n} $ is of the following form: $i)$every $ a_{n} $ is of the form $ kb_{n} $ for all positive integers $ n $ and a certain positive integer $ k $. (this is obvious, because k is the greatest common divisor of all the terms of the sequence a) $ii)$ $ b_{n} $ has the same set of exponents in its prime factorizations the number $n$, but the primes may be different. Moreover, like the sequence of positive integers is generated form the (infinite) set of prime numbers, the sequence $ b_{n} $ should also be generated from a certain set of prime numbers, all of which are relatively prime to the previously arbitrarily chosen positive integer $ k $. Hope this part made sense. Now we prove this claim.
We need to prove that $\prod_{d|n}{a_{d}^{\mu (\frac{n}{d})} }$ is an integer. The case $n=1$ is obvious therefore we will prove the statement for $n>1$. $\prod_{d|n}{a_{d}^{\mu (\frac{n}{d})} = \prod_{d|n}{k^{\mu (\frac{n}{d})}\prod_{d|n}{b_{d}^{\mu (\frac{n}{d})}={k^{\sum_{d|n}{\mu (\frac{n}{d}})}\prod_{d|n}{b_{d}^{\mu (\frac{n}{d})}=\prod_{d|n}{b_{d}^{\mu (\frac{n}{d})}}}}}}}$ because of the well-known identity $\sum_{d|n}{\mu (\frac{n}{d}})=0$ for $n>1$. We can replace $b_{d}$ with $d$ in the product $\prod_{d|n}{b_{d}^{\mu (\frac{n}{d})}}$ without changing its value. This is so, because the product depends only on the exponents of the prime factorization of the numbers $b_{d}$ which is precisely of the same nature as that of the number $d$. This is that we proved above. Therefore we have: $\prod_{d|n}{b_{d}^{\mu (\frac{n}{d})}=\prod_{d|n}{d^{\mu (\frac{n}{d})}}}$ We can switch the roles of $d$ and $\frac{n}{d}$ to obtain: $\prod_{d|n}{d^{\mu (\frac{n}{d})}=\prod_{d|n}{{(\frac{n}{d})}^{\mu (d)}=\prod_{d|n}{{n}^{\mu (d)}\prod_{d|n}{{d}^{-\mu (d)}=\prod_{d|n}{{d}^{-\mu (d)}}}}}}$ where the last equality holds because of the previously mentioned identity (the roles of $d$ and $\frac{n}{d}$ are switched again here). Clearly, it is enough to consider the square-free divisors of $n$. We will prove that this product is an integer with induction on the number of prime factors of $n$. The base of induction is when $n=p$ is prime. Then we have: $\prod_{d|n}{{d}^{-\mu (d)}={p}^{-\mu (p)}{1}^{-\mu (1)}=p}$ Now suppose $n'=pn$ where $p$ and $n$ are relatively prime and $p$ is a prime number. The induction hypothesis states that $\prod_{d|n}{{d}^{-\mu (d)}=R}$ is an integer. We will prove that $\prod_{d|n'}{{d}^{-\mu (d)}}$ is an integer. As suggested above, we will only consider square-free divisors. Indeed, we can partition the set of divisors of $n'$ into two sets of divisors, one set contains the divisors which are relatively prime to $p$ and the other set contains those divisible by $p$. The former ones are red, the latter ones are blue. Note that the product of the induction hypothesis runs over all red divisors of $n'$ and is equal to the positive integer $R$. So, we have: $\prod_{d|n'}{{d}^{-\mu (d)}=\prod_{blue}{{d}^{-\mu (d)}\prod_{red}{{d}^{-\mu (d)}=\prod_{red}{{(pd)}^{-\mu (pd)}\prod_{red}{{d}^{-\mu (d)}=\prod_{red}{{(pd)}^{-\mu (p)\mu (d)}\prod_{red}{{d}^{-\mu (d)}=\prod_{red}{{(pd)}^{\mu (d)}\prod_{red}{{d}^{-\mu (d)}}}}}}}}}}$ The last expression is equal to $\prod_{red}{p}^{\mu (d)}=\prod_{d|n}{p}^{\mu (d)}={p}^{\sum_{d|n}{\mu (d)}}=1$ Therefore our product is always an integer. QED
08.10.2023 17:56
We prove that for every prime number $p$, $$\nu_p(\prod\limits_{d|n}a_d^{\mu(\frac{n}{d})})\geq 0 \qquad(\star)$$ Let $\alpha(n)=\nu_p(a_n)$ for $n\geq 1$, then $(\star)$ is equivalent to $$f(n):=\sum\limits_{d|n}\alpha(d)\mu(\frac{n}{d})\geq 0$$Due to Mobius inversion formula, we know that $$\alpha(n)=\sum\limits_{d|n}f(d)$$ For positive integers $d$ and $x$, define $$S(d,x)=\sum\limits_{k|dx,k \nmid d}f(k)$$Claim: For any positive integer $d$ and coprime positive integers $x,y$, we have $$\min\{S(d,x),S(d,y)\}=0$$Proof of the claim: Apply $\gcd(a_{dx},a_{dy})=a_d$.$\blacksquare$ Now we have the following observation. Lemma: If $S(1,l)=0$ for all $l\mid n$, then $f(n)=0$. Proof of the lemma: Note that if $f(n)\neq 0$, then $f(h)\neq 0$ for some $h\mid n$, $1<h<n$. Apply induction to finish.$\blacksquare$ If $S(1,l)=0$ for all positive integer $l$, $f(n)=0$ would hold for any positive integer $n>1$. Hence we might assume that $S(1,l)$ is not always $0$. Suppose that $u$ is the smallest positive integer such that $S(1,u)>0$. Obviously $u>1$. From the claim we know that $S(1,x)=0$ for all positive integer coprime to $u$, because $S(1,u)>0$. In addition, $S(1,l)=0$ for all positive divisor $l$ of $u$ other than $u$ itself due to the minimality of $u$, indicating that $f(l)=0$ for $l|n,1<l<n$. Observe that for any positive divisor $h$ of $u$ smaller than $u$, $S(h,\frac{u}{h})=f(u)>0$, therefore for any integer $y$ coprime to $u$, $S(h,y)=0$. We wish to show that $f(h\cdot y)=0$ for $h|u,h<u$ and $\gcd(y,u)=1$. Note that above already holds for $h=1$. Then just apply induction on $h$ and use the fact that $S(h,y)=0$. We have so far shown that $$f(n)\neq 0 \quad \text{only if} \quad u\mid n$$Apply the method above for $u\mathbb{Z}$, consider the behaviour of $S(u,x)$ and eliminate the terms $f(k)$ where $u\nmid k$. This would show that there exist a finite or infinite (possibly none) sequence of positive integers $j_0<j_1<\dots$ such that $j_{i-1}|j_i$ for $i>0$, $f(j_i)>0$ and $f$ vanishes at all other positive integer values. Hence $f$ is always nonnegative.