What is the number of integers between 1 and 60 that are relatively prime to 60? I know that the answer is 16, but how do I go about finding the relative primes using a quick process?
[Math] Relative primes
prime numbers
Related Solutions
Lattice theorem for rings: For any ring homomorphism $\psi:A\to B$ and any ideal $I$ of $B$, the set $\psi^{-1}(I)$ is an ideal of $A$. This map of ideals is inclusion-preserving, i.e. if $I\subseteq J$ are ideals of $B$, then $\psi^{-1}(I)\subseteq \psi^{-1}(J)$. Furthermore, for any prime ideal $P\subset B$, we have that $\psi^{-1}(P)$ is a prime ideal of $A$.
We have an inclusion homomorphism $j:\mathbb{Z}\to\mathbb{Z}[i]$. Our strategy is to classify the (non-zero) prime ideals $P$ of $\mathbb{Z}[i]$ according to the "value" of $j^{-1}(P)=P\cap \mathbb{Z}$.
First, we will re-express the ring $\mathbb{Z}[i]$ in a more convenient form:
Consider the ring homomorphism $\operatorname{ev}:\mathbb{Z}[x]\to\mathbb{Z}[i]$ defined by $\phi(f)=f(i)$. This function is surjective, and the kernel of $\operatorname{ev}$ is the ideal $(x^2+1)$ of $\mathbb{Z}[x]$. Therefore, by the first isomorphism theorem, $\operatorname{ev}$ descends to an isomorphism $\phi:R\to\mathbb{Z}[i]$, where $R=\mathbb{Z}[x]/(x^2+1)$.
For the remainder of this post, we will now be interested in classifying the prime ideals of $R$. The lattice theorem guarantees that $\phi$ sets up a bijective, order-preserving correspondence between the prime ideals of the two rings. I can explain more about why this is okay if you'd like.
Consider the inclusion homomorphism $k:\mathbb{Z}\to R$ (of course $k=\phi^{-1}\circ j$); we will pretend for the sake of expediency that $\mathbb{Z}$ is actually contained as a subset of $R$.
For each (non-zero) prime ideal $(q)$ of $\mathbb{Z}$, we want to classify the prime ideals $Q$ of $R$ such that $k^{-1}(Q)=(q)$, i.e. the prime ideals $Q$ of $R$ that contain $(q)$. Note that a prime ideal $Q$ of $R$ will contain the $\mathbb{Z}$-ideal $(q)$ if and only if $Q$ contains the element $q$, which is the case if and only if $Q$ contains the $R$-ideal $qR$. By the lattice theorem, the prime ideals of $R$ containing $qR$ are in order-preserving bijection with the prime ideals of $$R/qR=(\mathbb{Z}[x]/(x^2+1))/q(\mathbb{Z}[x]/(x^2+1))\cong \mathbb{Z}[x]/(q,x^2+1)\cong \mathbb{F}_q[x]/(x^2+1).$$ If $q=2$, then in $\mathbb{F}_2$ we have $x^2+1=(x+1)^2$, so that $$R/2R\cong \mathbb{F}_2[x]/(x+1)^2$$ has one prime ideal, namely $(x+1)\mathbb{F}_2[x]/(x+1)^2$. Unwinding our various isomorphisms, this corresponds to $i+1$ in $\mathbb{Z}[i]$.
If $q\equiv 1\bmod 4$, then $x^2+1$ is reducible (by quadratic reciprocity there is some $a\in \mathbb{F}_q$ such that $a^2=-1$ in $\mathbb{F}_q$), so that $$R/qR\cong \mathbb{F}_q[x]/(x-a)(x+a)$$ which has two prime ideals, $(x-a)\mathbb{F}_q[x]/(x-a)(x+a)$ and $(x+a)\mathbb{F}_q[x]/(x-a)(x+a)$. Unwinding our various isomorphisms, this corresponds to a conjugate pair of Gaussian primes $\pi$, $\overline{\pi}$ with norm $q\equiv 1\bmod 4$ in $\mathbb{Z}[i]$.
Lastly, if $q\equiv 3\bmod 4$, then $x^2+1$ is irreducible (by quadratic reciprocity there is no $a\in \mathbb{F}_q$ such that $a^2=-1$ in $\mathbb{F}_q$), so that $$R/qR\cong \mathbb{F}_q[x]/(x^2+1)\cong\mathbb{F}_{q^2}$$ is a field and therefore has one prime ideal, namely the zero ideal. Unwinding our various isomorphisms, this corresponds to a Gaussian prime $q\equiv 3\bmod 4$ that lives in $\mathbb{Z}$.
Needless to say, this method is well-known and not original to me; for example I'm pretty sure that Neukirch does precisely this at the outset of his book. I'll see if I can find some good references later. Also, I'd just like to comment that algebro-geometrically, what's happening is we're looking at the fibers of $\operatorname{Spec}\mathbb{Z}[i]$ over $\operatorname{Spec}\mathbb{Z}$; look at the curve in $\operatorname{Spec}\mathbb{Z}[x]$ corresponding to the ideal $(x^2+1)$ in Mumford's famous sketch:
I have to get to sleep, so I'm signing off for now, but I'll respond to any comments or questions when I can.
No, $x^2+2x+1=(x+1)^2$ obviously is not prime for natural $x>0$.
Edit: for irreducible case you may want to read about the (unsolved) Bunyakovsky conjecture.
Best Answer
You can use the Euler's totient, see http://en.wikipedia.org/wiki/Euler%27s_totient_function for how it works. By the way, the answer is 16, not 15 (if you include 1).
If moreover you want to know who are those numbers, I guess you should list all the primes between 1 and 60 that does not appear in the factorisation of 60 ; then all the numbers you are looking for are made from those primes.