Prove or disprove : All of the generators greater than $1$ of $\Bbb Z_{60}$ are prime.

Question

I know that generators of $\mathbb{Z}_{60}$ have the form of {$k:\gcd(60,k)= 1$} . by brute force, i found that $\gcd(60,49) = 1 $and $49$ isnt prime. thus this statement would be false. However, is there a more efficient way to do this than brute force? also, is there an intuition of why this statement would be false? at first glance, I was sure that it was true, but I just didn't know how to prove it thus I started looking for counterexamples.

Answer 1

To summarize the discussion in the comments: Since $2\times 3\times 5$ divides $60$, any $k$ relatively prime to $60$ must be the product of primes $>5$.

The least such prime is $7$ so $7^2=49$ is the least composite number prime to $60$. The second least is $7\times 11=77$ but that's greater than $60$ so $49$ is the only composite generator amongst $\{1,\cdots, 59\}$.