Phi Euler

Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. Formally, it can be defined as the number of integers k in the range 1 less or equal than k less or equal than n for which g c d left parenthesis n comma k right parenthesis equals 1.

Euler's product formula states

phi left parenthesis n right parenthesis equals n product for p vertical line n of open parentheses 1 minus 1 over p close parentheses

For a prime number p and for an integer k, this expression reduces to

phi left parenthesis p to the power of k right parenthesis equals p to the power of k open parentheses 1 minus 1 over p close parentheses

phi_euler(Integer)

Given an integer n, returns phi left parenthesis n right parenthesis.