Determine the largest positive integer $n$ which cannot be written as the sum of three numbers bigger than $1$ which are pairwise coprime.
Problem
Source: Bosnia and Herzegovina TST 2016 day 2 problem 1
Tags: number theory, Additive Number Theory, coprime
16.05.2016 15:34
The answer is 17. Note that this problem is already appear in "Math problem book I" by "Kim Y. Li" which is easy to be found.
16.05.2016 17:20
if n is of form $4m + 2$ , then we have representation as a sum of 3 pairwise coprimes , $4m + 2 = (2m + 1) + (2m - 1) + 2 , for m > 1$. if $n = 4m $ , write $4m = 4 + (2m - 1) + (2m - 3)$ , for m > 3. if $n = 4m + 3$ , further (1) : if $3|m$ , write $4m + 3 = 3 + (2m - 1) + (2m + 1)$ (2): if $3$ , doesnot divides m .... (requires help here) , though possible could be $(m -1) + (2m + 3) + (m + 1)$ for even m. and $(m - 5) + (2m + 1) + (m + 7)$ for odd m. if $n = 4m + 1$ , 1) if m is odd : (a)7 does not divides m ,$4m + 1 = m + (m - 2) + (2m + 3)$ for m > 3. (b) 7 divides m , $4m + 1 = m + (m - 4) + (2m + 5)$ (2) : m is even ( > 4) $4m + 1 = (m + 3) + (m - 1) + (2m - 1)$ check all left cases where m < 4. P.S. last two cases may have been errored.
31.01.2017 19:02
gobathegreat wrote: Determine the largest positive integer $n$ which cannot be written as the sum of three numbers bigger than $1$ which are pairwise coprime. Let $n=a+b+c$ where $\gcd(a,b)=\gcd(b,c)=\gcd(c,a)=1$. Clearly, two of $a,b,c$ can not be even. Therefore, if $n$ is odd, then all of them are odd and if $n$ is even, two are odd whereas the other is even. Since none of $a,b,c$ are equal and at least $1$, if $n$ is odd, $n$ is at least $3+5+7=15$. If $n$ is even, $n$ is at least $3+5+2=10$. If $n$ is even and of the form $4k+2$, $n=2+(2k+1)+(2k+3)$ works for $n\geq2+3+5=10$. For even numbers of the form $4k$, $n=2+(2k+1)+(2k+5)$ which works for $n\geq2+3+7=12$. We are left with odd $n$. After checking for some values, we can see $n=17$ does not have such a representation. Since $19=3+5+11$, $21=5+7+9$ and $23=3+7+13$, we are done if we can prove that every odd number starting from $25$ can be written as a sum of three pair-wise co-prime numbers. For any even positive integer $n\geq8$, $n$ can be written as a sum of two co-prime positive integers. We can just write $n$ as $(2k+1)+(2k-1)$ or $(2k+3)+(2k-1)$. Let $n$ be $2k+1$, so $k\geq12$ if $n\geq25$. Then $2k-7\geq\frac{6(k+1)}{5}$. From Nagura's theorem, we have a prime $p$ such that $k+1\leq p\leq2k-7=n-8$. Our idea is to write $n$ as $p+m$ where $p>m$. Obviously, $m$ is an even positive integer, so we must write $m$ as a sum of two co-prime positive integers. This will be guaranteed if $m\geq8$ or $n-p\geq8$ or $p\leq n-8$ (this is the motivation behind our choice of prime earlier). We also need to guarantee that $p>m$, which is guaranteed by $p\geq k+1$. Otherwise, $m\geq p\geq k+1$ so $p+m\geq2k+2$, contradiction. Again, if $m=a+b$ with $\gcd(a,b)$ and $a>b$m then $p>a>b$, which ensures $a,b$ are co-prime to $p$. Thus, we have our representation.