> p:=1234567891;
> eulerphi(p):=p-1;
> ifactors(eulerphi(p));

                           p := 1234567891


                  eulerphi(1234567891) := 1234567890


         [1, [[2, 1], [3, 2], [5, 1], [3803, 1], [3607, 1]]]

> Power(2,(eulerphi(p)/2)) mod p;
> Power(2,(eulerphi(p)/3)) mod p;
> Power(2,(eulerphi(p)/5)) mod p;
> Power(2,(eulerphi(p)/3803)) mod p;
> Power(2,(eulerphi(p)/3607)) mod p;

                              1234567890


                                  1


                              486077068


                              167769818


                              518918469

> Power(3,(eulerphi(p)/2)) mod p;
> Power(3,(eulerphi(p)/3)) mod p;
> Power(3,(eulerphi(p)/5)) mod p;
> Power(3,(eulerphi(p)/3803)) mod p;
> Power(3,(eulerphi(p)/3607)) mod p;

                              1234567890


                              591191227


                              293485970


                              1143307061


                              1058784230