/*
** invphi.gp ver. 1.0 (c) 2005,07 by Max Alekseyev
**
** invphi(n)	computes all solutions to the equation eulerphi(x)=n with respect to x.
** numinvphi(n)	computes the number of such solutions and is faster than #invphi(n).
*/

{ numinvphi(n,m=1) = local(s=0,k,p); 
  if(n==1,return(1+(m<2))); 
  fordiv(n,d,
    if(d<m,next);
    p=d+1; 
    if(!isprime(p),next);
    k=n\d;
    while(1,
      s+=numinvphi(k,p);
      if(k%p,break);
      k\=p
    );
  );
  s
}

{ invphi(n,m=1) = local(k,p,P,R=Set()); 
  if(n==1, 
    if(m<2, return([1,2]), return([1]));
  );
  fordiv(n,d,
    if(d<m,next);
    p=d+1; 
    if(!isprime(p),next);
    k=n\d; P=p;
    while(1,
      R=setunion(R,P*invphi(k,p));
      if(k%p,break);
      k\=p; P*=p;
    );
  );
  vecsort(eval(R))
}