$\boxed{N1}$Let $n$ be a positive integer,$g(n)$ be the number of positive divisors of $n$ of the form $6k+1$ and $h(n)$ be the number of positive divisors of $n$ of the form $6k-1,$where $k$ is a nonnegative integer.Find all positive integers $n$ such that $g(n)$ and $h(n)$ have different parity.
Problem
Source: Balkan MO 2014 Shortlist
Tags: number theory, Balkan Mathematics Olympiad, Balkan MO Shortlist, Parity
01.10.2016 18:50
Let $n=2^a3^bM$ where $\gcd (M,6)=1$ for some $a,b\in \mathbb{Z}^+_0$. We get that $g(n)=g(M)$ and $h(n)=h(M)$. Also $d(M)=g(M)+h(M)$ where $d(M)$ is the number of divisor of $M$. We know that $g(M),h(M)$ have different parity. So $d(M)\equiv 1\pmod{2}$ which means $M$ is a perfect square. So the answer is $2^a3^bt^2$ for any positive integer $t$ that $\gcd(T,6)=1$. Easy to see that all numbers with such form satisfy the condition since $d(t^2)$ is odd and each of divisor of $t^2$ is counted either in $g(n)$ or $h(n)$.
08.05.2019 04:53
Above is quite simple and slick. For a slightly longer alternative (using the same notation, letting $n=2^a 3^b M$ with $(M,6)=1$) with a slightly stronger conclusion, let $S_1=\{d\mid M:d\equiv 1\pmod{6}\}$ and $S_2=\{d\mid M:d\equiv -1\pmod{6}\}$. If $M\equiv 5\pmod{6}$, then note that, $d\in S_1 \iff M/d\in S_2$, hence $|S_1|=|S_2|$. If $M\equiv 1\pmod{6}$, and $M$ is not a perfect square, then note that, $d\in S_1\iff M/d \in S_1$ with $d\neq M/d$; and $d\in S_2\iff M/d\in S_2$ with, again, $d\neq M/d$, thus, $|S_1|$ and $|S_2|$ are both even. If $M$ is a perfect square, then one of $S_1$ and $S_2$ must also contain $\sqrt{M}$, thus will make $|S_1|$ and $|S_2|$ to differ in parity.
12.07.2023 21:20
Let $n = 2^x \cdot 3^y \cdot z$, this means $z = 6k - 1$ or $6k + 1$ and it only has divisors of type $6k - 1$ or $6k + 1$. Let $z = c_1^{d_1} \cdot c_2^{d_2} \cdot \ldots \cdot c_k^{d_k} \cdot e_1^{f_1} \cdot e_2^{f_2} \cdot \ldots \cdot e_t^{f_t}$, where $c$'s are of type $6k - 1$ and $e$'s are from $6k + 1$. Let $A = (d_1 + 1) \cdot (d_2 + 1) \cdot \ldots \cdot (d_k + 1)$, $B = (f_1 + 1) \cdot (f_2 + 1) \cdot \ldots \cdot (f_t + 1)$, $C$ = number of ways of choosing a divisor $x$ of $c_1^{d_1} \cdot c_2^{d_2} \cdot \ldots \cdot c_k^{d_k}$ so $x \equiv 1 \pmod{6}$. This means that $g(n) = g(d) = B \cdot C$ and $h(n) = h(d) = B \cdot (A - C)$. If $B$ is even, then same parity. If $A$ is even, then same parity $\Rightarrow$ $A$ and $B$ are odd $\Rightarrow$ $z = t^2$ $\Rightarrow$ Answer: $n = 2^a \cdot 3^b \cdot t^2$, which indeed works.