Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need something explained or corrected: In my number theory class we proved that there are an infinite number of primes using Euler's Phi Totient. It went something like this:

Let $M = p_1 p_2 \dots p_n$ be the product of all primes. Consider $1 < A \le M$:

Some prime must divide $A$, call it $q$. Since $q$ must be one of the primes, $q$ must divide $M.$

So the $gcd(A,M) > 1.$ Thus $\phi(M) = 1$ ...?

Which is not even and contradicts the theorem that $\phi(N)$ is even for $N>2.$ Therefore there exists an infinite number of primes.

I get confused by the statement "Thus $\phi(M) = 1$"....

Did i possibly copy this proof down wrong? or am I missing something? Thank you in advance.

Edit: by consider a such that...i meant consider an integer '$a$' I replaced it with $A$ to hopefully make it more clear.

Edit2: I'm sorry I am not familiar with using the equation editor. This is not a homework assignment, just studying for my exam. I just want to be able to understand this or clearify it.

share|cite|improve this question
up vote 9 down vote accepted

By definition, $\phi(M)$ is the number of numbers in $S=\{1,2,\dots,M\}$ that are relatively prime with $M$. The argument shows that if $1<A\le M$, then $A$ is not relatively prime with $M$, so there is only one element of $S$ relatively prime with $M$, namely 1, and $\phi(M)$ is therefore equal to 1.

share|cite|improve this answer
Ohhhhhh... Thank you. There is only one element in S that is relatively prime with M...and it is 1. So \phi(M) = 1 . That makes sense. – Eric Apr 28 '11 at 22:43

Note that $\phi(M)$ counts the number of integers in the interval $[1, M-1]$ which are relatively prime to $M$. We are told to use the fact that $\phi(M)$ is almost always even.

Since $1$ is relatively prime to $M$, that leaves $\phi(M)-1$ numbers in our interval, different from $1$, which are relatively prime to $M$.

But since $\phi(M)$ is even, it follows that $\phi(M)-1$ is odd, and in particular not equal to $0$, since $0$ is even! Thus there is a number $a \ne 1$, in our interval, such that $a$ is relatively prime to $M$. Any prime divisor $p$ of $a$ must be different from all the $p_i$ in the given list, since $a$ is relatively prime to $M$.

Seems like a bit too much machinery for this problem, specially since we can see that if $n>1$, the number $M-1$ is not equal to $1$, and is relatively prime to $M$.

share|cite|improve this answer
In the proof I state that gcd(a,M) > 1 so i'm not saying that they are relatively prime. – Eric Apr 28 '11 at 22:40
I understand what you are saying now. Thank you! – Eric Apr 28 '11 at 22:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.