Let $n$ be a positive integer. Consider prime numbers $p_1,\dots ,p_k$. Let $a_1,\dots,a_m$ be all positive integers less than $n$ such that are not divisible by $p_i$ for all $1 \le i \le n$. Prove that if $m\ge 2$ then $$\frac{1}{a_1}+\dots+\frac{1}{a_m}$$is not an integer.
Problem
Source: Iran 3rd round 2017 Number theory first exam-P1
Tags: number theory, Divisibility, prime numbers, prime, Iran, IranMO
fattypiggy123
09.08.2017 15:41
Let $p$ be the smallest prime not excluded and let $k$ be the maximal $v_p$ among all the $a_i$'s. Let $v_p(a_j) = k$. We claim that for any other $a_i$, one has $v_p(a_i) < a_j$. This implies the conclusion since $p^k$ will divide the denominator of the final sum. Now otherwise, one has $v_p(a_i) = k$ for some $a_i$ distinct from $a_j$. Hence $a_i = cp^k$ where $c$ is some natural number whose prime factors are all larger than $p$. Since $c > 1$, one has $c > p$ and thus $n > a_i > p^{k+1}$, implying that $p^{k+1}$ is one of the $a_i$'s which is a contradiction to the maximality of $k$.
Adolmephus
03.02.2019 22:23
fattypiggy123 wrote: Let $p$ be the smallest prime not excluded and let $k$ be the maximal $v_p$ among all the $a_i$'s. Let $v_p(a_j) = k$. We claim that for any other $a_i$, one has $v_p(a_i) < a_j$. This implies the conclusion since $p^k$ will divide the denominator of the final sum. Now otherwise, one has $v_p(a_i) = k$ for some $a_i$ distinct from $a_j$. Hence $a_i = cp^k$ where $c$ is some natural number whose prime factors are all larger than $p$. Since $c > 1$, one has $c > p$ and thus $n > a_i > p^{k+1}$, implying that $p^{k+1}$ is one of the $a_i$'s which is a contradiction to the maximality of $k$. Pretty nice solution fattypiggy! But i could not understand what would happen if c=1?
fattypiggy123
04.02.2019 03:10
The idea is that both $a_i,a_j$ will be of the form $cp^k$ and so one of them, WLOG $a_i$, will have $c > 1$.
mojyla222
20.03.2024 12:56
Proposed by Amin Fathpour.