For some power of a prime, .
And since is a multiplicative function, let be the prime-power decomposition of . Then:
So if I were to find , we would have:
Hi everyone,
I need to find all integers n such that Phi(n) = 160 and as an extension, make a list of all primes that might possibly divide x if Phi(x) = 1000. I'm a bit lost on this and was wondering if anyone could give me a useful start? Thanks!
As o_O noted, , and .
The prime factorization of 160 is . Note that the above tells us that . Thus, we need to find prime p and integer n≥1 such that is equal to five times a power of two (less than ). This needs either p=5 or p-1 is 5 times a power of 2.
This leaves us with p=5, p=11, or p=41.
The first has
and 160=8*20, and .
Thus 25*16=400 is one number n such that .
For the second, p=11, we have
and 160=16*10, and .
Thus 11*32=352 is the second number n such that .
The third case, p=41, gives ; here 160=4*40, and .
Thus 41*8=328 is the third number n such that .
Working similarly, you can find the primes that might divide x if .
--Kevin C.
So if we write and use the fact that then we get 25×16=400 as the first solution.
But there is another possibility here. Notice that . So we could write
Here again, you get more than one solution. Starting from 160=16×10 and using , we need to find all the numbers n for which :
is one possibility. But so are
,
,
, and finally
.
Yet again, there are other possibilities...