Xrfgtjtk

I need some help in a proof:
Prove that for any integer $n>6$ can be written as a sum of two co-prime integers $a,b$ s.t. $gcd(a,b)=1$.

I tried to go around with "Dirichlet's theorem on arithmetic progressions" but didn't had any luck to come to an actual proof.
I mainly used arithmetic progression of $4$, $(4n,4n+1,4n+2,4n+3)$, but got not much, only to the extent of specific examples and even than sometimes $a,b$ weren't always co-prime (and $n$ was also playing a role so it wasn't $a+b$ it was $an+b$).

I would appriciate it a lot if someone could give a hand here.

Well if $n$ is odd you can always do $n-2$ and $2$. Or you can do $frac {n-1}2$ and $frac {n+1}2$.

If $n = 2k$ and $k$ is even you can do $k-1$ and $k+1$. As $kpm 1$ is odd and $gcd(k-1, k+1) = gcd(k-1, k+1 -(k-1)) = gcd(k-1,2)=1$.

If $n = 2k$ and $k$ is odd you can do $k-2$ and $k+2$ and as $kpm 2$ is odd you have $gcd(k-2,k+2)=gcd(k-1, 4) = 1$.

Just to provide an answer synthesized out of the comments already posted, your best (read as easiest) approach to this kind of problem is to toy around with general patterns until something either clicks and you can write a clever proof or until you accidentally exhaust all possible cases.

In this particular problem, we can break down cases into the residue classes $bmod 4$ in order to hunt for patterns:

1) If $n=2k+1$ then the decomposition $n=(k)+(k+1)$ satisfies our criterion since consecutive numbers are always coprime and $kgeq 3$.

2) If $n=4k$ then consider the decomposition $n=(2k-1)+(2k+1)$. Are these numbers coprime? We can no longer rely upon the general fact that consecutive numbers are coprime, since these are not consecutive. However, if two numbers differ by exactly $2$, what is the only prime factor that they can share? In general, if two numbers differ by $m$, what prime factors can they share? Finally, are we sure that these numbers are both greater than $1$?

I have basically given away the entire answer, but I didn't know how to discuss this phenomenon in any other way, so I leave the final details of the second case, and the entirety of the third case, to you.

Later: the numbers between $1$ and $n-1$ that are relatively prime to $n$ itself come in pairs that add up to $n$ and are relatively prime to each other as well. If $n=5$ or $n geq 7$ both such numbers can be chosen strictly larger than $1.$

Original:

A different emphasis: if Euler's totient $phi(n) geq 3,$ then there is some integer $a$ with $gcd(a,n) = 1$ and $1 < a < n-1.$ If we then name $b = n-a,$ we find that $gcd(a,b) = 1$ as well, since a prime $p$ that divides both $a,n-a$ also divides $n,$ and this contradicts $gcd(a,n) = 1.$

So, when is $phi(n) geq 3 ; ? ; ;$ If $n$ is divisible by any prime $q geq 5,$ then $phi(n)$ is a multiple of $phi(q) = q-1,$ and that is at least $4.$

Next, if $n = 2^c ; 3^d ; . ;$ When $d=0$ we find $phi(n) = 2^{c-1}$ is at least $3$ when $c geq 3,$ leaving $2,4$ out. When $c=0$ we find $phi(n) = 2 cdot 3^{d-1}$ is at least $3$ when $d geq 2,$ leaving $3$ out. When $c,d geq 1,$ we find $phi(n) = 2^c cdot 3^{d-1}$ is at least $3$ when either $c geq 2$ or $d geq 2,$ so this leaves out $6.$

Put it together, for $n=5$ or $n geq 7,$ there is some $a$ with $1 < a < n-1$ and $gcd(a,n) = 1.$

Here's another route you can take to solve this problem. For any $n ge 7$, you want to show that there is a number $a$ where

1. 
   $gcd(a, n - a) = 1$,


2. 
   $1 < a < n$, and


3. 
   $1 < n - a < n$.

One option would be to choose $a$ to be the smallest prime number that doesn't divide $n$. In that case, $gcd(a, n - a) = 1$ because otherwise you'd have $gcd(a, n - a) = a$, meaning that $a$ divides $a + (n - a) = n$, contradicting the fact that $a$ doesn't divide $n$.

What you'll need to then show is that if you pick $n ge 7$ that the smallest prime number that doesn't divide $n$ happens to be less than $n - 1$. I'll leave that as an exercise to the reader. :-)