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!

Printable View

- September 27th 2008, 06:38 AMcutmeoutEuler Phi Help
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! - September 27th 2008, 08:31 AMo_O
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: - September 27th 2008, 11:15 AMcutmeout
Right. I understand how to evaluate Phi(n), but I'm concerned with finding an n such that Phi(n) is equal to a given number.

- September 27th 2008, 10:40 PMTwistedOne151
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. - September 28th 2008, 12:06 AMOpalg
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... - September 28th 2008, 12:53 PMcutmeout
Thank you everyone; I understand it much better now.