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$
  • $\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 '16 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 '16 at 16:25
  • $\begingroup$ No. $\varphi (p^a) = p^{a-1}(p-1)$ if $p$ is prime. $\endgroup$ – lulu Apr 20 '16 at 16:29
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$
  • $\begingroup$ Euclid did not use contradiction $\endgroup$ – Henry Apr 20 '16 at 16:21
  • $\begingroup$ @Henry, you should update the wiki page then. en.wikipedia.org/wiki/Euclid%27s_theorem#Euclid.27s_proof $\endgroup$ – tilper Apr 20 '16 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 '16 at 16:23
  • 1
    $\begingroup$ Splendid. Then can you update my ability to read? $\endgroup$ – tilper Apr 20 '16 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$ – Robert Soupe Apr 21 '16 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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