Question

Number Theory

Could someone explain to me how to work out "The number of solutions of PHI(n) = 2"

This is elementary number theory, working with primes.

Answer 1

Eulers totient function?

Answer 2

Could be Euler's.

Answer 3

let x = 2*3*5*...(product of prime numbers up to nth term)
then if there are exactly (n+1) number of prime numbers less than x then only PHI(n)=2

Answer 4

@Jack172 There are many things that can give solutions of 2^n though.
I'm assuming this problem might extend to logic and manifolds too.

Answer 5

for example: x=2*3=6 and there are 3 prime numbers less than 6 So, PHI(6)=2

Answer 6

@primeralph lol

Answer 7

$$\lim_{T\to\infty}\frac{1}{2T}\int_{-T}^Tn^{s-it}\frac{\zeta(s-it-1)}{\zeta(s-it)} dt=\phi(n)$$

Answer 8

@Jack172 Mathematics.
Never heard of logic or manifolds?

Answer 9

Sorry I realise that question wasn't very specific,

I know how to use Euler's Totient Function to calculate how many integers are coprime to a number (as long as coprime numbers are less obviously)

However I'm not sure how to use it to calculate how many numbers (n) there are that have a value of PHI(n) = some value

Here are some examples from previous tests
Find the number of solutions to:
PHI(n)=2
PHI(n)=6
PHI(n)=4

I'm not sure how to work this out, my lecture notes don't really clarify anything

Thanks in advance for your help

Answer 10

My bad heres a better inequality $$\sqrt{n}\le \phi(n)$$

Answer 11

for n not equal to 2 or 6

Answer 12

Now just check the first n^2 cases

Answer 13

here is a link that might help
it give a method for finding the number of solutions to \(\phi(n)=72\)
http://math.stackexchange.com/questions/284003/computing-n-such-that-phin-m

Answer 14

For small n, I would just use a naive algorithm, like checking all the cases less then some number

Answer 15

Okay great! Thank you so so much!
I'm going to work through a few examples and try an get my head around it :)

Answer 16

So I understand what it's for now, but is there a quick way to work it out?
Say for example PHI(n)=8

In a 30 minutes spot test I'd prefer not to waste half of it writing out lists of coprime numbers!

And again, thankyou so much, I've got a final coming up so I'm trying to nail everything I'm unsure of!

Answer 17

I came across this issue in undergrad as well. In theory, we are looking for an "inverse function" \[\phi ^{-1}\]. However, this "inverse function" spits out sets of numbers instead of an individual value (i.e. it's a one-to-many function). And in practice, there is no known explicit formula to calculate the inverse function (however, there are recursive ones). The best resource I found to date was this paper
http://www.new.dli.ernet.in/rawdataupload/upload/insa/INSA_2/20005a81_22.pdf
Hope this helps