Note that $ a_{1}= 1$ -- the smallest positive integer that will be always relatively prime to $ n$. Also, $ a_{2}= p$ where $ p$ is a prime, because if it was not prime, then the smallest prime number dividing $ a_{2}$ would be greater than $ 1$ and relatively prime to $ n$ because $ a_{2}$ is relatively prime to $ n$. So, $ a_{2}= p$ where $ p$ is a prime, so $ p$ must be the smallest prime relatively prime to $ n$. Then, $ a_{2}-a_{1}= a_{3}-a_{2}=\cdots = a_{k}-a_{k-1}= p-1$. We will now consider 3 cases: Case 1 $ p = 2$. Then, $ a_{2}-a_{1}= a_{3}-a_{2}=\cdots = a_{k}-a_{k-1}= 1$, and because $ n-1$ is relatively prime to $ n$, then $ a_{k}= n-1$ so $ 1,2,...,n-1$ are all relatively prime to $ n$ so $ n$ is prime. Case 2 $ p = 3$. Then, $ a_{2}-a_{1}= a_{3}-a_{2}=\cdots = a_{k}-a_{k-1}= 2$ so the numbers $ 1,3,5,...,n-1$ are relatively prime to $ n$, so all odd numbers less than $ n$ are relatively prime to $ n$, so $ n$ has no divisors that are odd primes, so the only prime it is divisible by is $ 2$, so $ n$ is a power of $ 2$. Case 3 $ p > 3$. Then, $ a_{2}-a_{1}= a_{3}-a_{2}=\cdots = a_{k}-a_{k-1}= p-1$, so $ a_{k}= 1+(k-1)(p-1)$ but because $ n-1$ is the largest number less than $ n$ and relatively prime to $ n$, $ n-1 = 1+(k-1)(p-1)$ so $ n-2 = (k-1)(p-1)$. So, $ p-1$ divides $ n-2$. Let $ q$ be any prime dividing $ p-1$, then as $ 1 < q\leq p-1 < p$, $ q$ is not relatively prime to $ n$, so as $ q$ is prime, $ q$ must divide $ n$. On the other hand, $ q|(p-1)|(n-2)$ so $ n-2$ and $ n$ are both divisible by $ q$, so $ n-(n-2) = 2$ is divisible by $ q$ so $ q = 2$. Then, $ p-1$ can only be divisible by $ 2$, so it is a power of $ 2$, so $ p = 2^{r}+1$; because $ p > 3$ and is prime, $ p$ is not divisible by $ 3$, and as $ 2^{r}+1\equiv (-1)^{r}+1\pmod 3$ and $ p$ is not divisible by $ 3$, $ (-1)^{r}+1$ cannot be $ 0$, so $ r$ is even. But then, $ a_{3}= a_{1}+2(p-1) = 1+2*2^{r}= 1+2^{r+1}\equiv 1+(-1)^{r+1}\pmod 3$ $ \equiv 0\pmod 3$ as $ r$ is even. Hence, $ 3|a_{3}$ and as $ \gcd(a_{3},n) = 1$, $ n$ is not divisible by $ 3$ so $ 3$ and $ n$ are coprime so $ 1 < a_{2}\leq 3$ which contradicts the fact that $ a_{2}>3$. So we get a contradiction and in the case when $ p > 3$ the required $ n$ does not exist. Then, the only valid cases are $ 1$ and $ 2$ which yield $ n$ being a prime or a power of $ 2$ QED.