# Infinite Prime Proof Using Euler's Totient

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.

-

## 2 Answers

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.

-
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$.

-
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