Find n if $ϕ(n) = 2^{6} \times 17$ and $τ(n) = 12$.
-
$\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$– Cameron BuieApr 9, 2013 at 0:04
-
2$\begingroup$ @CameronBuie $\tau(n)$ is a pretty common notation for the number of divisors of $n$. $\endgroup$– Thomas AndrewsApr 9, 2013 at 0:06
-
$\begingroup$ $n = 2890$, divisors = $\{1, 2, 5, 10, 17, 34, 85, 170, 289, 578, 1445, 2890\}$. $\endgroup$– AmzotiApr 9, 2013 at 0:10
1 Answer
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?
-
$\begingroup$ Very nice +1! He has this and a numeric answer above - which should make life easy - now he has only understand it! :-) $\endgroup$– AmzotiApr 9, 2013 at 0:24