or TOTIENT FUNCTION
\[\varphi(n)\]
\[\varphi (n)= n\cdot \prod_{p|n}^{ } (1-\frac{1}{p}) \\ with \ p \ prime \ number \]
A000010 Euler's totient function phi(n).
n=12
euler_phi(n)
[i for i in range(n) if gcd(n,i) == 1]
len([i for i in range(4) if gcd(4,i) == 1]) == euler_phi(4)
#######
n = 2005
prime_divisors(n)
phi = n*prod([1 - 1/p for p in prime_divisors(n)]); phi
euler_phi(n)
#######
#calcul A000010(n)
#Choose a value for n, example with 329.
n=329
sum([ gcd(n,k) * exp( 2*pi*I*k/n ) for k in range(0, n) ]).numerical_approx();
#".numerical_approx()" can be deleted to see the whole expression
sum([ gcd(n,k) * cos( 2*pi*k/n ) for k in range(0, n) ]).numerical_approx();
#######
n=16
R = Zmod(16)
L = R.list_of_elements_of_multiplicative_group(); L
euler_phi(n)
R = IntegerModRing(16)
R.unit_group_exponent()
R.unit_group_order()
\[n=60=2^{2}\cdot 3\cdot 5\]
\[\varphi (60)= 60 \cdot (1-\frac{1}{2})\cdot (1-\frac{1}{3})\cdot (1-\frac{1}{5})\]
\[\varphi (60)= 60 \cdot (\frac{2}{2}-\frac{1}{2})\cdot (\frac{3}{3}-\frac{1}{3})\cdot (\frac{5}{5}-\frac{1}{5})\]
\[\varphi (60)= 60 \cdot \frac{1}{2}\cdot \frac{2}{3}\cdot \frac{4}{5}=\frac{480}{30}=16\]
\[\frac{1}{\varphi (60)}=\frac{1}{60}\cdot \frac{1}{(1-\frac{1}{2})}\cdot \frac{1}{(1-\frac{1}{3})}\cdot \frac{1}{(1-\frac{1}{5})}=\frac{1}{16}\]
Multiplicative function :
\[\varphi (u\times v)=\varphi (u)\times \varphi (v)\]
\[if~~p~~is~a~prime~number~so~\varphi (p)=p-1\] and if p and q are two prime numbers : \[\varphi (p*q)=(p-1)*(q-1) =\varphi (p)*\varphi (q)\]
If $p$ is a prime number and $k> 0$ : \[\varphi (p^{k})=p^{k}-p^{k-1}\] \[\varphi (p^{k})=p^{k-1}(p-1)\]
If $a$ and $b$ are coprime ( $\equiv GCD(a,b)=1$ ) : \[\varphi (a*b)=\varphi (a)*\varphi (b)\] If $GCD(a,b)=1$ , so $a^{\varphi (b)}\equiv 1~mod(b)$
$\varphi(n)$ is also the number of 1's in a multiplication table Z/nZ.
(For the number of 0's in Z/nZ see Pillai's arithmetical function,
which is equal, too, to the number of 1's in the character table for point group Cn.)
A018804 Pillai's arithmetical function.
$\varphi(2n)$ is the size of a square companion matrix of the minimal cyclotomic polynomial of $(-1)^{\frac{1}{n}}$ .
And if we consider $1^{\frac{1}{n}}$, the root of unity, the size of the companion matrix of the cyclotomic polynomial is $\varphi(n)$, where the last term (of the last row and the last column) is $\mu(n)$ .
A062570 phi(2*n).
A013595 Triangle coeff. cyclotomic poly.
# 1'th root of unity
x = polygen(QQ, 'x')
companion_matrix(cyclotomic_polynomial(1,'x'))
M1 = companion_matrix(cyclotomic_polynomial(1,'x'))
M1.charpoly()
M1[euler_phi(1)-1,euler_phi(1)-1]
nth cyclotomic polynomial :
\[\Phi _{n}(x)=\prod_{d|n}^{ } (x^{d}-1)^{\mu (\frac{n}{d})}\]
\[\Phi _{n}(x)=\prod_{1\leq k\leq n ~gcd(k,n)=1}^{ } (x-e^{2i\pi \frac{k}{n}})\]
\[\prod_{d|n}^{ }\Phi _{d}(x)=x^{n}-1\]
\[x^{n}-1=0 \\x^{n}=1\\x=\sqrt[n]{1}\]
\[x^{n}+1=0 \\x^{n}=-1\\x=\sqrt[n]{-1}\]
# nth cyclotomic polynomial
#\[\varphi _{n}(x)=\prod_{d|n}^{ } (x^{d}-1)^{\mu (\frac{n}{d})}\]
x = polygen(QQ, 'x')
n=12
prod([(x^d - 1)^(moebius(n/d)) for d in divisors(n)])
#\[\varphi _{n}(x)=\prod_{1\leq k\leq n ~gcd(k,n)=1}^{ } (x-e^{2i\pi \frac{k}{n}})\]
[exp(2*pi*I*k/n) for k in range(n+1) if gcd(k,n) == 1]
root_list=[exp(2*pi*I*k/n) for k in range(n+1) if gcd(k,n) == 1]
prod([(x - root) for root in root_list]).rational_simplify()
#\[\prod_{d|n}^{ }\Phi _{d}(x)=x^{n}-1\]
def polynx(n):
return prod([(x^j - 1)^(moebius(n/j)) for j in divisors(n)])
polynx(2)
prod([polynx(d) for d in divisors(n)]) #==x^n-1
#\[\prod_{d|n}^{ }\Phi _{d}(x)=x^{n}+1\]
def polynx(n):
return prod([(x^j + 1)^(moebius(n/j)) for j in divisors(n)])
polynx(2)
prod([polynx(d) for d in divisors(n)]) #==x^n+1
\[\sum_{d|n}^{ } \varphi (d)= n\]
n == sum([euler_phi(d) for d in divisors(n)])
Exemple with n = 10 :
\[\sum_{d|10}^{ } \varphi (d)= \varphi (1)+\varphi (2)+\varphi (5)+\varphi (10) = 1+1+4+4 =10\]
\[n-\varphi(n) \]
Cototient
A051953 Cototient(n) := n - phi(n).
\[\forall ~n > 0~~~\varphi({n^2}) = n\cdot \varphi(n) \]
A002618 n*phi(n).
\[\sum_{1}^{n}\varphi (n)\]
Sum of totient function.
A002088 Sum of totient function.
from sage.rings.polynomial.complex_roots import complex_roots
#function root of unity's graph
def rootofunitygraph(y):
x = polygen(CC)
n = y
rts = var('rts_%d' % n)
rts
rts = complex_roots(x^n - 1)
rts
graphique = var('graphique_%d' % n)
graphique = list_plot([ComplexIntervalField(10)(rt[0]) for rt in rts] ,figsize=[4,4], color='red')
graphique.set_axes_range(-1, 1, -1, 1)
#graphique.axes_labels(['Re($z$)', 'Im($z$)'])
return graphique
#
#function primitive root of unity's graph
def primitiverootofunitygraph(y):
x = polygen(CC)
n = y
rts = var('rts_%d' % n)
rts
rts = complex_roots(x^n - 1)
rts
graphique = var('graphique_%d' % n)
graphique = list_plot([ComplexIntervalField(10)(rt[0]) for rt in rts] ,figsize=[4,4], color='red')
prts=list_plot([exp(2*pi*I*k/n) for k in range(n+1) if gcd(k,n) == 1],figsize=[4,4], color='blue')
graphique.set_axes_range(-1, 1, -1, 1)
#graphique.axes_labels(['Re($z$)', 'Im($z$)'])
return graphique+prts
#
n=14
rootofunitygraph(n)
primitiverootofunitygraph(n)
#roots of unity
A=QQ[x](x^n-1).roots(QQbar)
B=[exp(2*pi*I*k/n) for k in range(n)]
E=[exp(2*pi*I*k/n) for k in range(n+1) if gcd(k,n) == 1]
print 'Roots of unity : ',A
print 'Roots of unity : ',B
print 'Primitive Roots of unity : ',E
C=len(QQ[x](x^n-1).roots(QQbar))
print 'Number of Roots of unity : ',C
D=len(B)
print 'Number of Roots of unity : ',D
F=len(E)
print 'Number of primitive Roots of unity : ',F
#number of roots of unity -- number of roots of unity minus number of primitives roots of unity = A051953 Cototient(n) := n - phi(n).
#A063985 Partial sums of cototient sequence A051953.
#A002088 Sum of totient function: a(n) = Sum_{k=1..n} phi(k), cf. A000010.
#Roots of unity complex_plot
f(z) = z^6 + 1
complex_plot(f, (-1, 1), (-1, 1), axes_labels = ['Re($z$)', 'Im($z$)'], figsize=[4,4])
##
from sage.rings.polynomial.complex_roots import complex_roots
x = polygen(CC)
rts = complex_roots(x^6 - 1)
[ComplexIntervalField(10)(rt[0]) for rt in rts]
graphique2=list_plot([ComplexIntervalField(10)(rt[0]) for rt in rts] ,figsize=[4,4], color='red',pointsize=10)
graphique2.set_axes_range(-1, 1, -1, 1)
graphique2.axes_labels(['Re($z$)', 'Im($z$)'])
graphique2