Let $n\in \Bbb N$. Is there a prime $p>n$ for which $\gcd(n,p-1)=1$? For which $n\in \Bbb N$, is there a prime number $p&gt;n$ for which $\gcd(n,p-1)=1$?
When $n$ is odd, Dirichlet's theorem implies there are infinitely many primes in the sequence
$$2,\quad 2+n,\quad 2+2n,\quad\ldots$$
and taking such a prime $p=2+kn$ (other than $2$), we have
$$\gcd(p-1,n)=\gcd(1+kn,n)=1$$
When $n$ is even, it is impossible to have $\gcd(p-1,n)=1$ for a prime $p&gt;n$ because any prime greater than $n$ is odd, so $\gcd(p-1,n)\geq 2$.
Yes, because if n is even then it is of the form 2c where c is some integer, and it is a classical result of number theory that any integer can be factored into a unique product of a finite number of primes. Thus to find a number m such that (n,m)=2  you find a number of the form 2p where p is some prime that does not divide c, which is always possible because of an infinite number of primes. Now you need merely to prove that there are an infinite number of primes a such that a=(b-1)/2, where b is also prime, which is relatively easy.