0
$\begingroup$

Solve the equation $\phi(N)=98$

I have no idea how to do it. How to find all N?

$\endgroup$

closed as off-topic by Watson, C. Falcon, choco_addicted, Dietrich Burde, user91500 Jun 21 '16 at 12:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Watson, C. Falcon, choco_addicted, Dietrich Burde, user91500
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Do you know how to use the prime factorisation of $N$ to calculate $\phi(N)$? $\endgroup$ – Arthur Jun 21 '16 at 12:11
  • 2
    $\begingroup$ If $n=p^aq^b\dots$ for distinct primes $p,q,\dots$ then $\phi(n)=n(1-\frac{1}{p})(1-\frac{1}{q})\dots$. You know that $98=2\cdot7\cdot7$. So just look at the possibilities. $p-1$ must divide $98$ and so must $p$ if the power is greater than 1. $\endgroup$ – almagest Jun 21 '16 at 12:11
  • 1
    $\begingroup$ Here, I found them: $\{\;\}$. $\endgroup$ – Ivan Neretin Jun 21 '16 at 12:14
  • $\begingroup$ In any case, solving $\phi(n)=a$ is a finite problem because $\phi(n) \geq \frac{\sqrt{n}}{\sqrt{2}}$ and so you only need to test for $n\le 2a^2$. See math.stackexchange.com/questions/301837/…. $\endgroup$ – lhf Jun 21 '16 at 12:42
4
$\begingroup$

A prime factor $p$ of $N$ contributes a factor $p-1$ to $\phi(N)$ and also a factor $p^{e-1}$ if $p^e$ divides $N$.

Since $98 = 2 \cdot 7 \cdot 7$, consider where $7$ comes from.

It cannot come from $p=7$, because $6$ does not divide $98$.

It cannot come from $p-1$, because $8$ is not prime.

It must come from a factor of $p-1$.

The two factors of $7$ in $98$ cannot come from the same $p-1$ because neither $50$ nor $99$ are primes.

But if the two factors of $7$ in $98$ came from different $p-1$, we would have a factor of $4$ in $98$.

Bottom line, $\phi(N)=98$ has no solutions.

$\endgroup$
  • $\begingroup$ But 7 might also be a non-trivial factor of $p-1$. $\endgroup$ – almagest Jun 21 '16 at 12:20
  • $\begingroup$ @almagest, thanks. I think I've fixed it now. $\endgroup$ – lhf Jun 21 '16 at 12:36
3
$\begingroup$

Clearly $N\ge 2$. If $N=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$ is the unique prime factorization of $N$ (with $p_1<p_2<\cdots <p_n$), then $$\phi(N)=p_1^{\alpha_1-1}p_2^{\alpha_2-1}\cdots p_n^{\alpha_n-1}\times$$

$$\times (p_1-1)(p_2-1)\cdots (p_n-1)=2\cdot 7^2$$

If $N$ is even, then $p_1=2$ and $$2^{\alpha_1-1}p_2^{\alpha_2-1}\cdots p_n^{\alpha_n-1}\times$$

$$\times (p_2-1)\cdots (p_n-1)=2\cdot 7^2,$$

and $p_2-1$, $\cdots$, $p_n-1$ are all even, so there are two cases:

$a)$ Here $\alpha_1=2$ and $n=1$, but then $\phi(N)=2\neq 2\cdot 7^2$.

$b)$ Here $\alpha_1=1$ and $n=2$. Then $$\phi(N)=p_2^{\alpha_2-1}(p_2-1)=2\cdot 7^2$$

$p_2$ is an odd prime, so we have two cases:

$a)$ Here $p_2=7$, but then $3\mid p_2-1$, so $\phi(N)\neq 2\cdot 7^2$.

$b)$ Here $\alpha_2=1$. Then $p_2=99$ is not prime.

If $N$ is odd, then, since $p_1-1$, $p_2-1$, $\ldots$, $p_n-1$ are all even, we get $n=1$, so $$\phi(N)=p_1^{\alpha_1-1}(p_1-1)=2\cdot 7^2$$

We get the same situation as before (with two cases). No solutions.

$\endgroup$
3
$\begingroup$

Note that $\phi(n)$ is even for all $n\gt2$. Consequently, if $2\lt m,n$ with $\gcd(m,n)=1$, then $4\mid\phi(mn)$, since $\phi(mn)=\phi(m)\phi(n)$. Now $4\not\mid98$, so $\phi(N)=98$ is possible only if $N=p^r$ or $2p^r$ for some odd prime $p$. But $\phi(2p^r)=\phi(p^r)=p^{r-1}(p-1)=98=2\cdot7^2$ clearly has no solution, mainly because $p=99$ is not a prime. (More precisely, if $r=1$ then $p=99$, while if $r\gt1$ then $p=7$, in which case $p-1=6$ implies $3\mid\phi(N)$, each of which is a contradiction.)

$\endgroup$

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