Let $n$ be a positive integer. Suppose there are exactly $M$ squarefree integers $k$ such that $\left\lfloor\frac nk\right\rfloor$ is odd in the set $\{ 1, 2,\ldots, n\}$. Prove $M$ is odd. An integer is squarefree if it is not divisible by any square other than $1$.
Problem
Source:
Tags: number theory, Poland, TST
22.04.2018 09:46
It’s an interesting problem, any solutions?
22.04.2018 10:33
Just induct on $n$. When you switch from $n$ to $n + 1$ the only $k$'s that change the parity are the squarefree divisors of $n + 1$, and there's clearly an even number of those.
22.04.2018 10:34
Let $S_n :=\{$set of all square free no. in $ \{1,2,\cdots n\}\}$,$M_n:=\{k : \lfloor\frac nk\rfloor \equiv 1\mod 2, k \in S_n\}$ and $D_n :=\{k:k|n,k \in S_n\}$ We are req'd to show that $|M_n| \equiv 1(\mod 2)$ , $\forall n \in \mathbb{N}$. Let's induct , we will skip the base case and proceed to inductive step:- So we have $\lfloor\frac {n+1} k\rfloor - \lfloor\frac nk\rfloor \equiv 0 $ if $k\not | n+1$ other wise $1$. case $1$) $n+1$ isn't square free, So , $|M_{n+1}| = |M_{n}| -|(M_n \cap D_{n+1})| + |((S_n-M_n) \cap D_{n+1})| \equiv |M_n| + |S_n\cap D_{n+1}| \mod 2$ See that if $n+1 = \prod_{i=1}^k p_i^{\alpha_i}$ , then $|S_n\cap D_{n+1}| \equiv 2^{k}$ case $2$) $n+1$ is square free, $|M_{n+1}| = |M_{n}| -|(M_n \cap D_{n+1})| + |((S_n-M_n) \cap D_{n+1})|+1 \equiv |M_n| + |S_n\cap D_{n+1}|+1 \mod 2$ $n+1 = \prod_{i=1}^k p_i$ , then $|S_n\cap D_{n+1}| \equiv 2^{k}-1$. Done
14.10.2018 09:49
Well here is my solution I will use mobius inversion formula.($\mu(n)$) $\mu(n)=1$ if $n=1$ $\mu(n)=0$ if $p^2|n$ for some prime $p$ $\mu(n)=(-1)^r$ if $n=p_1p_2\cdots p_r$ So i would be using the fact that $\mu(n)$ is multiplicative.
Now as $\sum_{d|n}\mu(n)=F(n)$ $\sum\limits_{n=1}^{n}F(n)=\sum\limits_{k=1}^{n}\mu(k)[\frac{n}{k}]$ $-(1)$ Thus $L.H.S=1$ by our claim. We can see that for all $k$ which aren't squarefree $\mu(k)=0$ hence they would be elimimated from $R.H.S$ We would be just left square free integers $k$ less than $n$. Now let us denote $Z$ to be sum of all $[\frac{n}{k}]$ which are odd and $L$ to be sum of all $[\frac{n}{k}]$ which are even where $k$ is a squarefree integer. So we get $Z+L\equiv 1\pmod{2}$ by $(1)$ Clearly $Z\equiv 1\pmod{2}$ $\implies M\equiv 1\pmod{2}$
09.05.2019 16:57
Awful problem
25.02.2021 16:26
Let $S$ be set of squarefree integers. Note that the prb statement is equivalent to proving that $a_n=\sum_{k\in S}\left\lfloor\frac nk\right\rfloor$ is odd for all $n\in\mathbb{N}$. Clearly $a_1=1$ Note that $a_{n+1}=a_n+f(n+1)$ where $f(m)$ is number of squarefree divisors of $m$ for $m\in\mathbb{N}$. But now $f(n+1)$ i.e. no. of squarefree divisors of $n+1$ is $2^{\omega (n+1)}$ where $\omega (n+1)$ is no. of distinct prime divisors of $n+1$ and hence is even as $\omega (n+1)\geq 1$ for $n\geq 1$. So difference between any two consecutive terms of sequence $\langle a_i\rangle$ is even and $a_1$ is odd. Hence $a_n$ is odd $\forall n\in\mathbb{N}$. Q.E.D.
01.03.2022 23:04
Note that $$M\equiv\sum_{k \, \mu(k)\neq 0}\lfloor \frac{n}{k}\rfloor = \sum_{k \, \mu(k)\neq 0}\sum_{d: k\vert d \, d\leq n}1 \pmod 2$$since if $\lfloor \frac{n}{k}\rfloor$ is even it contributes $0$ and else if $\lfloor \frac{n}{k}\rfloor=1$ it contributes $1$ (modulo 2). Now we change the order of sumation $$ \sum_{k \, \mu(k)\neq 0} \sum_{d: k\vert d \, d\leq n}1=\sum_{d=1}^n \sum_{k \, \mu(k)\neq 0 \, k\vert d} 1= \sum_{k \, \mu(k)\neq 0} 2^{\omega(d)}\equiv 1 \pmod 2 $$ so $M$ is odd. $\blacksquare$
03.03.2022 20:37
Euler365 wrote: Let $S$ be set of squarefree integers. Note that the prb statement is equivalent to proving that $a_n=\sum_{k\in S}\left\lfloor\frac nk\right\rfloor$ is odd for all $n\in\mathbb{N}$. Clearly $a_1=1$ Note that $a_{n+1}=a_n+f(n+1)$ where $f(m)$ is number of squarefree divisors of $m$ for $m\in\mathbb{N}$. But now $f(n+1)$ i.e. no. of squarefree divisors of $n+1$ is $2^{\omega (n+1)}$ where $\omega (n+1)$ is no. of distinct prime divisors of $n+1$ and hence is even as $\omega (n+1)\geq 1$ for $n\geq 1$. So difference between any two consecutive terms of sequence $\langle a_i\rangle$ is even and $a_1$ is odd. Hence $a_n$ is odd $\forall n\in\mathbb{N}$. Q.E.D. Nice Solution
01.04.2024 12:48
We can take $k$ to be any natural number ($\mathbb{N}=\left \lbrace 1,2,3,4,...\right \rbrace$), as if $k>n$, then $\lfloor \frac{n}{k} \rfloor=0$, so it doesn't change the number $M$. Let $M(n)$ be the number $M$ for a natural number $n$. We will induct on $n$. Base case: $M(1)=1$, that's obvious and odd. Inductive step: Let $M(n)$ be odd. Now $\lfloor \frac{n+1}{k} \rfloor=\lfloor \frac{n}{k} \rfloor$ or $\lfloor \frac{n+1}{k} \rfloor=\lfloor \frac{n}{k} \rfloor+1$. The second holds if and only of $n \equiv -1 (\textrm{mod} \ k)$, so $k|n+1$. Let $n+1=p_1^{t_1} \cdot ... \cdot p_s^{t_s}$. The number of squarefree divisors of $n+1$ is precisely $2^s$, so that's an even number. It means that $M(n+1)=M(n)+a-b$, where $a$ is the number of pairs $(\lfloor \frac{n}{k} \rfloor,\lfloor \frac{n+1}{k} \rfloor)$, where the first number is odd and the second is even, and $b$ is the number of pairs $(\lfloor \frac{n}{k} \rfloor,\lfloor \frac{n+1}{k} \rfloor)$, where the first number is even and the second is odd. Thus, we have $$M(n+1)=M(n)+a-b=M(n)+a+b-2b=M(n)+2^s-2b$$and so numbers $M(n)$ and $M(n+1)$ are same parity, which yields that $M(n+1)$ is odd and completes the proof.