SharedSage genom exempel / Aritmetiska_funktioner.sagewsOpen in CoCalc
Author: Robert Nyqvist

Aritmetiska funktioner

Låte nn vara ett positivt heltal. Då definieras Eulers fi-funktion ϕ(n)\phi(n) som antal positiva heltal i Zn\mathbb{Z}_n som är relativt prima med nn.
euler_phi(12)
4
Vilka av elementen i Z12\mathbb{Z}_{12} är relativt prima med 12?
filter(lambda a : gcd(a, 12) == 1, Zmod(12).list())
[1, 5, 7, 11]
Eulers fi-funktion för heltalen n=2,3,,20n = 2, 3, \ldots, 20.
table([[n, euler_phi(n)] for n in [2..20]], header_row = ['n', 'fi(n)'])
n fi(n) +----+-------+ 2 1 3 2 4 2 5 4 6 2 7 6 8 4 9 6 10 4 11 10 12 4 13 12 14 6 15 8 16 8 17 16 18 6 19 18 20 8
Vi kan även illustrera funktionen grafiskt.
fi = [[n, euler_phi(n)] for n in range(1000)] list_plot(fi, aspect_ratio = 1)
Låt aa vara ett heltal och pp ett udda primtal. Då definieras Legendresymbolen (a/p)(a/p) enligt (ap)={1om x2a(modp) har en lo¨sning1om x2a(modp) saknar lo¨sning \left(\frac{a}{p}\right) = \begin{cases} \phantom{-}1 & \text{om $x^2 \equiv a \pmod{p}$ har en lösning} \\ -1 & \text{om $x^2 \equiv a \pmod{p}$ saknar lösning} \end{cases} gcd(a,p)=1\gcd(a, p) = 1, och (a/p)=0(a/p) = 0pap \mid a. Notera att Lagendresymbolen är en funktion a(a/p)a \mapsto (a/p) för olika primtal pp. I Sage är (a/p)(a/p) implementerad som legendre_symbol(aa, pp).
Är x25(mod17)x^2 \equiv 5 \pmod{17} lösbar?
legendre_symbol(5, 17)
-1
Tydligen inte. Kanske x28(mod17)x^2 \equiv 8 \pmod{17} är lösbar?
legendre_symbol(8, 17)
1
Ja! Låt oss bestämma lösningarna - det finns två stycken.
x1 = mod(8, 17).sqrt() # en av lösningarna x1
5
x2 = 17 - x1 # den andra lösningen x2
12
# kontroll x1^2, x2^2
(8, 8)
Låt n=p1a1p2a2pkakn = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k} vara primtalsfaktoriseringen av nn Då definieras Möbiusfunktionen μ(n)\mu(n) enligt μ(n)={1om n=1(1)kom a1=a2==ak=10annars. \mu(n) = \begin{cases} 1 & \text{om $n = 1$}\\ (-1)^k & \text{om $a_1 = a_2 = \cdots = a_k = 1$} \\ 0 & \text{annars}. \end{cases} Alltså är μ(n)=0\mu(n) = 0 om och endast om a2na^2 \mid n för något heltal aa.
table([[n, moebius(n)] for n in [1..10]], header_row = ['n', 'my(n)'])
n my(n) +----+-------+ 1 1 2 -1 3 -1 4 0 5 -1 6 1 7 -1 8 0 9 0 10 1