Two numbers are relative prime if their greatest common divisor is $1$, that is $gcd(n,a)$. We can also find no of elements that are relative prime to given number by Euler function.
How can I find a number suppose '$a$' that is relative prime to my given number let's say '$n$' and is smaller than '$n$'? Ideally I want smallest number that is relative prime to $n$ except $1$.
On
The number $1$ is always there relatively prime to any given number. If you dislike this choice for all odd numbers $2$ will work. If you don't care about how big or small it is here is one possible way of getting more from less:
Suppose you know that $a$ is such that $\gcd(n,a)=1$ . (for example $a=1$). Now multiply $n$ by any number and add this 'a'. That is any number $xn+a$ will also be relatively prime to $n$.
Example $n=15$. You know $2$ is relatively prime to 15. Now every number in the arithmetic progression $2, 2+15, 2+30, 2+45, 2+60,\ldots$ will be relatively prime to $15$.
Primes are : $2,3,5,7,\ldots$. You can check divisibility of $n$ by $2$ if it's not divisible then $a=2$ if it is then try $3,5$ etc. Or you can find the product of primes that compose $n$ and pick the smallest prime not included. (this is if you don't want the number $1$)