For each positive integer $m$ let $t_m$ be the smallest positive integer not dividing $m$. Prove that there are infinitely many positive integers which can not be represented in the form $m + t_m$. (A. Golovanov)
Problem
Source: 2020 Tuymaada Junior P1
Tags: number theory
06.10.2020 09:01
We prove that the powers of $2$ work . Let $2^k=m+t_{m}$ , and notice that for all odd $m$ , $t_m=2$ , thus $m$ has to be even . Write $m=2^n\cdot q$ where $q$ is odd . On the other hand $2^n\mid {t_m}$ and since $2^n\mid{m}\implies{t_{m}>2^n}$ , so by the definition of $t_m$ , we have $t_m=2^{n+1}$ , absurd .
09.01.2021 15:19
Rickyminer wrote: For each positive integer $m$ let $t_m$ be the smallest positive integer not dividing $m$. Prove that there are infinitely many positive integers which can not be represented in the form $m + t_m$. (A. Golovanov) I think any even number work . Assume n is even then $t_m$ is not 2 then its odd . So the sum is odd . And for odd numbers we have that $t_m$ is 2 so the sum is odd . And we see that no even number can be $m+t_m$
09.01.2021 15:54
@above : $24$ is a counterexample to your claim, $t_m$ is of course not necessarily even for even $m$'s
09.06.2022 07:32
Mathmatin wrote: Rickyminer wrote: For each positive integer $m$ let $t_m$ be the smallest positive integer not dividing $m$. Prove that there are infinitely many positive integers which can not be represented in the form $m + t_m$. (A. Golovanov) I think any even number work . Assume n is even then $t_m$ is not 2 then its odd . So the sum is odd . And for odd numbers we have that $t_m$ is 2 so the sum is odd . And we see that no even number can be $m+t_m$ $10=6+t_{6}$
21.08.2024 18:45
\(Claim\): any number in the form $2^k$ can't be expressed as $m+t_m$ for any number $m$. \(Proof\): We suppose there are some $k$ and $m$ such $2^k=m+t_m$. Now $m$ can't be odd if $m$ is odd then $t_m=2$ which is \(contradictory\). So $m$ and $t_m$ are both even. Now $t_m$ must have a odd divisor $q>1$. Cause if not $t_m$ is in the form of $2^l$ for some $l$. Then $m=2^k - 2^l$. Now $l<k$ so $t_m=2^l|2^l(2^{k-l}+1)=2^k - 2^l =m$ a \(contradiction\). So $t_m$ must have an odd divisor $q>1$ and also $t_m>q$ as $t_m$ is the smallest number not dividing $m$ so $q|m$ so $q|m+t_m=2^k$ a \(contradiction\). there are infinite number in the form $2^k$.So by \(Claim\) there are infinite numbers which can't be expressed as $m+t_m$ for any $m$ $\square$