3
$\begingroup$

$$\frac{n}{\phi(n)}=\frac{n}{n\prod_{p|n}\left(1-\frac{1}{p}\right)}=\frac{1}{\prod_{p|n}\left(1-\frac{1}{p}\right)}$$

How do I learn to understand these equations by myself as I can't seem to find the mathematical notation descriptions online?

$\endgroup$
7
$\begingroup$

The big pi, $\prod$ denotes a product. The subscript on this tells you which numbers this product is over. In this example, the subscript says $p|n$ which means "$p$ divides $n$" i.e. the product is over all the prime numbers $p$ that divide $n$ (the prime factors of $n$). $\phi(n)$ denotes the Euler-Totient function. This counts the number of integers $m<n$ which are co-prime to $n$, i.e. have $\gcd(m,n)=1$.

As an example, say we have $n=105=3\times5\times7$. Then $$\prod_{p|n}\left(1-\frac1p\right)=\left(1-\frac13\right)\times\left(1-\frac15\right)\times\left(1-\frac17\right)=\frac{16}{35}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.