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})$ ?
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$.