The Legendre's function, which works like the Sieve of Eratosthene, gives the quantity of integers equal or lower than a number 'y' and that are prime with another number 'x'.
\[{Legendre_{x}}^{y}\equiv\sum_{d|x}^{ } \mu (d)\cdot \left \lfloor \frac{y}{d} \right \rfloor\] \[d|x : for~all~ ~\textit d ~~ that~ divide~ ~x.\\ We ~take~ only~ the~ integer~ part~ of ~~y/d.\]
Example : x = 6, y = 15
We are looking for the quantity of integers : lower than 15 and prime with 6.
The first thing to do is to look for the divisors of x : d|x
6 has 1, 2, 3, and 6 .
We know that our sum will have 4 terms.
And will be written :
\[{Legendre_{6}}^{15}\equiv \mu (1)\cdot \left \lfloor \frac{15}{1} \right \rfloor+\mu (2)\cdot \left \lfloor \frac{15}{2} \right \rfloor+\mu (3)\cdot \left \lfloor \frac{15}{3} \right \rfloor+\mu (6)\cdot \left \lfloor \frac{15}{6} \right \rfloor\]
\[=~(1)\cdot 15~+~(-1)\cdot7~+~(-1)\cdot5~+~(1)\cdot2~=~5\]
The result is 5.
There are 5 five numbers : 1, 5, 7, 13, 15 that are prime with 6 and equal or lower than 15.
x=6
y=15
sum([moebius(d)*y/d for d in divisors(x)])
When x=y the Legendre's function has the same result than the function phi of Euler.
We can write :
\[Legendre_{n} \equiv \sum_{d|n}^{ }\mu (d)\cdot \left \lfloor \frac{n}{d} \right \rfloor\]
\[\phi (n)= n\cdot \prod_{p|n}^{ } (1-\frac{1}{p})\]
\[\phi (n)= n\cdot \prod_{p|n}^{ } (1-\frac{1}{p})= \sum_{d|n}^{ } \mu (d)\frac{n}{d}\]
\[\sum_{d|n}^{ }\phi (d)=n\]
\[\sum_{d|n}^{ }\frac{\mu (d)}{d}= \prod_{p|n}^{ } (1-\frac{1}{p})\]
where p is a prime number.