OIM 2004 Problem 3

Let $n$ and $k$ be positive integers such as either $n$ is odd or both $n$ and $k$ are even. Prove that exists integers $a$ and $b$ such as $GCD(a,n) = GCD(b,n) = 1$ and $k = a + b$