0
$\begingroup$

Show that if $p_1,\ldots p_t$ are the first $t$ prime numbers, and $n_j = p_1\cdot \ldots \cdot p_t - \frac{p_1\cdot \ldots \cdot p_t}{p_j}$, then $\phi(n_j)=\phi(n_k)$ for $1 \leq j,k \leq t$ and conclude that the equation $\phi(x)=m$ has infinitely many solutions. Here $\phi(\cdot)$ is the Euler Totient function.

I am really stuck on this one. First of all $p_j \nmid n_j$ because even though $p_j$ divides the first term in $n_j$ it does not divide the second. Therefore $gcd(n_j,p_j)=1$. However, can we use this to prove the theorem? Thanks for any help!

EDIT At first the whole expression for $n_j$ seemed really confusing to me. I think it can be rewritten as: $$n_j = \left(1-\frac{1}{p_j}\right) \prod\limits_{i=1}^{t} p_i = (p_j-1)\left(\prod\limits_{i=1}^{j-1}p_i \right)\cdot \left(\prod\limits_{i=j+1}^{t}p_i \right)$$ Maybe this helps!

$\endgroup$
2
$\begingroup$

Let $\phi$ denote the Euler totient function. Let $d$, $n$ be positive integers with $d$ dividing some power of $n$, that is, every prime divisor of $d$ also divides $n$. Then $\phi(dn) = d\,\phi(n)$. As $N = p_1\cdots p_t$ is the product of the first $t$ prime numbers, every prime factor of $p_j-1$ still divides $N/p_j$. Therefore, $$\phi(n_j) = \phi\left((p_j - 1)\,\frac{N}{p_j}\right) = (p_j - 1)\,\phi\left(\frac{N}{p_j}\right) = \phi(p_j)\,\phi\left(\frac{N}{p_j}\right)$$ As $\phi$ is multiplicative and $N/p_j$ is coprime to $p_j$, we get $$\phi(n_j) = \phi(N)$$ which implies the statement $\phi(n_j) = \phi(n_k)$.

Nevertheless, $\phi(x) = m$ with given $m$ has only finitely many solutions for $x$. Too see this, consider the number of prime factors of $x$, counted with multiplicity. Let us denote this $\Omega(x)$. You can deduce from the product formula for $\phi(x)$ that $\Omega(\phi(x)) \geq \Omega(x) - 1$ (the $-1$ is for the possible prime divisor 2). Therefore $$\Omega(x) \leq \Omega(m) + 1$$ and since the greatest prime divisor of $x$ cannot exceed $m+1$, we can easily estimate an upper bound for $x$ as $$x \leq (m+1)^{\Omega(m)+1}$$ We conclude that there can only be finitely many $x$ with $\phi(x) = m$.

$\endgroup$
0
$\begingroup$

Call $N = p_1 p_2 \ldots p_t$ for compactness. Then: $$ n_j = N - N / p_j = (p_j - 1) N / p_j $$

As the totient is multiplicative and never zero: $$ \phi(n_j) = \phi(p_j - 1) \phi(N) / \phi(p_j) = \phi(p_j - 1) \phi(N) / (p_j - 1) $$ If it was $\phi(n_j) = \phi(n_k)$, then it would be: $$ \phi(p_j - 1) / (p_j - 1) = \phi(p_k - 1) / (p_k - 1) $$ But: $$ \begin{align*} \phi(5 - 1) / (5 - 1) &= 2 / 4 = 1/2 \\ \phi(7 - 1) / (7 - 1) &= 2 / 6 = 1/3 \end{align*} $$ Too nice to be true :-(

$\endgroup$
  • $\begingroup$ Hey thanks for your answer. I think the question is meant to mean that there exists $j$ and $k$ smaller than $t$ such that $\phi(n_j)=\phi(n_k)$. For instance in the example you gave $\phi(3)/(3-1) = 1/2$. So it does not need to hold for all $j$ and $k$ smaller than $t$. $\endgroup$ – Slugger May 3 '13 at 23:18
  • $\begingroup$ @TeunVerstraaten OK, then $p_j = 3$ and $p_k = 5$ will work for OP's needs, for any $t$ $\endgroup$ – vonbrand May 3 '13 at 23:55
  • $\begingroup$ Yeah but $j$ needs to specified beforehand. Thats why in the question I used $n_j$. And then you show that some $k$ exists to satisfy the condition. $\endgroup$ – Slugger May 4 '13 at 0:04
  • $\begingroup$ @vonbrand: $\phi$ is multiplicative, but not completely multiplicative. $\endgroup$ – ccorn May 4 '13 at 1:38

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.