# Does $a\in\mathbb Z$ such that $\gcd(n,a(m-a))=1$ exist for every $(m,n)\not=(\text{odd},\text{even})$?

When I was thinking about the greatest common divisors, I noticed that we seem to be able to find at least one integer $a$ such that $$\gcd(n,a(m-a))=1$$ for every pair of positive integers $(m,n)$ such that $(m,n)\not=(\text{odd},\text{even})$.

Examples :

• For $(m,n)=(5,7)$, we can take $a=1$.
• For $(m,n)=(4,7)$, we can take $a=-1$.
• For $(m,n)=(4,6)$, we can take $a=5$.

However, I have not been able to prove that.

If we can always take a prime $a\ (\gt m+n)$ such that $$\text{a-m is a prime},$$ then we win. But I think it is another big problem.

(As a user Ofir Schnabel points out, we cannot take such primes for odd $m$. Also, if $m$ is even, then it is an open conjecture in number theory. So this way, which is just one idea, does not seem to solve the problem.)

Maybe I'm missing something important. Can anyone help?

Question : Can we say that there exists at least one integer $a$ such that $$\gcd(n,a(m-a))=1$$ for every pair of positive integers $(m,n)$ such that $(m,n)\not=(\text{odd},\text{even})$ ?

• Clearly for odd $m$ you can't take prime $a$ such that $a-m$ is prime. – Ofir Schnabel Jan 9 '15 at 11:29
• @OfirSchnabel: You are right. I forgot to mention that. Thank you for pointing it out. – mathlove Jan 9 '15 at 11:32
• And for even $m$ you need that there will be two primes with difference $m$. This is an open conjecture in number theory. – Ofir Schnabel Jan 9 '15 at 11:39
• @OfirSchnabel: That's right. And taking such primes is just one idea. My question may be solved by another idea. That's why I'm asking this here. – mathlove Jan 9 '15 at 11:44
• Just thought to pointing it out so pepole will avoid this approch. nice question :). – Ofir Schnabel Jan 9 '15 at 11:46

If $n$ is prime, then there is $a$ such that $n\nmid a(m-a)$, since among values $a=0,\dots, n-1$, at most two are such that $n\mid a(m-a)$: it is $0$ and $m\mod n$. So if $n>2$, then there are at least $n-2$ values that fit, and if $n=2$, then, from your additional condition, $m$ is even, so the value $a=1$ fits.
Now, if $n = p_1^{d_1}\dots p_k^{d_k}$, where $p_i$ are prime, then there are $a_1, \dots, a_k$ such that $p_i\nmid a_i(m-a_i)$ for all $i = 1, \dots, k$. By Chinese remainder theorem, there is $a$ such that $a\equiv a_i\pmod {p_i}$ for all $i$. Then $a(m-a)\equiv a_i(m-a_i) \pmod {p_i}$, i.e., $a(m-a)$ is not divisible by any $p_i$, i.e., $(n,a(m-a))=1$.