Solution:
Let m=n−9 and for the sake of contradiction assume m has a prime factor p with p=3. Express p=9q+r where 0≤r≤8 (r is the remainder when p is divided by 9 and q may be zero). Since gcd(9,p)=1 we must have r=1,2,4,5,7 or 8. For each of these possibilities we will use a different choice for x to get our contradiction.
if r=1 then choose x=q so that (9x+1)=9q+1=p
if r=2 then choose x=5q+1 so that (9x+1)=45q+10=5p
if r=4 then choose x=7q+3 so that (9x+1)=63q+28=7p
if r=5 then choose x=2q+1 so that (9x+1)=18q+10=2p
if r=7 then choose x=4q+3 so that (9x+1)=36q+28=4p
if r=8 then choose x=8q+7 so that (9x+1)=72q+64=8p
In any we can choose x so that (9x+1) is a multiple of p. For this particular value of x we have
(nx+1)=mx+(9x+1),
and so (nx+1) is a multiple of p too (recall p∣m). Therefore p would be a common factor of (9x+1) and (nx+1). This is a contradiction so no such p can exist.
So m=n−9 cannot have any prime factors other than 3. Hence m=3k or m=−3k for some integer k≥0. i.e.
n=9+m=9+3k or 9−3k
The positive integers of this form, less than 2024 are: 6,8,10,12,18,36,90,252,738.
To show all these work, we now assume n=9±3k for some integer k≥0, and let g=gcd(9x+1,nx+1). Since 9x+1 is not a multiple of 3, we cannot have g being a multiple of 3. However
g∣(nx+1)−(9x+1)=±3k.
The only divisors of 3k which are not a multiple of 3 are 1 and −1. Therefore g=1 whenever n=9±3k.