1
$\begingroup$

Find n if $ϕ(n) = 2^{6} \times 17$ and $τ(n) = 12$.

$\endgroup$
3
  • $\begingroup$ $\phi(n)$ is standard notation for the number of positive integers less than $n$ which are coprime to $n$. What does $\tau(n)$ denote? We'll have a difficult time answering you if we don't know that. Also, if you have any thoughts on how to proceed, please relate them to us. We can then give you better help. $\endgroup$ Apr 9, 2013 at 0:04
  • 2
    $\begingroup$ @CameronBuie $\tau(n)$ is a pretty common notation for the number of divisors of $n$. $\endgroup$ Apr 9, 2013 at 0:06
  • $\begingroup$ $n = 2890$, divisors = $\{1, 2, 5, 10, 17, 34, 85, 170, 289, 578, 1445, 2890\}$. $\endgroup$
    – Amzoti
    Apr 9, 2013 at 0:10

1 Answer 1

4
$\begingroup$

Note that for any prime $p$, $\phi(p^k)=p^k-p^{k-1}$ and $\tau(p^k)=k+1$, so $n$ is not a power of a single prime.

Now, writing $n=p_1^{k_1}\cdots p_m^{k_m}$, where the $p_j$ are distinct primes indexed in increasing order, and where the $k_j$ are positive integers, we have $$\tau(n)=(k_1+1)\cdots(k_m+1).$$ Hence, there are only a few possibilities for the form of the decomposition of $n$ into prime powers:

(1) $n=p_1^1p_2^5,$

(2) $n=p_1^5p_2^1,$

(3) $n=p_1^2p_2^3,$

(4) $n=p_1^3p_2^2,$

(5) $n=p_1^1p_2^1p_3^2,$

(6) $n=p_1^1p_2^2p_3^1,$

(7) $n=p_1^2p_2^1p_3^1.$

(Why are there no other possibilities?)

In cases (1) through (4) (with $n=p_1^{k_1}p_2^{k_2}$), we would have $$\phi(n)=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1}),$$ and in cases (5) through (7) (with $n=p_1^{k_1}p_2^{k_2}p_3^{k_3}$), we would have $$\phi(n)=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})(p_3^{k_3}-p_3^{k_3-1}).$$ Note that each $p_j-1$ will necessarily divide $\phi(n)$, regardless of which of the cases holds, and when $k_j>1$ we have that $p_j^{k_j-1}$ is a (nontrivial) factor of $\phi(n)$, as well. Since the primes are indexed in increasing order, this alone should let you rule out several cases quickly. Can you take it from here?

$\endgroup$
1
  • $\begingroup$ Very nice +1! He has this and a numeric answer above - which should make life easy - now he has only understand it! :-) $\endgroup$
    – Amzoti
    Apr 9, 2013 at 0:24

You must log in to answer this question.

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