1
$\begingroup$

If $n$ is composite and $\phi{(n)} | (n - 1)$ then prove that $n$ has at least four distinct prime factors.

Attempt:

Since $n$ is not a prime, let's first take the case that $n$ is squarefree. Then $n = a_1 \cdot a_2 \cdots a_r$ where $a_i$ are the prime factors of $n$ listed in ascending order. Thus, $\dfrac{n-1}{\phi(n)} = \dfrac{a_1a_2\cdots a_r-1}{(a_1-1)(a_2-1)\cdots (a_n-1)}$. The denominator has a factor of $2^n$.

I am not sure how to continue from here.

$\endgroup$
  • $\begingroup$ What about $n = 1$? $\endgroup$ – Michael Biro May 26 '16 at 0:53
  • $\begingroup$ @MichaelBiro I think we suppose $n>1$? $\endgroup$ – Puzzled417 May 26 '16 at 1:01
  • $\begingroup$ Note that $n$ would have to be squarefree, since if $p^2\mid n$ then $p\mid \phi(n)$ but not $n-1$. $\endgroup$ – rogerl May 26 '16 at 1:21
  • $\begingroup$ This is related to Lehmer's totient problem. $\endgroup$ – rogerl May 26 '16 at 1:26
  • $\begingroup$ @rogerl Why is it true that if $p^2 | n$ then $p | \phi(n)$? $\endgroup$ – Puzzled417 May 26 '16 at 1:38
1
$\begingroup$

To eliminate $3$ prime factors is pretty simple because since $\phi(n)<n-1$ it implies that $\phi(n)\le\frac n2$. If $3$ isn't one of the factors the smallest $\frac{\phi(n)}n$ could be is $\frac45\frac67\frac{10}{11}=0.6234$. If $5$ isn't a factor, the smallest is $\frac23\frac67\frac{10}{11}=0.5165$. If both $3$ and $5$ are factors, $\frac23\frac45\frac{16}{17}=0.5020$ is too big, so we only have to test $\phi(105)=48$, $\phi(165)=80$, and $\phi(195)=96$ to eliminate all remaining possibilities.

$\endgroup$
0
$\begingroup$

This solves the 2 prime factor case, which together with user5713492's answer, solves the problem:

Suppose we have primes $p$ and $q$ such that $\phi(pq)=(p-1)(q-1)|pq-1$. Then we have:

$$pq\equiv1\pmod{(p-1)(q-1)}$$

so

$$pq\equiv1\pmod{p-1}$$

and also

$$p\equiv1\pmod{p-1}$$

so

$$pq\equiv q\pmod{p-1}$$

hence

$$q\equiv1\pmod{p-1}$$

and so

$$q\geq p.$$

Similarly,

$$p\geq q,$$

so $p=q$, which contradicts that it must be squarefree, as noted in the comments.

$\endgroup$
  • $\begingroup$ After reading user5713492's answer, I see that his answer actually solves the 2 prime case as well. I will leave this answer here for reference. $\endgroup$ – alphacapture May 26 '16 at 1:45
  • $\begingroup$ I think there are typos here. For instance, it should be $pq−1 \equiv 0 \pmod{(p−1)(q-1)}$. $\endgroup$ – Puzzled417 May 26 '16 at 3:27
  • $\begingroup$ @Puzzled417 Fixed $\endgroup$ – alphacapture May 26 '16 at 10:58

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.