Let $p_i$ for $i=1,2,..., k$ be a sequence of smallest consecutive prime numbers ($p_1=2$, $p_2=3$, $p_3=3$ etc. ). Let $N=p_1\cdot p_2 \cdot ... \cdot p_k$. Prove that in a set $\{ 1,2,...,N \}$ there exist exactly $\frac{N}{2}$ numbers which are divisible by odd number of primes $p_i$.
HIDE: example For $k=2$ $p_1=2$, $p_2=3$, $N=6$. So in set $\{ 1,2,3,4,5,6 \}$ we can find $3$ number satisfying thesis: $2$, $3$ and $4$. ($1$ and $5$ are not divisible by $2$ or $3$, and $6$ is divisible by both of them so by even number of primes )Problem
Source: Polish Mathematical Olympiad finals 2021
Tags: number theory, prime numbers
07.04.2021 17:42
This problem was proposed by Burii.
07.04.2021 18:21
Pair the numbers up in couples of the form $\left(m;m+\frac{N}{2}\right)$, with $1\leq m \leq \frac{N}{2}$. Since $\frac{N}{2}=p_2\cdots p_k$, if $i>2$ $p_i|m\iff p_i|m+\frac{N}{2}$, and $2|m\iff 2\nmid m+\frac{N}{2}$. Therefore, the two elements of a couple have different parity of prime factors in $\{p_1,...,p_k\}$ and so we have a total of $\frac{N}{2}$ with odd number of prime factors in $\{p_1,...,p_k\}$.
07.04.2021 22:21
Another approach to the problem. #(numbers are divisible by even number of pi)= #(numbers are divisible by 0 number of pi) + #(numbers are divisible by 2 number of pi)+...... #(numbers are divisible by odd number of pi)=#(numbers are divisible by 1 number of pi)+..... #(numbers are divisible by 0 number of pi)=phi(N) (phi is Euler totient function) #(numbers are divisible by 1 number of pi)= Sum of phi(N/pi) And so on. It's remains to show that these two sums are equal. And it could be easily done by induction on k .(left to the reader) I am just showing N=2 case. phi(2×3)+phi(1)=phi(2)+phi(3)
12.05.2021 14:20
Let's call the numbers which are in $\{1,2,\dots , N\}$ and divisible by odd number of $p_i$'s lucky. Claim: If $1\leq n \leq \frac{N}{2}$, then exactly one of the numbers $\{n , n + \frac{N}{2}\}$ is lucky. Proof: Let $n = p_{i_1}^{r_1} \cdot p_{i_2}^{r_2} \dots p_{i_m}^{r_m}$. Then $n + \frac{N}{2} = p_{i_1}^{r_1} \cdot p_{i_2}^{r_2} \dots p_{i_m}^{r_m} + p_2\cdot p_3 \dots p_k$. Note that $n$ and $n + \frac{N}{2}$ have the same set of prime divisors from $\{p_2 , p_3 , \dots , p_k\}$. And also the parities of $n$ and $n + \frac{N}{2}$ are different. So one of them is lucky and other is not, as desired. $\square$ It is clear that claim solves the problem.
03.06.2021 00:08
We will call a number in the set bad if the number is divisible by even number of $p_i's$ and good if is divisible by odd numbers of $p_i's$. Observe that we have $x$ a good number if $gcd(x,N)= p_{i_1}p_{i_2}....p_{i_{2l+1}}=d$ for some $l \geq 0$ and positive integer numbers $i_1,i_2,...i_{2l+1} \leq k$. So we want $d \mid x$ and $gcd(\frac{N}{d}, x) = 1$. Observe that the total of numbers coprimes with $\frac{N}{d}$ and less than $\frac{N}{d}$ is exactly $\phi(\frac{N}{d})$ So if $S_1$ is the number of good numbers , we have: $$S_1 = \sum_{i \in G}\phi(\frac{N}{i})$$where $G$ is the set of the numbers in the form $p_{i_1}p_{i_2}....p_{i_{2l+1}}$ Let $S_2$ be the number of bad numbers, by analogous reasons we have $$S_2 = \sum_{j \in B}\phi(\frac{N}{j})$$where $B$ is the set of the numbers in the form $p_{i_1}p_{i_2}....p_{i_{2l}}$ with the number 1. We may prove that $S_1 = S_2$, but this can be easily done with a bijection. Consider the case that $k$ is even. Hence, every term of $S_1$ sum is good and every term of $S_2$ sum is bad, and in each sum all numbers from $G$ and $B$ are included. If $2l$ is a number from $G$, hence $l$ is a number from $B$, and observe that: $$ \phi({2l}) = \phi(2)\phi(l) = \phi(l)$$So they cancel in $S_1-S_2$, for example. If $2v+1$ is a number from $G$, hence $4v+2$ is a number from $B$, but: $$\phi({4v+2}) = \phi({2})\phi({2v+1}) = \phi({2v+1})$$So they cancel too, and the $k$ odd case is analogous. The conclusion is that for each number in $S_1$, there exists another equal number in $S_2$, hence $S_1=S_2$ and $2S_1=N \Longleftrightarrow S_1= \frac{N}{2}$ Example for case $k=4$ for maybe better understanding...
Cool problem.
04.08.2021 11:02
I think $p_3=3$ in the problem is a typo
28.02.2022 20:46
We can count by $$\sum_{d\vert N, \omega(d)\equiv 1\pmod 2}\sum_{m: m\leq N, \gcd(m, N)=d}1=\sum_{d\vert N, \omega(d)\equiv 1\pmod 2}\phi(\frac{N}{d})=\sum_{A\subseteq \{1, \dots, k\}, 2\big\vert \vert A\vert -1}\prod_{i\in A}\phi(p_i)=\sum_{A\subseteq \{1, \dots, k\}, 2\big\vert \vert A\vert-1}\prod_{i\in A}(p_i-1)$$ (Where $\omega(n)$ counts the distinct prime divisors of $n$.) Define the generating function $f\in \mathbb{Z}[X]$ by $$f(x):=\prod_{i\in \{1, 2\dots, k\}}(x+(p_i-1))$$ We want to calculate the sum of the coefficients corresponding to the monomial terms of degree $k+1\pmod 2$, that is $$\frac{f(1)+(-1)^{k+1} f(-1)}{2}=\frac{N}{2}$$ since $f(-1)=0$ from $p_1=2$ and $f(1)=p_1p_2\cdots p_k=N$. $\blacksquare$