Let $\tau(n)$ be the number of positive divisors of $n$. Let $\tau_1(n)$ be the number of positive divisors of $n$ which have remainders $1$ when divided by $3$. Find all positive integral values of the fraction $\frac{\tau(10n)}{\tau_1(10n)}$.
Problem
Source: 2016 IMO Shortlist N2
Tags: number theory, IMO Shortlist
20.07.2017 00:43
Notice that $\tau_1(3^uw)=\tau_1(w)$ for any $w$ not multiple of $3$ Notice also that $\tau(n) > \tau_1(n)$ for any $n$ multiple of $10$, since $2$ is a divisor of $n$. Then $\frac{\tau(10n)}{\tau_1(10n)}>1$ Notice that $\frac{\tau(10)}{\tau_1(10)}=\frac{4}{2}=2$ Let $m$ be a composite number. Then $m=ab$ for some positive integers $a,b\ge 2$. Take $k=\tau_1(2^{a-1}5^{b-1})$ and $n=2^{a-2}5^{b-2}3^{k-1}$ $\frac{\tau(10n)}{\tau_1(10n)}=\frac{\tau(2^{a-1}5^{b-1}3^{k-1})}{\tau_1(2^{a-1}5^{b-1}3^{k-1})}=\frac{abk}{k}=m$ We will prove that it is impossible to have $\frac{\tau(n)}{\tau_1(n)}=p$ for some prime $p>2$ and $n$ a multiple of $10$ Define a number not divisible by $3$ to be of type $1$ or type $2$ if it leaves a reminder $1$ or $2$ respectively when divided by $3$. Let $T_1(n)$ be the set of divisors of $n$ of type $1$ and $T_2(n)$ be the set of divisors of $n$ of type $2$. So $\tau_1(n)=|T_1(n)|$. Define $\tau_2(n)=|T_2(n)|$. Let $T(n)$ be the set of divisors of $n$ $\mathbf{Lemma:}$ Suppose that $n$ is not divisible by $3$. a) $\tau_1(n)+\tau_2(n) = \tau(n)$ b) If $n$ has no prime divisors of type 1 then $\tau_1(n)=\tau_2(n)$ or $\tau_1(n)=\tau_2(n)+1$ c) If $n=mh$ where all prime divisors of $m$ are type 2 and all prime divisors of $h$ are type 1. Then $\frac{\tau(n)}{\tau_1(n)}=\frac{\tau(m)}{\tau_1(m)}$ $\mathbf{Proof:}$ a) This is trivial, since $n$ doesn't have divisors that are divisible by $3$ b) We will prove that by induction. $\tau_1(1)=1$ and $\tau_2(1)=0$. So it holds for $n=1$. Suppose that $n>1$. Then $n=p^am$ for some $p$ prime of type 2, $a,m\ge 1$ and $m$ not divisible by $p$. By the induction hypothesis $\tau_1(m)=\tau_2(m)$ or $\tau_1(m)=\tau_2(m)+1$ $T_1(n)=\{xy: x\in T_1(p^a), y\in T_1(m)\ or\ x\in T_2(p^a), y\in T_2(m)\}$ and $T_2(n)=\{xy: x\in T_1(p^a), y\in T_2(m)\ or\ x\in T_2(p^a), y\in T_1(m)\}$ Then $\tau_1(n)=\tau_1(p^a)\tau_1(m) + \tau_2(p^a)\tau_2(m)$ and $\tau_2(n)=\tau_1(p^a)\tau_2(m) + \tau_2(p^a)\tau_1(m)$. If $\tau_1(m)=\tau_2(m)$ then $\tau_1(n)=\tau_2(n)=\tau(p^a)\tau_1(m)$ If $\tau_1(m)=\tau_2(m)+1$. Then we have two cases: $a$ even or odd $T_1(p^a) = \{p^x: 0\le x\le a, x\ even\}$ and $T_2(p^a) = \{p^x: 0\le x\le a, x\ odd\}$. If $a=2k$ then $\tau_1(p^a)=k+1$ and $\tau_2(p^a)=k$. $\tau_1(n)=(k+1)\tau_1(m)+k\tau_2(m)=k\tau(m)+\tau_1(m)$ and $\tau_2(n)=(k+1)\tau_2(m)+k\tau_1(m)=k\tau(m)+\tau_2(m)$. Then $\tau_1(n)=\tau_2(n)+1$ If $a=2k-1$ then $\tau_1(p^a)=k$ and $\tau_2(p^a)=k$. $\tau_1(n)=k\tau_1(m)+k\tau_2(m)=k\tau(m)$ and $\tau_2(n)=k\tau_1(m)+k\tau_2(m)=k\tau(m)$. Then $\tau_1(n)=\tau_2(n)$ c) $T_1(n)=\{xy: x\in T_1(m), y\in T(h)\}$. Then $\tau_1(n)=\tau_1(m)\tau(h)$ $T(n)=\{xy: x\in T(m), y\in T(h)\}$. Then $\tau(n)=\tau(m)\tau(h)$ It follows that $\frac{\tau(n)}{\tau_1(n)}=\frac{\tau(m)}{\tau_1(m)}$. Now suppose that $\frac{\tau(n)}{\tau_1(n)}=p$ for some prime $p>2$ and $n$ a multiple of $10$ Let $n=3^uw$ with $w$ not divisible by $3$. By the lemma, we have that $\frac{\tau(w)}{\tau_1(w)} = 2$ or $\frac{2s-1}{s}$ where $s=\tau_1(w)$. Notice that $s=\tau_1(w)>1$ since $1$ and $10$ are divisors of $w$ $\frac{\tau(n)}{\tau_1(n)}=\frac{(u+1)\tau(w)}{\tau_1(w)}=2(u+1)$ or $\frac{(u+1)(2s-1)}{s}$ $p$ is not even, then $p=\frac{(u+1)(2s-1)}{s}$, then $ps=(u+1)(2s-1)$. $s$ and $2s-1$ are coprime, then $2s-1$ divides $p$, then $p=2s-1=\tau(w)$. However, $w$ is multiple of $10$, then $(a+1)(b+1)$ divides $\tau(w)$ where $w=2^a5^bv$, $v$ coprime with $10$. Then $\tau(w)$ can't be prime. Contradiction! Then the proof is complete, and all posible values of $\frac{\tau(10)}{\tau_1(10)}$ are $2$ and all composite numbers
20.07.2017 03:14
Let $10n=3^\alpha p_1^{\beta_1}\dots p_r^{\beta_r}\underbrace{q_1^{\gamma_1}\dots q_s^{\gamma_s}}_{=:m}$ where $r\ge 0$, $s\ge 2$, $\alpha\ge 0$ and $\beta_i,\gamma_i\ge 1$, and all the $p_i$'s are $1$ mod $3$, while all the $q_i$'s are $2$ mod $3$. Then \[ \lambda:=\frac{\tau(10n)}{\tau_1(10n)}=\frac{(\alpha+1)\prod(\beta_i+1)\cdot \tau(m)}{\prod(\beta_i+1)\cdot \tau_1(m)}=(\alpha+1)\frac{\tau(m)}{\tau_1(m)}. \]Use generating functions. Define $G(x)=\prod_{j=1}^s (1+x+\dots+x^{\gamma_i})$. Multiply out the product $G(x)$, then we will have the sum of terms $x^{k_1+k_2+\dots +k_s}$, one term corresponding to each divisor $\delta=q_1^{k_1}\dots q_s^{k_s}$ of $m$. Note that $\delta$ is $1$ mod $3$ if $k_1+\dots+k_s$ is even, and $2$ mod $3$ if it is odd. Therefore, \[ G(1)=\tau(m),\qquad G(-1)=\tau_1(m)-(\tau(m)-\tau_1(m)). \]Now $G(-1)=\prod_{j=1}^s \frac{(-1)^{\gamma_i+1}-1}{(-1)-1}$ is $0$ if some $\gamma_i$ is odd, and $1$ if all the $\gamma_i$'s are even. In the first case, $\tau(m)=2\tau_1(m)$, so $\lambda$ runs through the even positive integers. In the second case, $\tau(m)=2\tau_1(m)-1$ is coprime to $\tau_1(m)$, so $\lambda$ can only be an integer if it is a multiple of $\tau(m)$. Since $\tau(m)=\prod_{j=1}^s (\gamma_j+1)$ runs through the composite odd numbers due to $s\ge 2$ (as $10|m$), this case generates all multiples of some composite odd number. Therefore the answer: the possible integer values are precisely the even numbers and the composite odd numbers.
23.04.2018 20:50
30.12.2019 13:48
20.08.2020 04:33
07.06.2021 16:03
The answer is all evens and odd composites (which can also be described as all composites and two). Let the fraction be $f(n)$. I will exhaust all possible cases of the value of $n$ and show that there always exists a construction for evens and odd composites, and also that odd primes are not achievable. First observe that if $3 \nmid n$, we have $f(3^kn)=(k+1)f(n)$. Also note that multiplying $n$ by primes that are $1 \pmod{3}$ doesn't change $f(n)$, so for the rest of this solution suppose that $n$ is not divisible by any primes $1 \pmod{3}$. Now, call a prime "cool" if it is $2\pmod{3}$. I will prove the following lemma: Lemma: Suppose $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$, where for $1 \leq i \leq k$, $p_i$ is a cool prime and $e_i$ is a positive integer. Then $\tau_1(n)$ is equal to $$\left\lfloor \frac{\tau(n)}{2}\right\rfloor.$$Proof: Observe that a divisor $d=p_1^{d_1}p_2^{d_2}\cdots p_k^{d_k}$ (where we allow $d_i$ to be zero) of $n$ is counted in $\tau_1(n)$ if and only if $d_1+d_2+\cdots+d_k$ is even. First, suppose at least one of the $e_i$ is odd; let one such odd be $e_j$. Then the expression is just $\frac{\prod_{i=1}^k (e_i+1)}{2}$. Thinking combinatorically, we obtain every divisor counted in $\tau_1(n)$ by first picking $d_1,d_2,\ldots,d_{j-1},d_{j+1},\ldots,d_k$ arbitrarily. Then we have exactly $\tfrac{e_k+1}{2}$ choices of $e_k$, which implies the result. Now suppose all of the $e_i$ are even. Here is a curious combinatorical proof for this part: Pick some $N>\max(e_1,e_2,\ldots,e_k)$. Then for a divisor $p_1^{d_1}p_2^{d_2}\cdots p_k^{d_k}$ of $n$, let $g(n)=\overline{d_1d_2\ldots,d_k}_N$. We can order the set $$S=\{g(d), d \mid n\}$$in increasing order, starting with $g(1),g(d_k),\ldots$ and ending with $g(n)$. It's not hard to check that the mod 3 residue of $d$ flips between 1 and 2 as we traverse the sequence. Since the parity of 1 and n mod 3 are both 1, it follows that $\tau_1(n)$ equals $$\frac{1}{2}(\tau(n)-1)=\left\lfloor \frac{\tau(n)}{2}\right\rfloor.\quad \blacksquare$$Now we compute the possible values of $f(n)$. If $10n$ is not a perfect square and $3 \nmid n$, then from our lemma we have $$f(n)=\frac{\tau(10n)}{\tau_1(10n)}=2.$$Using $f(3^kn)=(k+1)f(n)$ when $3 \nmid n$, it follows that $$f(3^k\cdot n)=2(k+1),$$which covers all evens. Now suppose $10n$ is a perfect square and $3 \nmid n$. Then $$f(3^k\cdot n)=\frac{\tau(10n)(k+1)}{\frac{1}{2}(\tau(10n)-1)}.$$We can verify with the Euclidean Algorithm that $\gcd(\tau(10n),\tfrac{1}{2}(\tau(10n)-1))=1$, so if $f(3^k\cdot n)$ is an integer, it must be divisible by $\tau(10n)$. Let $$10n=2^a5^bp_1^{e_1}p_2^{e_2}\cdots p_r^{e_r},$$where for $1 \leq i \leq r$, $p_i$ is a good prime not equal to $2$ or $5$ and $e_k$ is a positive integer; note that since $10n$ is a perfect square, $a,b$ are even numbers that are at least $2$. Then $(a+1)(b+1) \mid \tau(10n) \mid f(3^k\cdot n)$, hence $f(3^k\cdot n)$ must be composite. Conversely, by letting the prime factors of $n$ only be $2$ and $5$, we may easily control $a,b$ such that $f(n)$ is any odd composite number. These two cases cover all possible values of $n$, showing that evens and odd composites are always possible but odd primes are not, so we're done. $\blacksquare$
07.07.2021 01:06
The answer is all evens and odd composites. Let $n=2^{k_1} \cdot 3^m\cdot 5^{k_2} \cdot \prod p_i^{e_i} \prod q_i^{k_i}$ where all $p_i \equiv 1 \pmod 3$ and all $q_i \equiv 2 \pmod 3$ and $m\ge 0.$ Claim: $\tau_1(10n)$ must be of the form: $$\tau_1(10n) = \begin{cases} \frac{1}{2}\prod(e_i+1)\left(\prod (k_i+1) + 1\right) & \text{all }k_i \equiv 0 \pmod 2 \\ \frac{1}{2}\prod(e_i+1)\prod (k_i+1) & \text{else}\end{cases}$$Proof. Note that a divisor $d\mid 10n$ is $1\pmod 3$ iff it is the product of an even number of $2,5,q_i,$ counting multiplicity. As a result, consider the generating function $$f(X) = \prod_{i=1}\sum_{j=0}^{k_i} X^j.$$Then the number of such $d\equiv 1 \pmod 3$ is the sum of coefficients of all even power of $X$ in $f(X).$ In particular, $$\tau_1(10n) = \frac 12\prod(e_i+1)(f(1) + f(-1)) = \begin{cases} \frac{1}{2}\prod(e_i+1)(\prod (k_i+1) + 1) & \text{all }k_i \equiv 0 \pmod 2 \\ \frac{1}{2}\prod(e_i+1)\prod (k_i+1) & \text{else}\end{cases},$$Proving the claim. $\blacksquare$ Then, if all $k_i \equiv 0 \pmod 2,$ $$\frac{\tau(10n)}{\tau_1(10n)} = \frac{2(m+1)\prod (e_i+1) \prod (k_i+1)}{\prod (e_i+1)(\prod (k_i+1) + 1)} = \frac{2(m+1)\prod (k_i+1)}{(\prod (k_i+1)+1)} = \frac{2x(m+1)}{x+1},$$Where since $k_1, k_2 \ge 1$ and $k_i$ are all even, $x$ can be any composite odd integer by considering its prime factorization. In particular, denoting $x = 2z+1$ and setting $m = z,$ $$\frac{\tau(10n)}{\tau_1(10n)} = 2z+1 = x,$$So all odd composite integers are possible. If not all $k_i\equiv 0\pmod 2,$ then $$\frac{\tau(10n)}{\tau_1(10n)} = \frac{2(m+1)\prod (e_i+1) \prod (k_i+1)}{\prod (e_i+1)\prod (k_i+1)} = 2(m+1),$$Whence all evens are possible, finishing the problem. $\blacksquare$
11.06.2022 05:53
Let $x=3^p \cdot a\cdot b$ where \[a=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots p_i^{a_i}\]where $p_k$ are distinct primes equivalent to $2\pmod 3$ in the prime factorization of $x.$ Similarly, define \[b=q_1^{b_1}q_2^{b_2}q_3^{b_3}\dots q_j^{b_j}\]where $q_k$ are distinct primes equivalent to $1 \pmod 3.$ Now, \[\tau(x)=(p+1)(a_1+1)(a_2+1)\dots(a_i+1)(b_1+1)(b_2+1)\dots(b_j+1).\]When picking a divisor that is equivalent to $1\pmod 3,$ we cannot pick any factors of three. We must pick an even number of prime divisors of $a$ (accounting for multiplicity) and we can pick any prime divisors of $b.$ Thus, $\frac{\tau(x)}{\tau_1(x)}=(p+1)\frac{\tau(a)}{\tau_1(a)}.$ In particular if a number $r$ is a possible value, any multiple of $r$ is always a possible value. $~$ Choosing an even number of prime divisors with $2\pmod 3,$ if we have any $a_k$ being odd, there are an even number of choices for the number of factors of $p_k.$ Thus, no matter how we pick the other prime factors, there will always be half of the ways to pick the number of $p_k,$ so $\frac{\tau(a)}{\tau_1(a)}=2$ in this case. Thus, all evens work. $~$ Now consider $\frac{\tau(a)}{\tau_1(a)}$ where $a$ is a perfect square. In this case, our previous argument does not work. However, we know that $a$ is odd and $\tau_1(a)$ is an integer, so any multiple of $\frac{\tau(a)}{\tau_1(a)}$ is a possible value. In particular, $\frac{\tau(a)}{\tau_1(a)}\cdot \tau_1(a)=\tau(a)$ is a possible value. Since $a$ has at least two distinct prime divisors, there are at least two nontrivial factors contributing to $\tau(a)$ so $\tau(a)$ is any odd composite. Therefore, our answer is all evens and odd composite numbers.
26.06.2022 20:39
The first thing I did when I found this problem was to find if $ \tau_1 $ was a multiplicative function as that is the first thing you'd do in any textbook about arithmetic functions. Unfortunately I quickly found that it is in fact not multiplicative but has a property that I'll call $\mod 3 \text{ } multiplicative $. Given any integer $n$ we may write $n = X Y Z$ where $X$ is either 1 or a product of primes $p \equiv 1 \mod 3$, $Y$ is either 1 or a product of primes $p \equiv 2 \mod 3$ and $Z$ is either $1$ or a product of primes $p \equiv 3 \mod 3$. With this in mind we can prove: \[ \textbf{Lemma 1: } \tau_1(XYZ) = \tau_1(X) \tau_1(Y) \tau_1(Z) \] Let's first prove that $\tau_1(XYZ) = \tau_1(XY) \tau_1(Z)$. Because $Z$ is either 1 or a power of 3 we have that $\tau_1(Z) = 1$. Hence what we want to prove is that $\tau_1(XYZ) = \tau_1(XY)$. This is true because if $d$ is a divisor counted on the left hand side it can't be a multiple of 3 so it would also be a divisor counted in the right hand side. Now we have to prove that $\tau_1(XY) = \tau_1(X) \tau_1(Y)$. This is also true because if $d$ is a divisor on the left hand side then we can also decompose $d = X' Y'$ where both $X' \equiv 1\mod 3$ and $Y' \equiv 1 \mod 3$ and vice-versa so the number of possible $d's$ is equivalent to the number of posible $X''s$ multiplied by the number of possible $Y''s$ so our lemma is proved. It is also simple to see that because $\tau$ itself is multiplicative, we also have $\tau(XYZ) = \tau(X) \tau(Y) \tau(Z)$. So we would have: \[ \frac{\tau(n)}{\tau_1(n)} = \frac{\tau(X) \tau(Y) \tau(Z)}{ \tau_1(X) \tau_1(Y) \tau_1(Z)}\] We can simplify this by noting as before that $\tau_1(Z) = 1$ so it vanishes, but also $\tau_1(X) = \tau(X)$. This is because all divisors of $X$ are $1 \mod 3$. So now we are left with: \[ \frac{\tau(Y) \tau(Z)}{\tau_1(Y)} \] We are now fully equipped to find some solutions. Let's first calculate the case of $10$ in which $X = 1$, $Y = 10$ and $Z=1$. By computation we have that $\frac{\tau(10)}{\tau_1(10)} = \frac{4}{2} = 2 $. So 2 is a solution but if we add to this $Z = 3^n$ we would be able to generate $2(n+1)$ hence our first observation is that all even numbers are solutions. Now consider the case of $2^a 5^b 3^{\tau_1 (2^a 5^b) - 1}$. If we evaluate our fraction on this the result would be just $\tau(2^a 5^b) = (a+1)(b+1)$. Here we can play with any values of $a$ and $b$ as long as they are both atleast one (we are forced to have a factor of 10). This would actually generate all composite numbers so our solution is updated to $2$ and all composite numbers. We will now conjecture that these are all possible solutions. In other words, our fraction can never be an odd prime. To do this I want to prove that always either $\tau_1(Y) = \frac{\tau(Y)}{2}$ or $(\tau_1(Y),\tau(Y)) = 1$. If we had the first case the result of our fraction would be $2 \tau(Z)$ so it would never generate odd primes. If we had the second case then to make the fraction an integer, all factors of $\tau_1(Y)$ would need to cancel with $\tau(Z)$ so we would end up with some integer multiple of $\tau(Y)$ and we already saw that this is never prime. To prove that this is true we will now prove \[ \textbf{Lemma 2: } \tau_1(Y) = \lceil \frac{\tau(Y)}{2} \rceil \] I found a fun way to prove this. First, remember that $Y$ has only primes that are $2 \mod 3$. We can associate any $Y$ to a matrix by decomposing $Y = p_1^{a_1} p_2^{a_2}...$ and then defining: \[ Y \to \left( \begin{matrix} p_1^0 & p_2^0 & ...\\ p_1^1 & p_2^1 & ... \\ ... & ... & ... \\ ... & p_2^{a_2} & ... \\ ... & ... & ... \\ p_1^{a_1} & 0 & ... \end{matrix} \right) \] So the idea is to create columns with all the prime powers of a certain prime and then we concatenate those prime columns to form a matrix. If a certain column is bigger than others (the power of a certain prime is bigger than the power of other primes) then we just fill with $0$ in that row for other columns. Just as a quick example suppose that $Y=2^3 5^2 11$, then the associated matrix would be: \[ \left( \begin{matrix} 1 & 1 & 1 \\ 2 & 5 & 11 \\ 4 & 25 & 0 \\ 8 & 0 & 0 \end{matrix} \right) \] If the number has no prime factors then we would say that $M$ just contains a single $1$. For each of these matrices $M$ we will define the operation $|M|$ as the amount of ways of picking one non-zero element from each column and then multiplyign them. So for the matrix above $|M| = 4 \times 3 \times 2 = 24$. It is easy to see that $\tau(Y) = |M|$. Then we will define $|M|_1$ as the amount of ways to pick one non-zero element from each column, multiplying them, and then having the result be congruent to $1 \mod 3$. It is also easy to see that $|M|_1 = \tau_1(Y)$. Given that all we care about is the result of the products $\mod 3$ we can also just apply $\mod 3$ to the matrices so we only have $1's$, $-1's$, and $0's$. We will now prove the formula $|M|_1 = \lceil \frac{|M|}{2} \rceil$ by induction on $|M|$. Consider the base case $|M| = 2$. Necessarily the matrix comes from a number of the form $p$ and in this case $|M| = 2$ and $|M|_1 = 1$. This result fits our hypothesis. Lets now consider a matrix with an arbitrary size $|M|$. If this is a column matrix then it would come from a number of the form $p^k$ in which case $|M| = k+1$ and $|M|_1 = \lceil \frac{k+1}{2} \rceil$. This is true because all even $k$ in $p^{k}$ would count for $|M|_1$ and to get the amount of even $k$ we would use the previous formula. So in the case of column matrices the result holds true. In the case that we don't have a column matrix then we may pick one prime that divides $Y$ and then write $M$ as: \[M = \left( \begin{matrix} 1 & & \\ -1 & M' & \\ 1 & & \\ ... & & \end{matrix} \right) \] In simpler terms, we would have the column and a submatrix $M'$ to the right. To calculate $|M|_1$ notice that we can iterate through the numbers in the first column and then for each $1$ in the column it would add a $|M'|_1$ because we can take all of the products in $M'$ that are equivalent to $1 \mod 3$ and then just multiply it by the $1$ we have in the column and we would generate a number equivalent to $1 \mod 3$. Then for each $-1$ in the column we would find the products in $M'$ that are equivalent to $-1 \mod 3$. But now if we have those products that are equivalent to $-1$ and before we had all the products that were equivalent to $1$ we would have all the non-zero products and hence those two would add up to $|M'|$. So in the first column for each pair of $1$ and $-1$ we add a $|M'|_1$. Suppose that the number of elements in that first column is $n$. If $n$ is even then there are the same amount of 1's and -1's and hence the result would be $|M|_1 = \frac{n|M'|}{2}$. But we can also calculate $|M| = n |M'|$ and this result is also consistent with our hypothesis. The harder case is when $n$ is odd. In this case we would have $|M|_1 = \frac{|M'|(n-1)}{2} + |M'|_1$ but again $|M| = n|M'|$. Applying our induction hypothesis on $M'$ we now want to prove that: \[\frac{|M'|(n-1)}{2} + \lceil \frac{|M'|}{2} \rceil = \lceil \frac{n|M'|}{2} \rceil \] We will prove this the classic way by finding that $LHS \geq \frac{n|M'|}{2}$ but $LHS \leq \frac{n|M'|}{2} + 1$ The first one is easy because $LHS = \frac{|M'|(n-1)}{2} + \lceil \frac{|M'|}{2} \rceil \geq \frac{|M'|(n-1)}{2} + \frac{|M'|}{2} = \frac{|M'|(n)}{2} $. For the second one we have to work a little more. To prove that $\frac{|M'|(n-1)}{2} + \lceil \frac{|M'|}{2} \rceil \leq \frac{|M'|(n)}{2} + 1$ we can simplify this to $\lceil \frac{|M'|}{2} \rceil - \frac{|M'|}{2} \leq 1$ which is a well known inequality. Hence the result is proved. And if we untangle all the matrix notation and go back to the natural world, this proves our second lemma. Equipped with our second lemma, we have $\tau_1(Y) = \lceil \frac{\tau(Y)}{2} \rceil$. In the case when $\tau(Y)$ is even this is an exact fraction and by doing some algebra we find that the fraction is a product of two. Again, this will not produce odd primes. In the case that $\tau(Y)$ is odd we would have $\tau_1(Y) = \frac{\tau(Y) + 1}{2}$. We can now prove that $(\tau(Y),\tau_1(Y)) = 1$ because of a number $d$ divides both things, then it must also divide $2 \tau_1(Y) - \tau(Y) = 1$ and hence $d = 1$. Given that those two are coprime, we have proven that we can never generate odd primes. Tying this all up we also can find a general formula for $\tau_1(n)$. If $n = X Y Z$ as defined above then: \[ \tau_1(n) = \tau(X) \lceil \frac{\tau(Y)}{2} \rceil \] Which means that given the prime factorization of $n$ we could easily compute $\tau_1(n)$ without needing to actually count all such divisors.
16.07.2022 15:19
31.03.2023 15:54
对于 $m\in\mathbb N_+$, 记 $m=3^x\prod\limits_{i}p_i^{a_i}\prod\limits_{j=1}^kq_j^{b_j}$, 其中 $p_i\equiv 1\pmod 3$ 且为素数, $q_j\equiv 2\pmod 3$ 且为素数. 则 ${}d$ 为 ${m}$ 的$\mod 3$ 余 ${}{1}$ 正因子当且仅当 $d=\prod\limits_{i}p_i^{c_i}\prod\limits_{j=1}^kq_j^{d_j}$. 其中 $0\leq c_i\leq a_i$, $0\leq d_j\leq b_j$. 且 $2\mid \sum\limits_{j=1}^kd_j$. 从而 $\tau_1(n)=\prod\limits_{i}(a_i+1)\cdot\left|\left\{(d_1,d_2,\cdots,d_k)\in\mathbb Z_+\mid 0\leq d_i\leq b_i,\sum\limits_{j=1}^kd_j\equiv 0\pmod 2\right\}\right|$. 不难证明 $\left|\left\{(d_1,d_2,\cdots,d_k)\in\mathbb Z_+\mid 0\leq d_i\leq b_i,\sum\limits_{j=1}^kd_j\equiv 0\pmod 2\right\}\right|=\left\lceil\frac 12\prod\limits_{j=1}^k(b_j+1)\right\rceil$. 从而 $Q\overset{\Delta}{=}\frac{\tau(m)}{\tau_1(m)}=\dfrac{(x+1)\prod\limits_{i}(a_i+1)\prod\limits_{j=1}^k(b_j+1)}{\prod\limits_{i}(a_i+1)\left\lceil\dfrac 12\prod\limits_{j=1}^k(b_j+1)\right\rceil}=\dfrac{(x+1)\prod\limits_{j=1}^k(b_j+1)}{\left\lceil\dfrac 12\prod\limits_{j=1}^k(b_j+1)\right\rceil}$. 原题中考虑 $m=10n$ 的情形, 则 ${m}$ 的$\mod 3$ 余 ${}{1}$ 正因子至少有 ${}{2}$, ${}{5}$ 两个, 即 $k\geq 2$. 若 $\exists b_j\equiv 1\pmod 2$, 则 $Q=2(x+1)$, $x\in\mathbb N$, 故可遍全体偶数. 若所有 $b_j$ 均为偶数, 则 $Q=\dfrac{2(x+1)\prod\limits_{j=1}^k(b_j+1)}{\prod\limits_{j=1}^k(b_j+1)+1}$. 要求 $Q\in\mathbb Z$, 故$\left(\prod\limits_{j=1}^k(b_j+1)+1\right)\mid 2(x+1)$. 结合 $k\geq 2$, $Q=\dfrac{2(x+1)}{\prod\limits_{j=1}^k(b_j+1)+1}\prod\limits_{j=1}^k(b_j+1)$ 可取遍全体奇合数. 综上所述, $\frac{\tau(10n)}{\tau_1(10n)}$ 可取到的整数值为全体偶数以及全体奇合数.$\blacksquare$
28.07.2023 13:54
Answer: All composite numbers and $2$ Proof: Let $10n=3^a\cdot\prod_{i=1}^{r_1}p_i^{\alpha_i}\cdot\prod_{i=1}^{r_2}q_i^{\beta_i}$ where all $p_i$ equivalent 2 $mod3$ and all $q_i$ equivalent 1 $mod3$ And let $\prod_{i=1}^{r_1}p_i^{\alpha_i}=a$ Easy to see $\frac{\tau(10n)}{\tau_1(10n)}=\frac{(a+1).\prod_{i=1}^{r_1}(a_i + 1)}{\tau_1(a)}$ for all a is positive integer or $0$ so we can take $a=\tau_1(a)-1$ so we have proof for all composite numbers. If $n=1$ we have the answer $2$ If $a$ isn't a square ve have one prime factor powered by odd number and If we choose other powers random and accordingly the power of this prime number we will see that $\frac{\tau(10n)}{\tau_1(10n)}=2.(a+1)$ and it covers all even numbers. Other case is all powers of $p_i$ are even. And from here we can see that $\frac{\tau(10n)}{\tau_1(10n)}=\frac{(a+1).\prod_{i=1}^{r_1}(a_i + 1)}{\prod_{i=1}^{r_1}(a_i + 1)+1}$ So rest of the solution is easy for equality don't works for prime $p\ge 3$
02.08.2023 04:06
We claim that the answer is even numbers and odd composite numbers. Let $m=10n$. Note that 1 mod 3 prime factors do not matter at all, since they give the same multiplier to top and bottom. To obtain even values, start with 10, which gives a value of 2, and then add as many factors of 3 as necessary to get the required multiplier to reach even numbers. Now, consider odd values. Clearly, $m$ has to be a perfect square. Then, let $v_3(m)=s-1$, and let $$\frac{m}{3^{s-1}}=p_1^{2e_1}\cdots p_k^{2e_k}.$$ Claim: $$\tau_1(m)=\frac{(2e_1+1)\cdots (2e_k+1)+1}{2}.$$ Proof: Use generating functions! We need an even number of 2 mod 3 factors, so we want to the sum of even degree coefficents in $$(e_1+1+e_1x)(e_2+1+e_2x)\cdots (e_k+1+e_kx).$$Plugging in $1$ and $-1$ gives the desired claim. Thus, the value of the expression is $$\frac{2cs}{c+1},$$where $$c=(2e_1+1)\cdots (2e_k+1),$$since $m$ has $cs$ divisors. Note that since $m$ is divisible by 10, the possible values of $c$ are precisely the odd composite numbers (since $k\geq 2$). Suppose we want the value to be $v$. Then, $$\frac{2cs}{c+1}=v$$$$c=\frac{v}{2s-v}.$$If $v$ is prime, the only way for it to be an integer is for either $c=1$ or $c=v$, neither of which are possible due to the fact that $c$ is an odd composite number. On the other hand, if $v$ is composite, then $2s=v+1$ (possible since $v$ odd) would give $c=v$, which is possible. Hence, the answer is even numbers and odd composites.
23.04.2024 05:46
Consider $n\equiv 0\pmod 3$. Let \[r(n)=\frac{\tau_1(10n)}{\tau(10n)}.\]let $S$ be the set of possible values of $r(n)$. Essentially if $d$ occurs as a denominator in some reduced fraction in $S$ then by taking $n\cdot 3^k$ we can get any multiple of $d$. Now if $n$ is not a perfect square then $\frac{1}{2}$ appears. Otherwise use recursion to calculate the denominator; the number of prime factors cannot decrease and yet is at least two upon considering just two prime factors of $n$, thus primes are impossible. We can easily construct $pq$ and $p^2$, hence done. (The answer is anything except for odd primes and $1$.)
14.10.2024 15:33
If I did solve it right, This is actually equal to $2v_{3}(n)+2$.
25.11.2024 22:34
We claim that $\frac{\tau(n)}{\tau_{1}(n)}=2k, \forall k \in \mathbb{N}$ covers all the positive integral values. First, let $n=3^{\alpha}, \alpha \in \mathbb{Z}_{\ge 0}$ $\implies \frac{\tau(n)}{\tau_{1}(n)}= \frac{\tau(2 \cdot 5 \cdot 3^{\alpha})}{\tau_{1}(2 \cdot 5 \cdot 3^{\alpha})}=\frac{4(\alpha +1)}{2}= 2(\alpha +1))$ Now, we show that for any $n$, the value of $\frac{\tau(n)}{\tau_{1}(n)}=2k$. Let $n=3^{\alpha} k$, where $\alpha \in \mathbb{N}$ and gcd($3,k$)=$1$. Observe that $\tau(10n)=\tau(3^{\alpha})\tau(10k)=(\alpha +1)\tau(10k)$ and $\tau_{1}(10n)=\tau_{1}(10k)$. Thus, we need to show the result only for $n$ with gcd($n,3$)=1 Now, we use induction to show that $\frac{\tau(10k)}{\tau_{1}(10k)}=2$ where $3$ and $k$ are coprime. Base case: This clearly is true for $k=1$. Induction: Say that for some positive integral $k$, $\frac{\tau(10k)}{\tau_{1}(10k)}=2$ where $3$ and $k$ are coprime. Take a prime $p \neq 3$. Let $ 1=d_{1}<d_{2}<…<d_{l}=10k$ be the divisors of $10k$. Not that the divisors of $10kp$ are $$ 1=d_{1}<d_{2}<…<d_{l}=10k$$and $$ p=pd_{1}<pd_{2}<…<pd_{l}=10kp$$. If $p \equiv 1(\mod 3)$, then $d_{i} \equiv 1 (\mod 3) \implies pd_{i} \equiv 1 (\mod 3)$ and $d_{i} \equiv 2 (\mod 3) \implies pd_{i} \equiv 2 (\mod 3) $. Since half of the numbers $ 1=d_{1}<d_{2}<…<d_{l}=10k$ are $1(\mod 3)$, half of the numbers $ p=pd_{1}<pd_{2}<…<pd_{l}=10kp$ are $1(\mod 3)$, which gives us that half of the divisors of $10kp$ are of the for $1(\mod 3)$, hence the induction is true for this case. If $p\equiv 2(\mod 3)$, then $d_{i} \equiv 1 (\mod 3) \implies pd_{i} \equiv 2 (\mod 3)$ and $d_{i} \equiv 2 (\mod 3) \implies pd_{i} \equiv 1 (\mod 3)$ Therefore, half of the divisors of $10kp$ are of the for $1(\mod 3)$, hence the induction is true for this case as well, which completes the induction. $\blacksquare$