1
$\begingroup$

I'm trying to prove that for any $N \in \mathbb{Z^+}$, there exists only finite many integers $n$ with $\varphi(n) = N$ (i.e. finite amount of numbers that have $N$ numbers relatively prime to them)

I started by addressing the lower bound of $\varphi(n)$ as the set of primes $P = \{0<p\leq n~|~\varphi(p) = p-1\}$ from $0$ to $n$ If I can prove that this lower bound increases as $n$ increases, then I can say that $N$ eventually is excluded from the bounds of the function and so the amount of $n$ has to be finite.

For any $k\in \mathbb{Z^+}$ there is a prime factorization $k = \prod p_i^{\alpha_i}$

For $|P|$ (the lower bound) to remain finite and less than $N$, $p_i$ must also be finite.

This leads to the reasoning that for all $k \in \mathbb{Z^+}$ there must exist a finite amount of distinct prime factors $p_i$. This is where I'm stuck.

How can I prove that there must be an infinite amount of primes to represent an infinite amount of integers?

$\endgroup$
3
  • $\begingroup$ Well, using your notation, $\varphi(k)=\prod p_i^{a_i-1}\times \prod (p_i-1)$. Thus you need $p_i-1\leq N$, so only finitely many primes, and you need $p_i^{a_i-1} \leq N$ so only finitely many $a_i$. $\endgroup$
    – lulu
    Apr 20, 2016 at 16:18
  • $\begingroup$ how did you get $\prod (p_i - 1)$? Isn't it just $\prod p_i$ because $p_i^{a_i -1} \times p_i = p_i^{a_i}$? $\endgroup$
    – Obliv
    Apr 20, 2016 at 16:25
  • $\begingroup$ No. $\varphi (p^a) = p^{a-1}(p-1)$ if $p$ is prime. $\endgroup$
    – lulu
    Apr 20, 2016 at 16:29

2 Answers 2

0
$\begingroup$

You're just trying to prove that there are infinitely many primes? I recommend this classic proof by contradiction, which is part of a proof attributed to Euclid:

Suppose there are finitely many primes, say $p_1, \dots, p_n$. Note that every one of these primes divides the product $p_1 \cdots p_n$. Consider the number $p_1 \cdots p_n + 1$. It can't be prime because it's larger than the largest prime. So it must be divisible by at least one prime, call it $p_k$. Then $p_k$ divides $p_1 \cdots p_n$ and $p_k$ divides $p_1 \cdots p_n + 1$, which means $p_k$ divides $(p_1 \cdots p_n + 1) - (p_1 \cdots p_n) = 1$, a contradiction.

$\endgroup$
7
  • $\begingroup$ Euclid did not use contradiction $\endgroup$
    – Henry
    Apr 20, 2016 at 16:21
  • $\begingroup$ @Henry, you should update the wiki page then. en.wikipedia.org/wiki/Euclid%27s_theorem#Euclid.27s_proof $\endgroup$
    – user307169
    Apr 20, 2016 at 16:22
  • 3
    $\begingroup$ That page already says correctly "Euclid is often erroneously reported to have proved this result by contradiction, ..." $\endgroup$
    – Henry
    Apr 20, 2016 at 16:23
  • 1
    $\begingroup$ Splendid. Then can you update my ability to read? $\endgroup$
    – user307169
    Apr 20, 2016 at 16:23
  • 1
    $\begingroup$ For example, take a look at Chapter 2 in Number Theory: An Introduction via the Distribution of Primes by Benjamin Fine and Gerhard Rosenberger. $\endgroup$ Apr 21, 2016 at 2:15
0
$\begingroup$

I don't have enough reputation to comment, but see this Wiki page. You're asking for a proof of Euclid's Theorem

https://en.wikipedia.org/wiki/Euclid%27s_theorem

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .