Why are the distances of $n$ to the closest non-adjacent coprimes always a prime number?

Question

I have observed that the distance of any $n\in\Bbb N$ to its closest non-adjacent (smaller or greater than $n$ at a distance $\not=$ 1) coprimes is always a prime number.

Def:

$\forall n\ \exists\ c_{left}\ /\ (c_{left},n)=1\ ,\ c_{left}\lt n\ ,\ (d_{left}=n-c_{left})\gt 1\ \land\ \not \exists\ k\ \ 1 \lt (n-k) \lt (n-c_{left}) \land (k,n)=1$

$\forall n\ \exists\ c_{right}\ /\ (c_{right},n)=1\ ,\ c_{right}\gt n\ ,\ (d_{right}=c_{right}-n)\gt 1\ \land\ \not \exists\ k\ \ 1 \lt (k-n) \lt (c_{right}-n) \land (k,n)=1$

So it seems that:

$\forall n\ d_{left},d_{right} \in \Bbb P$

E.g.:

$n=16, c_{left}=13, c_{right}=19, d_{left}=3 , d_{right}=3$

$n=892290, c_{left}=892279, c_{right}=892301, d_{left}=11 , d_{right}=11$

This is a very brute-force Python code, just in case somebody would like to try or modify it:

def coprimes():
    from sympy import gcd
    from gmpy2 import is_prime

    print("Result " + "\t" + "n" + "\t" + "From" + "\t" + "c" + "\t" + "d")
    for n in range (1,1000000):
        j=n-2
        while not gcd(n,j)==1:
            j=j-1
        if is_prime(n-j):
            print("OK" + "\t" + str(n) + "\t" + "Left" + "\t" + str(j) + "\t" + str(n-j))
        else:
            print("ER" + "\t" + str(n) + "\t" + "Left" + "\t" + str(j) + "\t" + str(n-j))

        j=n+2
        while not gcd(n,j)==1:
            j=j+1
        if is_prime(j-n):
            print("OK" + "\t" + str(n) + "\t" + "Right" + "\t" + str(j) + "\t" + str(j-n))
        else:
            print("ER" + "\t" + str(n) + "\t"  + "Right" + "\t" +  str(j) + "\t" + str(j-n))

coprimes()

It also might be possible that every prime $p$ could appear as a distance $d_{left}$ or $d_{right}$, so every prime is a distance from a given $n$ to its $c_{left}$ or $c_{right}$ closest non-adjacent coprime.

I do not understand the reasons behind this, just can guess that somehow might be related with the probabilities of two numbers of being non-adjacent coprimes and some inference from the PNT, so I would like to ask the following questions:

1. Does it make sense that according to the definition or coprimality, these distances were always prime numbers?

2. Is there a counterexample of them?

3. Is it a trivial property?

Any hint is very appreciated. Thank you!

Answer 1

Take $n$ and $a$ such that $\gcd(n,a) = 1$. Then we know that

$$\gcd(n+a,n) = 1, \gcd(n+a,a) = 1$$

By employing the Euclidean algorithm for division.

For any given number, the smallest integer coprime to it is a prime number (which will give the nearest non-adjacent coprime number by addition). This is easy to see; if an integer is coprime to some number, then it must be coprime with all factors of that number.

This means that the distance to the nearest non-adjacent coprime is simply the smallest $p$ that does not divide $n$.

To see the other direction, suppose we had some number other than that satisfying this property. If it is not coprime to $n$, then it fails to generate a coprime. If it is coprime, then its factorization yields a smaller coprime prime, a contradiction.