For any positive integer $n$, let $D_n$ denote the set of all positive divisors of $n$, and let $f_i(n)$ denote the size of the set $$F_i(n) = \{a \in D_n | a \equiv i \pmod{4} \}$$where $i = 1, 2$. Determine the smallest positive integer $m$ such that $2f_1(m) - f_2(m) = 2017$.
Problem
Source: Chinese Southeast Mathematical Olympiad
Tags: modular arithmetic, number theory
l1090107005
06.08.2017 05:53
The answer is $2\cdot 5^{2016}$. Lemma When a positive number $p$ only have prime factors in the form $4k+3$, then $f_1(p)-f_3(p)=0$ or $1$.
Carl2015
11.08.2017 05:04
For grade 11 the problem is Determine the smallest positive integer $m$ such that $f_0(m) +f_1(m)-f_2(m) - f_3(m) = 2017$. Suppose $n=2^a(\prod{p_i^{a_i}})(\prod{q_i^{b_i}})$ $p_i \equiv 1\pmod{4} , q_i \equiv 3\pmod{4} $ $p=\prod{(1+a_i)} , q=\prod{(1+b_i)}$ Then $f_0(n) =(a-1)pq , f_1(n) =p[\frac{q}{2}] , f_2(n) =pq , f_1(n) +f_3(n) =pq$
targo___
11.08.2017 14:49
l1090107005 wrote: The answer is $2\cdot 5^{2016}$. Lemma When a positive number $p$ only have prime factors in the form $4k+3$, then $f_1(p)-f_3(p)=0$ or $1$. Can you(or,anyone else) help me to do the proof ,i am not getting it..
l1090107005
18.08.2017 13:36
targo___ wrote: l1090107005 wrote: The answer is $2\cdot 5^{2016}$. Lemma When a positive number $p$ only have prime factors in the form $4k+3$, then $f_1(p)-f_3(p)=0$ or $1$. Can you(or,anyone else) help me to do the proof ,i am not getting it.. Use induction on the number of prime factors of $p$. First obviouly $p^\alpha$ satisfy, and $$f_1(pq)-f_3(pq)=f_1(p)f_1(q)+f_3(p)f_3(q)-f_1(p)f_3(q)-f_3(p)f_1(q)=(f_1(p)-f_3(p))(f_1(q)-f_3(q))=0\text{ or }1$$
babu2001
18.08.2017 21:21
targo___ wrote: l1090107005 wrote: The answer is $2\cdot 5^{2016}$. Lemma When a positive number $p$ only have prime factors in the form $4k+3$, then $f_1(p)-f_3(p)=0$ or $1$. Can you(or,anyone else) help me to do the proof ,i am not getting it.. Here is an extremely useful and intuitive method to do this. Define $f (n)=f_1 (n)-f_3(n) $. Define a function $\phi:2\mathbb Z+1\longrightarrow \{1,-1\} $ as $n\equiv \phi (n)\pmod 4$. Easy to check that $\phi$ is multiplicative. Now observe that $f (n)=\sum_{d|n}\phi (d) $, so $f $ is multiplicative and its enough to check the required result for prime powers which is trivial. Moreover we can now completely characterise $ f$ for all numbers since $f (p^t)=t+1\quad\forall p\equiv 1\pmod 4$ and $f (p^t)=(t+1)\pmod 2\in\{0,1\}\quad\forall p\equiv 3\pmod 4$. In general, for any number $n $ having a primitive root $g $, i.e., $n=2,4,p^t,2p^t $ for some prime $p $, we have $\mathcal U (n)\equiv \{a:\gcd (a,n)=1,1\leq a\leq n\} $ is cyclic with generator $g $, then $\phi:\mathcal U (n)\longrightarrow \{1,-1\} $ is a non-trivial homomorphism if and only if $\phi (g^t)=(-1)^t $, kind of like the Legendre function for quadratic residues.
GorgonMathDota
28.07.2018 17:27
Isnt there any more elementary and elegant solution. I dont quite understand
GorgonMathDota
29.07.2018 14:54
bump bump
korncrazy
02.06.2019 19:01
Let $m=2^c p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}q_1^{\beta_1}q_2^{\beta_2}\cdots q_l^{\beta_l};p_i\equiv 1 \pmod{4},q_i\equiv -1 \pmod{4}$ and $p_1<p_2<\cdots<p_k,q_1<q_2<\cdots<q_l$ be an distinct prime$.$
So that $f_2(m)=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)(\beta_1+1)(\beta_2+1)\cdots(\beta_l+1).$
Consider the number of ways to choose even numbers of $q_i$ is equal to the sum of coefficient of $x^{2k}$ of polynomial
$$P(x)=(1+x+\cdots+x^{\beta_1})(1+x+\cdots+x^{\beta_2})\cdots(1+x+\cdots+x^{\beta_l}).$$The sum of coefficient of $x^{2k}$ of $P(x)$ is equal to
$$\frac{P(1)+P(-1)}{2}=\begin{cases}\frac{(\beta_1+1)(\beta_2+1)\cdots(\beta_l+1)}{2} & \mbox{if}{\;there\; exists\; i \; that \;\beta_i\; is \; odd} \\ \frac{(\beta_1+1)(\beta_2+1)\cdots(\beta_l+1)+1}{2} & \mbox{if}{\; for\; all\; i\; \beta_i\; is\; even}\end{cases}.$$Then $$f_1(m)=\begin{cases}\frac{(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)(\beta_1+1)(\beta_2+1)\cdots(\beta_l+1)}{2} & \mbox{if}{\; there\;exists\; i \; that \;\beta_i\; is \; odd} \\ (\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)\cdot\frac{(\beta_1+1)(\beta_2+1)\cdots(\beta_l+1)+1}{2} & \mbox{if}{\; for\; all\; i\; \beta_i\; is\; even}\end{cases}.$$Then $$2017=2f_1(m) - f_2(m)=\begin{cases}0 & \mbox{if}{\; there\;exists\;i \;that \;\beta_i\;is \;odd} \\ (\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)& \mbox{if}{\quad for\;all\;i\;\beta_i\;is\;even}\end{cases}.$$$\therefore k=1,\alpha_1=2016,c\geqslant 1$ and for all $i\;\beta_i$ is even
$\therefore$ The minimum of $m$ is $2\cdot 5^{2016}$
f6700417
11.08.2022 16:28
Most parts of the solution are not difficult. Here is one of the ways to calculate f₁(m). If there exists i that β_i is odd, let β₁ be odd. Consider f: (2j, β₂', β₃‘, ..., β_t') to (2j+1, β₂', β₃‘, ... β_t'), (j=0, 1, ..., (β₁-1)/2, 0≤β_i’≤β_i). If for all i, β_i is even. Consider f: (β₁,β₂, ..., β_(i-1), 2j, β_(i+1)', ...,β_t') to (β₁,β₂, ..., β_(i-1), 2j+1, β_(i+1)', ...,β_t'), (i=0, 1, ..., t-1, j=0, 1, ..., β_i/2-1).