euler_phi() computing time

savecancel

This looks like a homework, so try to implement the own fair version of the following code, based on the formula $$\varphi(n)=n\prod_{p\text{ prime dividing }n}\left(1-\frac 1p\right)\ .$$

sage: def my_euler_phi(n):
....:     return ZZ( n*prod( [ 1 - 1/p for p in ZZ(n).prime_divisors() ] ) )

Test of the two-liner:

sage: euler_phi( 10**27+864291 )
857068852255018256626311168

sage: my_euler_phi( 10**27+864291 )
857068852255018256626311168

Note: The code for a function can be simply inspected in the sage interpreter via ??, in our case for instance ??euler_phi or euler_phi?? . In our case one finds immediately the line with return ZZ(pari(n).eulerphi()) ...

Note: The formula is based on the isomorphism $\mathbb Z/(mn) \cong (\mathbb Z/m)\times (\mathbb Z/n)$ for relatively prime integers $m,n$. This delivers the (so called restricted, or arithmetic) multiplicativity of $\varphi$, in this case $\varphi(mn)=\varphi(m)\varphi(n)$. So it is enough to prove the formula for prime powers...